Models and algorithms of time-dependent scheduling (Q778893): Difference between revisions

The book is a monograph about time dependend scheduling, it is the second edition of a monograph of the author from Poznan (Poland) which has been published in 2008 [Time-dependent scheduling. Berlin: Springer (2008; Zbl 1155.90004)]. The book has more than 500 pages organized in 6 parts and can be seen as the ``state of the art'' of the research results in the field of time dependent scheduling, but also as a reference to the history of more than 60 years of research. Part 1 deals with ``fundamentals'', that means the basis for stating scheduling problems is provided, the main solution methods are introduced, starting from well-known algorithms to heuristics and other approximative methods like branch-and-bound. That all is concluded with the complexity classification, mainly the proof of NP-hardness of some scheduling problems. Part 2 is called ``Scheduling models''. Here, at first, the classical scheduling models are treated, classical means here that all job processing times are fixed and known in advance. Then the so-called ``modern models'' are mentioned, here the job processing times may vary over the time, depending on the machine used or the position of the job in the process. At last, the models with time depending processing times are analyzed. Part 3 concentrates on ``Polynomial problems'', where single machine, parallel machine models and at last dedicated machine problems (that means here are models like ``flow shop'', or ``open shop'' are solved) are discussed with algorithmic approaches. Part 4 concentrates on NP-hard problems in this field of scheduling. Like in Part 3, also the different single machine, parallel machine and dedicated machine problems are compared. Part 5 looks at the possible algorithms to handle the problems. Besides exact algorithms, her are also approximation schemes, heuristics, greedy algorithms and local search algorithms are provided. Part 6 is called ``Advanced topics'' and looks at the models with time dependent processing times and additional constraints, like precedence constraints or bi-criteria problems or limited machine availability. Conclusion: The book presents a lot of material for time dependent scheduling, it is full of algorithms (in pseudo-code) and of complexity proofs, it provides a deep insight to the theory and practice of scheduling.