Integrated production and delivery scheduling with disjoint windows

Yumei Huo, Joseph Y.T. Leung, Xin Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationCombinatorial Optimization and Applications - Third International Conference, COCOA 2009, Proceedings
Pages471-482
Number of pages12
DOIs
StatePublished - Nov 9 2009
Event3rd International Conference on Combinatorial Optimization and Applications, COCOA 2009 - Huangshan, China
Duration: Jun 10 2009Jun 12 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5573 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Conference on Combinatorial Optimization and Applications, COCOA 2009
CountryChina
CityHuangshan
Period6/10/096/12/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Fully polynomial time approximation schemes
  • NP-hard and strong NP-hard
  • Parallel and identical machines
  • Perishable goods
  • Single machine

Fingerprint Dive into the research topics of 'Integrated production and delivery scheduling with disjoint windows'. Together they form a unique fingerprint.

Cite this