Production scheduling with supply and delivery considerations to minimize the makespan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

36 Citations (Scopus)


In this paper we study a scheduling model that simultaneously considers production scheduling, material supply, and product delivery. One vehicle with limited loading capacity transports unprocessed jobs from the supplier's warehouse to the factory in a fixed travelling time. Another capacitated vehicle travels between the factory and the customer to deliver finished jobs to the customer. The objective is to minimize the arrival time of the last delivered job to the customer. We show that the problem is NP-hard in the strong sense, and propose an O(n) time heuristic with a tight performance bound of 2. We identify some polynomially solvable cases of the problem, and develop heuristics with better performance bounds for some special cases of the problem. Computational results show that all the heuristics are effective in producing optimal or near-optimal solutions quickly.
Original languageEnglish
Pages (from-to)743-752
Number of pages10
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 1 May 2009


  • Heuristics
  • Performance bounds
  • Scheduling
  • Supply and delivery

ASJC Scopus subject areas

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


Dive into the research topics of 'Production scheduling with supply and delivery considerations to minimize the makespan'. Together they form a unique fingerprint.

Cite this