Minimizing Maximum Lateness in a Job Shop with Sequence Dependent Setups

by 

Mehmet R. Taner
Bilkent University

A job-shop scheduling problem involving family setups with a special structure seen in process industries is addressed.
First, we formulate a single-machine dynamic scheduling problem as a basic building block of the job-shop problem,
and develop state dependent scheduling rules for this single machine problem. Then, we establish a generalized scheduling
policy based on a characterization of the optimal results secured via Markov Decision Processes, and incorporate this policy
into an adoptive-iterative scheduling system to solve the job shop problem. We present computational results with two
different job shop scenarios to illustrate superior performance of the proposed procedure in comparison to that of the
existing alternatives.