SCHEDULING OF MANUFACTURING SYSTEMS USING THE LAGRANGIAN-RELAXATION TECHNIQUE

Scheduling is one of the most basic but the most difficult problems to be solved in the manufacturing industry. Many of the methodologies currently used in industry result in what one manager has referred to as ''scheduling chaos,'' and overall shop goals such as on-time delivery of jobs are beyond control. There is a great need for improving the scheduling operation in complex and turbulent manufacturing environments. Unfortunately, problem characteristics generally translate into large-scale, discrete, dynamic, and / or stochastic scheduling formulations, which are generally considered impossible to solve in most practical situations. The logical strategy is to pursue scheduling methods which consistently generate good schedules efficiently. However, the schedule quality is often difficult to determine without actually knowing the optimum. In this paper, the practical solution of three manufacturing scheduling problems are examined. As each problem is formulated, constraints are added or modified to reflect increasing real world complexity. The first problem considers scheduling single-operation jobs on identical machines. The second problem is concerned with scheduling multiple-operation jobs with simple fork / join precedence constraints on identical machines. Lastly, the job shop problem is considered, where multiple-operation jobs with general precedence constraints are scheduled on multiple machine types. Lagrangian relaxation is used to decompose each of the scheduling problems into job- or operation-level subproblems. The subproblems are easier to solve than the original problem and have intuition appeal. This technique results in algorithms which generate near-optimal schedules efficiently, while giving a lower bound on the optimal cost. In resolving the scheduling problem from one time instant to the next, the Lagrange multipliers from the last schedule can be used to initialize the multipliers, further reducing the computation time. Although individual results for the identical machine problems have been reported in the literature, this paper provides a unified framework for developing scheduling methodologies for large scale, diverse, and interdependent systems. In addition, an improved methodology for the job shop problem is presented, the most difficult of the systems studied here. The step-by-step modeling, resolution, intuitive explanation and comments provide much insight into the nature of manufacturing scheduling problems. All algorithms are illustrated with examples using actual factory data. This paper demonstrates that optimization methodologies are not only practical for scheduling in manufacturing systems, but produce consistently high quality results as well.