Parallel machine scheduling with batch delivery costs

Guoqing Wang, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

79 Citations (Scopus)


We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on m parallel machines. The jobs are delivered in batches and the delivery date of a batch is equal to the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total flow time and delivery cost. We first show that the problem is NP-complete in the ordinary sense even when m = 2, and NP-complete in the strong sense when m is arbitrary. Then we develop a dynamic programming algorithm to solve the problem. The algorithm is pseudopolynomial when m is constant and the number of batches has a fixed upper bound. Finally, we identify two polynomially solvable cases by introducing their corresponding solution methods.
Original languageEnglish
Pages (from-to)177-183
Number of pages7
JournalInternational Journal of Production Economics
Issue number2
Publication statusPublished - 20 Nov 2000

ASJC Scopus subject areas

  • General Business,Management and Accounting
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Parallel machine scheduling with batch delivery costs'. Together they form a unique fingerprint.

Cite this