An effective approach for job-shop scheduling with uncertain processing requirements

Production systems often involve various uncertainties such as unpredictabl e customer orders or inaccurate estimate of processing times. Managing such uncertainties is becoming critical in the era of "time-based competition." For example, if a schedule is generated without considering possible order s in the future, new orders of significant urgency may interrupt those alre ady scheduled, causing serious violation of their promised delivery dates. The consideration of uncertainties, however, has been proven to be very dif ficult because of the combinatorial nature of discrete optimization compoun ded further by the presence of uncertain factors. This paper presents an effective approach for job-shop scheduling consideri ng uncertain arrival times, processing times, due dates, and part prioritie s, A separable problem formulation that balances modeling accuracy and solu tion method complexity is presented with the goal to minimize expected part tardiness and earliness cost. This optimization is subject to arrival time and operation precedence constraints (to be satisfied for each possible re alization), and machine capacity constraints (to be satisfied in the expect ed value sense). A solution methodology based on a combined Lagrangian rela xation and stochastic dynamic programming is developed to obtain dual solut ions. A good dual solution is then selected by using "ordinal optimization, " and the actual schedule is dynamically constructed based on the dual solu tion and the realization of random events. The computational complexity of the overall algorithm is only slightly higher than the one without consider ing uncertainties. To evaluate the quality of the schedule, a dual cost is proved to be a lower bound to the optimal expected cost for the stochastic formulation considered here. Numerical testing supported by simulation demo nstrates that near optimal solutions are obtained, and uncertainties are ef fectively handled for problems of practical sizes.