Static Shop Scheduling

In this chapter we will consider scheduling tasks on dedicated processors (machines). As we said in Section 3.1 we assume that tasks form n subsets (or jobs), belonging to set j, and two adjacent tasks of a job are to be performed on different machines. Unfortunately, most scheduling problems of this kind are NP-hard, which is especially true for optimality criteria other than C_max. In the first two sections we will concentrate first on polynomial time algorithms, where special cases of flow shop and open shop scheduling problems will be considered. Then the job shop scheduling problem will be discussed and two approaches, a heuristic based on simulated annealing and an exact based on branch and bound will be presented.