Machine scheduling with deliveries to multiple customer locations

Chung Lun Li, George Vairaktarakis, Chung Yee Lee

Research output: Journal article publicationReview articleAcademic researchpeer-review

126 Citations (Scopus)


One important issue in production and logistics management is the coordination of activities between production and delivery. In this paper, we develop a single-machine scheduling model that incorporates routing decisions of a delivery vehicle which serves customers at different locations. The objective is to minimize the sum of job arrival times. The problem is NP-hard in the strong sense in general. We develop a polynomial time algorithm for the case when the number of customers is fixed. More efficient algorithms are developed for several special cases of the problem. In particular, an algorithm is developed for the single-customer case with a complexity lower than the existing ones.
Original languageEnglish
Pages (from-to)39-51
Number of pages13
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 1 Jul 2005


  • Computational complexity
  • Dynamic programming
  • Scheduling

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Machine scheduling with deliveries to multiple customer locations'. Together they form a unique fingerprint.

Cite this