TY - JOUR

T1 - Integrated production and delivery scheduling with disjoint windows

AU - Huo, Yumei

AU - Leung, Joseph Y.T.

AU - Wang, Xin

N1 - Funding Information:
The authors would like to thank an anonymous referee for suggesting a faster approximation algorithm for the arbitrary profit case. The work of the first author is supported in part by the PSC-CUNY research fund. The work of the second author is supported in part by the NSF grant DMI-0556010.

PY - 2010/4/28

Y1 - 2010/4/28

N2 - Consider a company that manufactures perishable goods. The company relies on a third party to deliver goods, which picks up delivery products at regular or irregular times. At each delivery time, there is a time window that products can be produced to be delivered at that delivery time. The time windows are disjoint. Suppose we have a set of jobs with each job specifying its delivery time, processing time and profit. The company can earn the profit if the job is produced and delivered at its specified delivery time. From the company point of view, we are interested in picking a subset of jobs to produce and deliver so as to maximize the total profit. The unpicked jobs will be discarded without penalty. We consider both the single machine case and the parallel and identical machine case. In this article we consider three kinds of profits: (1) arbitrary profit, (2) equal profit, and (3) profit proportional to its processing time. In the first case, we give a fully polynomial time approximation scheme (FPTAS) for a single machine with running time O (frac(n3, ε{lunate})). Using the bound improvement technique of Kovalyov, the running time can be further reduced to O (frac(n2, ε{lunate}) + n2 log n). In the second case, we give an O (n log n)-time optimal algorithm for a single machine. In the third case, we give an FPTAS for a single machine with running time O (frac(n2, ε{lunate})). All of our algorithms can be extended to parallel and identical machines with a degradation of performance ratios.

AB - Consider a company that manufactures perishable goods. The company relies on a third party to deliver goods, which picks up delivery products at regular or irregular times. At each delivery time, there is a time window that products can be produced to be delivered at that delivery time. The time windows are disjoint. Suppose we have a set of jobs with each job specifying its delivery time, processing time and profit. The company can earn the profit if the job is produced and delivered at its specified delivery time. From the company point of view, we are interested in picking a subset of jobs to produce and deliver so as to maximize the total profit. The unpicked jobs will be discarded without penalty. We consider both the single machine case and the parallel and identical machine case. In this article we consider three kinds of profits: (1) arbitrary profit, (2) equal profit, and (3) profit proportional to its processing time. In the first case, we give a fully polynomial time approximation scheme (FPTAS) for a single machine with running time O (frac(n3, ε{lunate})). Using the bound improvement technique of Kovalyov, the running time can be further reduced to O (frac(n2, ε{lunate}) + n2 log n). In the second case, we give an O (n log n)-time optimal algorithm for a single machine. In the third case, we give an FPTAS for a single machine with running time O (frac(n2, ε{lunate})). All of our algorithms can be extended to parallel and identical machines with a degradation of performance ratios.

KW - Fully polynomial time approximation schemes

KW - NP-hard and strongly NP-hard

KW - Parallel and identical machines

KW - Perishable goods

KW - Single machine

UR - http://www.scopus.com/inward/record.url?scp=77949284301&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77949284301&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2009.12.010

DO - 10.1016/j.dam.2009.12.010

M3 - Article

AN - SCOPUS:77949284301

SN - 0166-218X

VL - 158

SP - 921

EP - 931

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 8

ER -