Block method in scheduling tasks

---

ISBN 83-87674-49-4
Author: Józef Grabowski, Eugeniusz Nowicki, Czesław Smutnicki
Publisher: EXIT

---

About the book

The book deals with the problem of scheduling tasks. This problem occurs both in production systems and in computer systems and networks. The book presents mathematical models of problems, their properties and algorithms, based primarily on the so-called block method. This method is the original approach in the theory of task scheduling, which, using a simple conceptually and structurally graphical model, properties of the critical path in the graph and some other stuctural properties of problems, allows you to design accurate and approximate algorithms with surprisingly good numerical properties. The presented book is the first in Polish such a comprehensive and comprehensive presentation of the block method that is the output of the authors. After introducing the reader to the problem of scheduling tasks (notation, criteria, computational complexity), three most basic types of scheduling problems are discussed in detail: single-machine problems, flow problems and nesting problems. A number of practical generalizations are also presented, such as: transport, conversion, buffering, limited system capacity, palletizing. A large number of illustrative examples makes reading a book relatively easy, despite its rather theoretical nature.

The book is addressed to students of the senior years of Automation and Robotics as well as Information Technology, PhD students, as well as to research workers. It can also be helpful for planner and designer managers in the field of short-term management and production planning.

---

Table of Contents

1. Introduction

I. Introduction

2. Data, restrictions and criteria

2.1. Basic concepts
2.2. Equivalence of criteria

3. Problems

3.1. Classification of issues

II. Computational complexity and methods of solving discrete programming problems

4. Computational complexity

4.1. Measures of computational complexity
4.2. P and NP class issues, reducibility
4.3. Exemplary NP-complete issues

5. Methods of solving discrete programming problems

5.1. Direct calculation methods
5.2. Local optimization methods
5.3. Conclusions and remarks

III. One-machine problems

6. Problems "1BC" and "1BL"

6.1. The output problem
6.2. Preparedness, delivery, urgency of tasks
6.3. Task dependency
6.4. The problem of a bottleneck
6.5. The interruptability of tasks
6.6. Methods of solving
6.7. Lower limits
6.8. Approximate algorithms
6.9. C algorithm
6.10. GNZ block algorithm

7. Problems "1Bf"

7.1. Polynomial problems
7.2. The interruptability of tasks
7.3. Some properties of the problem
7.4. Lower limits
7.5. Algorithms approximate
7.6. Block ZG algorithm

8. Problems "1Bh"

8.1. Penalties for acceleration and lateness
8.2. A two-level decomposition

IV. Flow problems

9. Basic properties. Accurate algorithms

9.1. General wording of the issue
9.2. A two-machine flow issue
9.3. Three-way flow problem
9.4. Some features of the issue
9.5. Block method of division and restrictions
9.6. Rules for selecting tasks to be moved
9.7. Methods of determining the lower limits
9.8. Algorithm
9.9. Conclusions and remarks
9.10. Implementation of the algorithm
9.11. Calculation example
9.12. Flow issue

10. approximate algorithms

10.1. Priority algorithms
10.2. Algorithms based on the method of reducing the number of machines
10.3. Algorithms based on the method of relaxation of executive capabilities of machines
10.4. Algorithms based on the insert method

V. Nest problems

11. Block method in classic nesting problems

11.1. Mathematical model
11.2. Blocks of operations and their properties
11.3. Block method of division and restrictions
11.4. An overview of the methods of division and restrictions

12. Block method in socket problems with parallel machines

12.1. Mathematical model
12.2. Elimination properties of operation blocks
12.3. Block method of division and restrictions
12.4. Summary

13. Constructional algorithms in nesting problems

13.1. A classic nest problem
13.2. Socket problem with parallel machines

14. Generalization of nesting problems

14.1. Conversion and transport
14.2. Pallets
14.3. Other generalizations

Epilogue

Literature