Scheduling two-stage production lines with multiple machines

Abstract

Most manufacturing process maintain separate fabrication and assembly centres. Based on this observation, the author coincides a manufacturing process that contains two stages of production with multiple machines. The manufacturer produces a variety of products to satisfy customer demands, operates under a 'push' mode and in a ‘ make-to-order’ environment. Each customer order consists of known quantities of different products which must be delivered as a whole shipment. Periodically, the manufacturer schedules all the accumulated unscheduled customer orders. The scheduling objective is to minimize the sum of weighted customer order lead times. Such manufacturing systems are formulated as a mathematical programming problem. It is then shown that this problem is unary NP-hard and remains unary NP-hard even when all the weights are equal. Some insights about the structure of the optimal schedule(s) are provided and some special cases solved in polynomial time. Several polynomial time heuristics are proposed, and worst-case analysis of some of the heuristics are provided. Tight lower bounds are developed in order to measure the performance of the proposed heuristics. Numerical examples are presented and possible extensions are discussed.

Keywords:

• scheduling
• NP-hard
• lead time
• heuristics