Job Shop Scheduling with Simple Precedence Constraints

This paper presents a near-optimal scheduling methodology for job shops where each job consists of a small number of operations. Each operation requires a particular machine type for a specified processing time. There may be a "timeout" between successive operations for inspection, heat treatment, paperwork or other processing which does not require the use of the machine types under consideration Jobs also have different due dates and different levels of importance. The objective is to minimize the total weighted quadratic tardiness of the schedule. We present an efficient near-optimal scheduling method based on the Lagrangian relaxation technique and the list scheduling concept. The dual cost is a lower bound on the objective function, and can be used to measure the quality of the schedule generated. The multipliers contain sensitivity information, and can be used to answer a wide range of "what if" questions. Since the status of the shop does not change much from day to day, the multipliers can be easily updated and schedules can be efficiently reconfigured to incorporate new jobs and other changes occurring in the system. Most numerical results are within 1% of the dual optimum and are obtained with reasonable CPU times.