Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost

Hua Gong, Lixin Tang, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Motivated by the flow of products in the iron and steel industry, we study an identical and parallel machine scheduling problem with batch deliveries, where jobs finished on the parallel machines are delivered to customers in batches. Each delivery batch has a capacity and incurs a cost. The objective is to find a coordinated production and delivery schedule that minimizes the total flow time of jobs plus the total delivery cost. This problem is an extension of the problem considered by Hall and Potts, Ann Oper Res 135 (2005) 41–64, who studied a two-machine problem with an unbounded number of transporters and unbounded delivery capacity. We first provide a dynamic programming algorithm to solve a special case with a given job assignment to the machines. A heuristic algorithm is then presented for the general problem, and its worst-case performance ratio is analyzed. The computational results show that the heuristic algorithm can generate near-optimal solutions. Finally, we offer a fully polynomial-time approximation scheme for a fixed number of machines.

Original languageEnglish (US)
Pages (from-to)492-502
Number of pages11
JournalNaval Research Logistics
Issue number6
StatePublished - Sep 1 2016

All Science Journal Classification (ASJC) codes

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


  • batch delivery
  • dynamic programming
  • parallel machines
  • worst-case performance


Dive into the research topics of 'Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost'. Together they form a unique fingerprint.

Cite this