Coordinated scheduling of customer orders with decentralized machine locations

Abstract

We consider a scheduling model with two machines at different locations. Each job is composed of two tasks where each task must be processed by a specific machine. The finished tasks are shipped to a distribution center in batches before they are bundled together and delivered to customers. The objective is to minimize the sum of the delivery cost and customers' waiting costs. This model attempts to coordinate the production and delivery schedules on the decentralized machines while taking into consideration the shipping cost as well as the waiting time of the customers. We develop polynomial-time heuristic algorithms for this problem and analyze their worst-case performance. Computational experiments are conducted to test the effectiveness of the heuristics and to evaluate the benefits obtained by coordinating the production and delivery of the two decentralized machines.

Keywords:

• Scheduling
• deliveries
• coordination
• heuristics
• worst-case analysis

Acknowledgement

This research was supported in part by the Research Grants Council of Hong Kong under grant PolyU5222/06E.