Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains

Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains

0.00 Avg rating0 Votes
Article ID: iaor200971842
Country: United Kingdom
Volume: 12
Issue: 6
Start Page Number: 565
End Page Number: 574
Publication Date: Dec 2009
Journal: Journal of Scheduling
Authors: ,
Keywords: supply & supply chains
Abstract:

We study a supply chain scheduling problem in which n jobs have to be scheduled on a single machine and delivered to m customers in batches. Each job has a due date, a processing time and a lateness penalty (weight). To save batch-delivery costs, several jobs for the same customer can be delivered together in a batch, including late jobs. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time has to be added before processing the first job in each batch. The objective is to find a schedule which minimizes the sum of the weighted number of late jobs and the delivery costs. We present a pseudo-polynomial algorithm for a restricted case, where late jobs are delivered separately, and show that it becomes polynomial for the special cases when jobs have equal weights and equal delivery costs or equal processing times and equal setup times. We convert the algorithm into a fully polynomial-time approximation scheme (FPTAS) and prove that the solution produced by it is near-optimal for the original general problem by performing a parametric analysis of its performance ratio.

Reviews

Required fields are marked *. Your email address will not be published.