Zusammenfassung
Es werden Variationen für Reihenfolgeprobleme mit Unterbrechungen betrachtet bei denen die Aufgaben mit unterschiedlicher Bearbeitungszeit auf den einzelnen Maschinen gelöst werden können. Insbesondere wird ein Problem mit nichterneuerbaren Resourcen und zeitabhängigen Nachfragen behandelt und es wird gezeigt, daß dieses Problem durch eine Erweiterung der 2-Phasenmethode gelöst werden kann. In Phase 1 wird ein LP gelöst, während in Phase 2 ein zugehöriger Schedule konstruiert wird. Diese Konstruktion erfolgt durch die Bestimmung ganzzahliger Vektoren, die Ecken eines Polyeders entsprechen, der durch eine vollständig unimodulare Matrix definiert wird. In Spezialfällen reduziert sich dies auf Flußprobleme.
Abstract
Some variations are presented for the preemptive scheduling problem on unrelated processors, one shows how nonrenewable resources with a time-varying supply may be taken into account in an extension of the two-phase method; phase 1 consists in solving an LP problem and phase 2 is the construction of the schedule; such a construction reduces to the determination of integral vectors in polyhedra defined by totally unimodular matrices. In special cases, this is simply a compatible flow problem.
This is a preview of subscription content, log in via an institution to check access.
References
Berge C (1983) Graphes. Gauthier-Villars, Paris
Blazewicz J, Cellary W, Slowinski R, Weglarz J (1976) Deterministy czne problemy szeregowaia zadan na rownoleglych procesorach, Cz. I. Zbiory Zadanniezaleznych, Podstawy Sterowania 6:155–178
Lawler E-L, Labetoulle J (1978) On preemptive scheduling of unrelated processors by linear programming. J Assoc Comput Mach 25:612–619
Slowinski R (1980) Two approches to problems of resource allocation among project activities — a comparative study. J Opl Res Soc 31:711–723
Slowinski R (1979) Cost-minimal preemptive scheduling of independent jobs with release and due dates on open shop under resource constraints. Information Processing Letters 9:233–237
Slowinski R (1981) L'ordonnancement des tâches préemptives sur les processeurs indépendants en présence de ressources supplémentaires. RAIRO Informatique 15:155–166
Slowinski R (1984) Preemptive scheduling of independent jobs on parallel machines subject to financial constraints. European J of Operational Research 15:366–373
Weglarz J (1979) New models and procedures for resource allocation problems. Proc. of the 6th INTERNET Congress, vol 2. VDI-Verlag GmbH, Düsseldorf, pp 521–530
Weglarz J (1981) Project scheduling with continuously-divisible, doubly constrained resources. Management Sci 27:1040–1053
de Werra D (1984) Preemptive scheduling, linear programming and network flows. SIAM J on Algebraic and Discrete Methods 5:11–20
de Werra D (1984) A decomposition property of polyhedra. Mathematical Programming 30:261–266
Additional references on preemptive scheduling
Gonzalez T, Sahni S (1978) Preemptive scheduling of uniform processor systems. J ACM 25: 92–101
Sahni S, Gonzalez T (1976) Preemptive scheduling of two unrelated machines. Techn. Report 76-16, Univ. of Minnesota, Minneapolis
Blazewicz J, Cellary W, Slowinski R, Weglarz J (1986) Scheduling under resource constraints — deterministic models. Annals of Operations Research (Baltzer AG, Basel)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Cochand, M., de Werra, D. & Slowinski, R. Preemptive scheduling with staircase and piecewise linear resource availability. ZOR - Methods and Models of Operations Research 33, 297–313 (1989). https://doi.org/10.1007/BF01416077
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01416077