Integrated Process Planning and Scheduling for a Complex Job Shop Using a Proxy Based Local Search

TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Tech


Within manufacturing systems, process planning and scheduling are two interrelated problems that are often treated independently. Process planning involves deciding which operations are required to produce a finished product and which resources will perform each operation. Scheduling involves deciding the sequence that operations should be processed by each resource, where process planning decisions are known a priori. Integrating process planning and scheduling offers significant opportunities to reduce bottlenecks and improve plant performance, particularly for complex job shops.

This research is motivated by the coating and laminating (CandL) system of a film manufacturing facility, where more than 1,000 product types are regularly produced monthly. The CandL system can be described as a complex job shop with sequence dependent setups, operation re-entry, minimum and maximum wait time constraints, and a due date performance measure. In addition to the complex scheduling environment, products produced in the CandL system have multiple feasible process plans. The CandL system experiences significant issues with schedule generation and due date performance. Thus, an integrated process planning and scheduling approach is needed to address large scale industry problems.

In this research, a novel proxy measure based local search (PBLS) approach is proposed to address the integrated process planning and scheduling for a complex job shop. PBLS uses a proxy measure in conjunction with local search procedures to adjust process planning decisions with the goal of reducing total tardiness. A new dispatching heuristic, OU-MW, is developed to generate feasible schedules for complex job shop scheduling problems with maximum wait time constraints. A regression based proxy approach, PBLS-R, and a neural network based proxy approach, PBLS-NN, are investigated. In each case, descriptive statistics about the active process plan set are used as independent variables in the model. The resulting proxy measure is used to evaluate the effect of process planning local search moves on the objective function sum of total tardiness. Using the proxy measure to guide a local search reduces the number of times a detailed schedule is generated reducing overall runtime.

In summary, the proxy measure based local search approach involves the following stages:

• Generate a set of feasible schedules for a set of jobs in a complex job shop. • Evaluate the parameters and results of the schedules to establish a proxy measure that will estimate the effect of process planning decisions on objective function performance. • Apply local search methods to improve upon feasible schedules.

Both PBLS-R and PBLS-NN are integrated process planning and scheduling heuristics capable of addressing the challenges of the CandL problem. Both approaches show significant improvement in objective function performance when compared to local search guided by random walk. Finally, an optimal solution approach is applied to small data sets and the results are compared to those of PBLS-R and PBLS-NN. Although the proxy based local search approaches investigated do not guarantee optimality, they provide a significant improvement in computational time when compared to an optimal solution approach. The results suggest proxy based local search is an appealing approach for integrated process planning and scheduling in complex job shop environment where optimal solution approaches are not viable due to processing time.



scheduling, process planning, local search, job shop