Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains |
| |
Authors: | George Steiner Rui Zhang |
| |
Affiliation: | 1. Operations Management Area, DeGroote School of Business, McMaster University, Hamilton, Ontario, Canada
|
| |
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 an 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|