Scheduling a stochastic job shop to minimize tardiness objectives.

Traditional job shop scheduling models ignore the stochastic elements that exist in actual job shops. This research concerned solution methods for the stochastic job shop problem. R and om elements were incorporated to aid in underst and ing the effects of uncertainty. The problem we analyzed had multiple machines and permitted general routings. We minimized two objective functions: expected tardiness and the probability that tardiness is above a threshold value. We assumed at most two moments, and the range, of the distribution of each r and om element. No assumptions were made about the type of dependence among the r and om elements. A simple recourse model was used to approximate the stochastic job shop. Under simple resource, decisions can depend only on initial conditions. We devised an algorithm for finding the optimal simple recourse schedule for a job shop. We also developed a heuristic procedure which allows limited updating of an initial schedule. The heuristic reduces the inflexibility of the simple recourse approach. The simple recourse job shop scheduling problem was represented as a disjunctive graph. In this representation, a schedule is obtained by resolving the direction of each disjunctive pair in the graph. Determining the value of a given schedule exactly is difficult, since the objective function depends on the r and om job completion times. To avoid this obstacle, a minimax approach was employed to solve the problem, under both tardiness objectives. In an exact procedure for the simple recourse problem, implicit enumeration is required to find the direction of each disjunctive arc. In addition, an upper bound on the objective value of each (partial) schedule must be determined. We derived upper bounds on the expected tardiness of a given schedule when two moments of each distribution function are available. We also computed upper bounds on the probability that tardiness is above a threshold value when up to two moments of each distribution function are known. The heuristic procedure we developed allows limited updating of an initial schedule during scheduling implementation. Initial simulation tests with the heuristic show it has better average tardiness performance than the ATC dispatching rule.PhDOperations researchUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/162087/1/8907090.pd