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.