Previous Scheduling Research
2.1 Introduction
Scheduling problems have been studied in a number of different fields, e.g. manufacturing, logistics, project management and different areas of computer science. A classic text book on scheduling is "Computer and job-shop scheduling theory" by Coffman [8]. Two more recent books on the subject are written by Pinedo [35] and by Blazewicz et al [1]. Two other relevant books on scheduling are [6] and [24], both of which take the form of a collection of research papers. In addition to these books there are a large number of research papers on the subject published in various journals and conference proceedings.
The Journal of Scheduling published by Wiley & Sons is entirely devoted to the subject of scheduling. This journal covers almost all aspects of scheduling, including areas such as Computer Science, Discrete Mathematics, Operational Research, Management, Manufacturing and Transport. The first issue of this journal was published in June 1998, indicating the growing interest in scheduling from industry and academia. Another journal that contains extensive results on scheduling is IIE Transactions, which is published by Kluwer academic publishers. This journal is composed of four Focused Issues: Design and Manufacturing, Operations Engineering, Quality and Reliability Engineering, and Scheduling and Logistics. Another journal which extensively publishes scheduling results is Real-Time Systems, which is also published by Kluwer. Scheduling results also appear in other journals, e.g., IEEE Transactions on Computers, IEEE Transactions and Parallel and Distributed Systems, IEEE Transactions on Robotics and Automation, SIAM Journal of Computing and ACM Transactions on Computer Systems.
In this chapter we give a brief overview of previous work on scheduling, with an emphasis on deterministic scheduling in computer science. Section 2.2 discusses previous work on multi-user and real-time scheduling on single-processor computers. In Section 2.3 we discuss some results of scheduling in multiprocessor and distributed computer systems. Section 2.4 gives a brief overview of scheduling in other contexts, e.g., disk scheduling, scheduling in manufacturing and project scheduling. In Section 2.5 commonly used heuristics for obtaining good schedules, e.g., simulated annealing and genetic algorithms, are described. In Section 2.6 we present some optimal and near optimal scheduling algo-