Modeling Job Shop Scheduling Problems

The job shop has a more general structure than the flow shop in which each job go through multiple processing stages (or machines) in an order that might be different than other jobs. The basic job shop scheduling problem holds the same assumptions that were made for the basic flow shop problem. In addition it is assumed that each job may be processed by a machine at most once, i.e., without recirculation. 

A colored Gantt chart of a possible schedule is shown in Fig. 3.7. Notice that no more than one operation of the same job is being processed at the same time and no machine is processing two operations at the same time. Also, the order of operations is maintained for each job across the schedule, as given in Fig. 3.6. Clearly this many possible schedules (block orders) satisfying the requirement, but it is needed to find the one with the shortest length (makespan). 

This problem is extensively studied in the hterature with various solution methods and several modelling approaches. One of the first Mixed Integer Programming models for the problem was developed by Manne [7] in 1960 and adopted here as described by Conway et al. [2]. 

1 if the jth operation of job i requires machine k 0 otherwise Tik = the starting time of job i on machine k 

For the requirement that a machine can process only one job at a time, we have for 

---