Manufacture and Delivery Scheduling for Multiple Customers on a Single Machine with Availability Constraint

摘要

In this paper we consider a scheduling problem with the joint consideration of manufacture and delivery for multiple customers. Since the machine is not always available due to breakdown or maintenance during the manufacture period, the interrupted job is resumable after the machine becomes available again. In the delivery period, amounts of vehicles with fixed load capacities deliver completed jobs in batches to K customers. Only jobs belonging to the same customer can be delivered together in the same shipment. The cost of each delivery for different customer is different. Our goal is to minimize the sum of total departure time and total delivery cost. The problem is solved optimally by a dynamic programming algorithm with polynomial time O(n~(K+2)), where n is the number of jobs. The performance of an instance is shown the effectiveness of the algorithm.