Scheduling jobs on several machines with the job splitting property

Scheduling jobs on several machines with the job splitting property

0.00 Avg rating0 Votes
Article ID: iaor20002785
Country: United States
Volume: 44
Issue: 4
Start Page Number: 617
End Page Number: 628
Publication Date: Jul 1996
Journal: Operations Research
Authors:
Keywords: programming: linear
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.