Minimal Resources for Fixed and Variable Job Schedules

Ilya Gertsbakh and Helman I. Stern
Additional contact information
Ilya Gertsbakh: Ben Gurion University of the Negev, Beersheva, Israel
Helman I. Stern: Ben Gurion University of the Negev, Beersheva, Israel

Operations Research, 1978, vol. 26, issue 1, 68-85

Abstract: We treat the following problem: There are n jobs with given processing times and an interval for each job's starting time. Each job must be processed, without interruption, on any one of an unlimited set of identical machines. A machine may process any job, but no more than one job at any point in time. We want to find the starting time of each job such that the number of machines required to process all jobs is minimal. In addition, the assignment of jobs to each machine must be found. If every job has a fixed starting time (the interval is a point), the problem is well-known as a special case of Dilworth's problem. We term it the fixed job schedule problem (FSP). When the job starting times are variable, the problem is referred to as the variable job schedule problem (VSP), for which no known exact solution procedure exists. We introduce the problems by reviewing previous solution methods to Dilworth's problem. We offer an approximate solution procedure for solving VSP based on the entropy principle of informational smoothing. We then formulate VSP as a pure integer programming problem and provide an exact algorithm. This algorithm examines a sequence of feasibility capacitated transportation problems with job splitting elimination side constraints. Our computational experience demonstrates the utility of the entropy approach.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.1.68 (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:26:y:1978:i:1:p:68-85

Access Statistics for this article

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