An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

Ji Tian, Edwin Tai Chiu Cheng, Chi To Ng, Jinjiang Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)

Abstract

We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio 22-1≈1.828, which improves on a 2-competitive on-line algorithm for this problem in the literature.
Original languageEnglish
Pages (from-to)1191-1210
Number of pages20
JournalDiscrete Applied Mathematics
Volume160
Issue number7-8
DOIs
Publication statusPublished - 1 May 2012

Keywords

  • Competitive ratio
  • Delivery times
  • On-line scheduling
  • Parallel-batch machine

ASJC Scopus subject areas

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics

Cite this