A Lagrangian relaxation approach to scheduling in manufacturing systems

Scheduling is one of the most important issues in the planning and operation of manufacturing systems, but the generation of consistently good schedules has proven to be extremely difficult. The problem is that optimal scheduling solutions involve costly and impractical enumeration procedures, while the performance of most heuristic techniques is difficult to estimate and may vary considerably from one problem to the next. This Thesis considers the solution of four categories of machine scheduling problems. These problems range in difficulty from scheduling singleoperation jobs on parallel machines to the job shop problem, wherein multi-operation jobs are scheduled on nonidentical machines. For all the problems, jobs have due dates, different levels of importance (or weights), and various processing times on the machines. The objective is to minimize the total weighted job tardiness or the weighted quadratic tardiness of the schedule. Since machine scheduling problems are generally NP-hard, our goal is not to obtain the optimal schedule. Rather, we present efficient, decentralized, near-optimal algorithms based on Lagrangian relaxation. A nice feature of this approach is that it provides a lower bound on the cost, which can be used as a measure of the suboptimality of the generated schedule. Furthermore, the method provides valuable job and machine interaction information, which shop floor management uses to answer "what if' questions, to reconfigure the schedule to accommodate dynamic changes, as well as to schedule new jobs. All algorithms are designed to facilitate distributed implementation, and have been tested in an actual manufacturing environment.
The first problem to be considered involves scheduling independent, singleoperation jobs with due dates on identical, parallel machines. Multi-operation jobs subject to simple precedence constraints are to be scheduled on parallel machines in the second problem. The third problem concerns nonidentical machines, where each job consists of a small number of operations. The general job shop with simple routing considerations is the subject of the last problem. These problems are formulated as deterministic integer programming problems. When Lagrangian relaxation is applied, a set of decentralized problems results, which are easier to solve. Once the dual problem is solved, the resulting schedule is generally infeasible. A list processing algorithm, combined with a greedy method based upon the objective function used, is then employed to generate a feasible schedule. Numerical examples illustrate that the feasible schedule costs are generally within a few percent of their respective lower bounds, and are obtained within reasonable CPU times.