Scheduling in a production environment with multiple process plans per job

Traditional job shop scheduling problems generally assume that there is a single feasible routing with which a part can be processed in a shop. In today's flexible production systems, this assumption is rarely true. For most manufactured parts, it is possible to generate multiple ways to sequence the operations required to realize the finished product. Each feasible ordering of the operations generates a process plan. Multiple process plans per job increase production flexibility, while at the same time they increase planning and scheduling difficulty. In this paper, the problem of scheduling multiple jobs with each having multiple process plans in a job shop environment is addressed. The problem is modelled and solved using a mathematical approach. Because of the high computational effort required to solve the model using an exact solution procedure, two algorithms were developed and compared against solutions obtained by an optimum finding technique. The results of the test problems indicate that one of the algorithms, referred to as the preprocessing algorithm, finds the optimal solution in all problem cases tested. The second algorithm, referred to as the iterative algorithm, is also effective in finding good solutions; however, its overall performance is lower than that of the first algorithm.