Scheduling Jobs on Several Machines with the Job Splitting Property

Paolo Serafini
Additional contact information
Paolo Serafini: University of Udine, Italy

Operations Research, 1996, vol. 44, issue 4, 617-628

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.

Keywords: industries; textiles; model for loom scheduling; network flow algorithms; application to scheduling; scheduling; sequencing multiple machines; application in textile industry (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.44.4.617 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:44:y:1996:i:4:p:617-628

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().