Single batch machine scheduling with deliveries

B. Y. Cheng, J. Y.T. Leung, K. Li, S. L. Yang

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time pj and a size sj. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where r ≥ 2 and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in O (n log n) time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in O (n log n) time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in O (n log n) time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst-case ratios in both cases.

Original languageEnglish (US)
Pages (from-to)470-482
Number of pages13
JournalNaval Research Logistics
Volume62
Issue number6
DOIs
StatePublished - Sep 2015

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Keywords

  • NP-hard
  • approximation algorithms
  • batch machine
  • delivery
  • polynomial time algorithms
  • scheduling

Fingerprint

Dive into the research topics of 'Single batch machine scheduling with deliveries'. Together they form a unique fingerprint.

Cite this