TY - GEN
T1 - Integrated production and delivery scheduling with disjoint windows
AU - Huo, Yumei
AU - Leung, Joseph Y.T.
AU - Wang, Xin
PY - 2009
Y1 - 2009
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 times. At each delivery time, there is a time window that products can be produced to be delivered at that delivery time. Suppose we have a set of jobs with each job specifying its delivery time, processing time and profit. The company can earn the profit of the job 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 jobs that are not picked will be discarded without penalty. We consider both the single machine case and the parallel and identical machines case. In this article we consider two kinds of profits: (1) arbitrary profit, (2) 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(n3/ε). In the second case, we give a faster FPTAS for a single machine with running time O(n2/ε). 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 times. At each delivery time, there is a time window that products can be produced to be delivered at that delivery time. Suppose we have a set of jobs with each job specifying its delivery time, processing time and profit. The company can earn the profit of the job 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 jobs that are not picked will be discarded without penalty. We consider both the single machine case and the parallel and identical machines case. In this article we consider two kinds of profits: (1) arbitrary profit, (2) 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(n3/ε). In the second case, we give a faster FPTAS for a single machine with running time O(n2/ε). 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 strong NP-hard
KW - Parallel and identical machines
KW - Perishable goods
KW - Single machine
UR - http://www.scopus.com/inward/record.url?scp=70350629761&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350629761&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02026-1_45
DO - 10.1007/978-3-642-02026-1_45
M3 - Conference contribution
AN - SCOPUS:70350629761
SN - 3642020259
SN - 9783642020254
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 471
EP - 482
BT - Combinatorial Optimization and Applications - Third International Conference, COCOA 2009, Proceedings
T2 - 3rd International Conference on Combinatorial Optimization and Applications, COCOA 2009
Y2 - 10 June 2009 through 12 June 2009
ER -