Job shop scheduling with alternative process plans

Successful implementation of automated manufacturing systems highly depends on effective utilization of resources. Efficient scheduling algorithms for alternative process plans may increase the throughput rate and guarantee a reasonable return on investment. This paper investigates an optimization methodology for scheduling jobs in a just-in-time environment. We consider the non-preemptive case where each job consists of a distinct number of operations to be processed in a specified order. Each operation has to be processed on one of a set of resources (e.g. machines) with possibly different efficiency and hence processing time. The objective is to minimize the sum of the weighted quadratic tardiness of the jobs. We obtain a fast near-optimal algorithm with guaranteed bounds for the distance to the optimum by using Lagrangian relaxation and show that just one relaxation suffices.