Scheduling to Minimize Maximum Workload

Hans-Jakob Lüthi and Andrés Polyméris
Additional contact information
Hans-Jakob Lüthi: Institut für Operations Research Eidgenössische Technische Hochschule, Zürich, Switzerland
Andrés Polyméris: Institut für Operations Research Eidgenössische Technische Hochschule, Zürich, Switzerland

Management Science, 1985, vol. 31, issue 11, 1409-1415

Abstract: We pose the following problem: given m jobs, each of which requires a certain total amount of labour that must be performed within specified time periods, how should one schedule the jobs' execution to obtain a total workload that is as even as possible? A related question is: what is the minimal work capacity needed to accomplish all jobs? These questions can be formulated as a linear program, but the number of variables and constraints required usually will be large. Using linear duality theory we instead derive a purely combinatorial problem whose resolution leads to the needed minimal capacity, and thus to the imposed bottleneck. Then we concentrate on the important special case where the time constraints for performing each job are in the form of a single time interval: We detail a simple procedure that efficiently determines the minimal capacity and the bottleneck. A second efficient combinatorial algorithm determines a feasible execution schedule which minimizes the maximum total workload. These algorithms require a computational time of the order of m 2 and negligible core memory, and for most practical applications can be implemented on microcomputers.

Keywords: production/scheduling: workstudies; programming: linear; algorithms (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.31.11.1409 (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:ormnsc:v:31:y:1985:i:11:p:1409-1415

Access Statistics for this article

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