Scheduling jobs on several machines with the job splitting property

• 成果类型: Article
• 署名作者: Serafini, P
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.44.4.617
• 发表日期: 1996
• 页码: 617-628
• 关键词: industries; textiles; model for loom scheduling; network flow algorithms; application to scheduling; Scheduling; sequencing multiple machines

摘要

This scheduling model is derived from the real problem of scheduling looms in a textile industry. Jobs may be independently split. over several specified machines, and preemption is allowed. Deadlines are specified for each job, and jobs are assumed to be available. It is shown that minimizing maximum weighted tardiness can be done in polynomial time. The case of uniform machines (as in the considered application) can be modeled as a network flow, and minimization of maximum tardiness can be done in strongly polynomial time. The case of unrelated machines can be solved either by generalized flow techniques or by Linear Programming. Attention is also focused on the problem of finding so-called Unordered Lexico Optima, in order to schedule nonbinding jobs as early as possible.