- 1 GONZALEZ, T, AND SAHNI, S Open shop scheduhng to mmtmize fimsh time J. ACM 23, 4 (Oct 1976), 665 -679 Google Scholar
- 2 GONZALEZ, T, AND SAHNI, S Preemptive schedulmg of uniform processor systems J A CM 25, 1 (Jan 1978), 92-101 Google Scholar
- 3 SAHNI, S, AND GONZALEZ, T Preemptive scheduhng of two unrelated machines Tech. Rep 76-16, Comptr Sct Dept, U of Minnesota, Mmneapohs, Mmn, Nov 1976Google Scholar
- 4 MCNAUGHTON, R Sequencmg with deadhnes and loss functions Manage Scl 6 (1959), 1-12Google Scholar
- 5 STERN, H l Mimmmmg makespan for independent jobs on nomdentlcal parallel machines--An optimal procedure Tech Rep, Dept of Industrial Eng and Mgt, Ben-Gunon U of the Negev, Beer-Sheva, Israel, March 1976Google Scholar
Index Terms
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
Recommendations
Preemptive and non-preemptive scheduling on two unrelated parallel machines
AbstractIn this paper, for the problem of minimizing the makespan on two unrelated parallel machines we compare the quality of preemptive and non-preemptive schedules. It is known that there exists an optimal preemptive schedule with at most two ...
Complexity of preemptive minsum scheduling on unrelated parallel machines
We show that the problems of minimizing total completion time and of minimizing the number of late jobs on unrelated parallel machines, when preemption is allowed, are both NP-hard in the strong sense. The former result settles a long-standing open ...
Complexity of preemptive minsum scheduling on unrelated parallel machines
We show that the problems of minimizing total completion time and of minimizing the number of late jobs on unrelated parallel machines, when preemption is allowed, are both NP-hard in the strong sense. The former result settles a long-standing open ...
Comments