Schedule algorithms

---

ISBN 83-87674-39-7
Author: Czesław Smutnicki
Publisher: EXIT

---

About the book

The book is addressed to students, PhD students and graduates specializing in the field of scheduling tasks, designers of management systems, planning and control of unit production, short- and medium-series, designers of robotic systems, as well as computer scientists involved in the implementation of computer algorithms.

The scheduling issues model the functioning of real production systems and can be used to solve practical optimization and control problems occurring among others in conventional and flexible manufacturing systems, operating systems of digital machines, decision support systems, management systems.

The book contains an overview of selected scheduling problems along with the richness of methods and algorithms used to solve them, largely designed and researched by the author. Indicates alternative techniques and approaches recommended for specific classes of practical problems. It shows examples of applications, software and algorithmic tools used in practice as well as modern, surprising with its structure and effectiveness, methods of solving. Presented approaches can be, after appropriate modification, also used to analyze many complex optimization problems, including discrete and combinatorial problems, difficult due to lack of classical analytical properties (differentiability, convexity), multiplicity or curvature of dimensionality. Theoretical achievements directly imply the improvement of the quality of commercial software packages that support human activities in many areas of life.

The theoretical analyzes contained in the book are supplemented with the source codes of algorithms in C / C ++ along with the description, available on the author's website.

---

Table of Contents

1. Introduction

2. Introduction

2.1. Reality and modeling
2.2. Basic concepts
2.3. Criteria for optimization
2.4. Relations between criteria
2.5. Criteria for optimization and practice
2.6. Hierarchy of computational complexity
2.7. Characteristics of solutions
2.8. Regularity of criteria

3. Structures of control systems

3.1. PUSH strategy. MRP and ERP systems
3.2. SQUEZEE strategy. OPT systems
3.3. PULL strategy. JIT systems
3.4. Other strategies: CAW, CRS

4. Applications

4.1. Chemical industry
4.2. Automotive industry
4.3. architecture
4.4. Electronic industry
4.5. Heavy industry

5. Program packages

5.1. Project management systems
5.2. Task scheduling systems
5.3. MRP, MRP II, ERP systems
5.4. Simulation packages

6. Discrete optimization methods

6.1. Precise methods
6.2. Approximate methods

7. Basic single-machine problems

7.1. Basic problem
7.2. Dates of readiness and completion
7.3. Dependent tasks
7.4. Preparation and delivery times
7.5. Intermittent tasks
7.6. Lower limits for the general problem
7.7. Algorithms approximate the general problem
7.8. Approximate schemes
7.9. Review algorithms
7.10. Comments

8. Cost-effective single-machine problems

8.1. Polynomial cases
8.2. Integer model
8.3. PD algorithm
8.4. B & B algorithm
8.5. The dual approach
8.6. Alternative dual approaches
8.7. Simple approximate algorithms
8.8. Local search algorithms
8.9. Comments

9. Complex single-machine problems

9.1. Penalties for acceleration and delay
9.2. Scheduling in JIT systems

10. Basic flow problems

10.1. Basic problem
10.2. Polynomial cases
10.3. Some properties of the problem
10.4. Schemes B & B
10.5. Basic approximate algorithms
10.6. A cultural algorithm
10.7. DS algorithms
10.8. TS algorithms
10.9. Ant search
10.10. Simulated annealing
10.11. Evolutionary search
10.12. Geometric approach
10.13. Network-neural approach
10.14. Comments

11. Advanced flow problems

11.1. Regular, additive criterion
11.2. Modeling of additional restrictions
11.3. Comments

12. Nest problems

12.1. The problem and its models
12.2. Some properties of the problem
12.3. B & B scheme
12.4. Priority algorithms
12.5. Approximate algorithms
12.6. Local searches
12.7. The method of sliding the bottleneck
12.8. Simulated annealing
12.9. Searching with bans
12.10. Meeting restrictions
12.11. Evolutionary search
12.12. The dual approach
12.13. Neural networks
12.14. Comments