On the two-phase method for preemptive scheduling. (English) Zbl 0652.90064

Preemptive scheduling problems on parallel processors may in some cases be solved by a two-phase method: first solve an LP problem which will give the minimum total completion time T and the processing times of the jobs on the various processors; second construct a feasible schedule using T time units. Some extensions of this procedure are discussed. A general model for preemptive scheduling is described with a two-phase method for solving problems of this type.


90B35 Deterministic scheduling theory in operations research
90B30 Production models
90B10 Deterministic network models in operations research
90C90 Applications of mathematical programming
90C05 Linear programming
Full Text: DOI


[1] Berge, C., Graphes (1983), Gauthier-Villars: Gauthier-Villars Paris · Zbl 0213.25702
[2] Blazewicz, J.; Cellary, W.; Slowinski, R.; Weglarz, J., Scheduling under Resource Constraints: Deterministic Models (1986), J.C. Baltzer AG: J.C. Baltzer AG Basel · Zbl 0668.90045
[3] Cochand, M.; de Werra, D.; Slowinski, R., Preemptive scheduling with staircase and piecewise linear resource availability, (working paper 85/01 (January, 1986), Ecole Polytechnique Fédérale de Lausanne), OR · Zbl 0675.90045
[4] Golumbic, M., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press London · Zbl 0541.05054
[5] Slowinski, R., Production scheduling on parallel machines subject to staircase demand, (Cahiers de LAMSADE 74 (January 1987), Université de Paris-Dauphine)
[6] Slowinski, R., L’ordonnancement des tâches préemptives sur les processeurs indépendants en présence de ressources supplémentaires, R.A.I.R.O. Informatique, 15, 155-166 (1981) · Zbl 0461.68035
[7] de Werra, D., Preemptive scheduling, linear programming and network flows, SIAM Journal on Algebraic and Discrete Methods, 5, 11-20 (1984) · Zbl 0532.90047
[8] de Werra, D., A decomposition property of polyhedra, Mathematical Programming, 30, 261-266 (1984) · Zbl 0579.90049
[9] de Werra, D., Variations on the integral decomposition property, Mathematical Programming Study, 26, 197-199 (1986) · Zbl 0586.90068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.