Scheduling under resource constraints - deterministic models. Reprint of the journal Annals of Operations Research 7, Nos. 1-4 (1986). (English) Zbl 0668.90045

Annals of Operations Research 7. Basel: J. C. Baltzer AG, Scientific Publishing Company (ISBN 3-905-13525-6). xvi, 359 p. (1986).
Firstly, the book deals with deterministic scheduling problems, in the sense that information about each particular problem parameter is assumed to be either fully known or completely unknown in advance. It means that in the description of a problem there is no parameter of a non- deterministic nature.
Secondly, we consider problems in which, apart from machines (processors) additional constrained resources are used in processing tasks. This is perhaps the most important feature of the book, reflecting the growing interest in these problems over the past ten years. We try to give an extensive overview of models and techniques concerning different categories of resources and different resource requests of tasks.
Thirdly, we study not only problems which are direct generalizations of classical scheduling on parallel machines and job-shop scheduling problems, but also problems taking into account both the specific nature of computer systems, in which resource requests and releases of tasks are unknown in advance, and some particular features of scheduling in distributed systems. We also consider problems in which tasks may be processed using alternative processing modes, each one consisting of a machine and given numbers of additional resource units, which may in the most general case be renewable (only their total usage at every moment is constrained), nonrenewable (only their total consumption over the period of task processing is constrained) and doubly constrained (both usage and consumption are constrained). Multicriteria problems, as well as problems in which tasks are described by continuous, dynamic functions, which relate processing speed vs. resource amounts, are also examined. In this way, we proceed from simple scheduling problems to problems having more general importance, e.g. for performance evaluation of computer systems.
The chapter headings: Ch. 1: Preliminaries.
Part I: Discrete renewable resources.
Ch. 2: Parallel machines-efficient algorithms, complexity results. Ch. 3: Parallel machines-linear programming and enumerative algorithms. Ch. 4: Job shop systems.
Part II: Multiple category resources.
Ch. 5: General discrete resource requests. Ch. 6: Multicriteria scheduling. Ch. 7: Discrete and continuous resource requests.
Part III: Computer scheduling and system performance failures.
Ch. 8: Centralized systems. Ch. 9: Distributed systems.
Appendix: The computational complexity of decision problems - basic concepts.


90B35 Deterministic scheduling theory in operations research
90C31 Sensitivity, stability, parametric optimization
90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68N99 Theory of software
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
68-02 Research exposition (monographs, survey articles) pertaining to computer science


[1] Conway, R. W.; Maxwell, W. L.; Miller, L. W.: Theory of scheduling. (1967) · Zbl 1058.90500
[2] Baker, K. R.: Introduction to sequencing and scheduling. (1974)
[3] Lenstra, J. K.: Sequencing by enumerative methods. (1976) · Zbl 0407.90025
[4] Kan, A. H. G. Rinnooy: Machine scheduling problems: classification, complexity and computation. (1976) · Zbl 0366.90092
[5] Jr., E. G. Coffman: Computer & job-shop scheduling theory. (1976) · Zbl 0359.90031
[6] French, S.: Sequencing and scheduling: an introduction to the mathematics of the job-shop. (1982) · Zbl 0479.90037
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.