Intermittent Production Scheduling: Practical Formulations, Relaxation, and Decomposition Procedures

Intermittent production scheduling encompasses the classical job shop and project scheduling problems. Viewed from the perspective of the researcher, these complex problems require some simplifying assumptions to improve our ability to design scheduling procedures. These simplifying assumptions are in essence constraints on the problem formulation. Viewed from the perspective of the manager, practical formulations may require the relaxation of these constraints. This chapter reports on some research, undertaken by the authors, aimed at extending results obtained with simplified formulations to formulations in which some of the assumptions are relaxed. Assumptions relaxed are: 1) due dates are fixed and must be met; 2) machine capacity is fixed; 3) technological precedence requirements are strictly applied; 4) transportation times and set-up times are negligible; 5) processing times are deterministic; and 6) no new jobs arrive during the scheduling period. Two approaches are pursued. The first relaxes one or two constraints at a time and explores the usefulness of schedules generated using standard single-pass or multi-pass procedures. The second starts with a more general formulation and develops formal decomposition procedures that allow subproblems to be solved using standard procedures.