A heuristic for common due-date assignment and job scheduling on parallel machines

Research output: Journal article publicationJournal articleAcademic researchpeer-review

51 Citations (Scopus)

Abstract

In this paper we consider the problem of scheduling a set of simultaneously available jobs on several parallel and identical machines. The problem is to find the optimal due-date, assuming this to be the same for all jobs. We also seek to sequence the jobs such that some are early and some are late so as to minimize a penalty function. For the single-machine problem, we present a simple proof of the well-known optimality result that the optimal due-date coincides with one of the job completion times. We show that the optimal job sequence for the single-machine problem can be easily determined. We prove that the same optimal due-date result can be generalized to the parallel-machine problem. However, determination of the optimal job sequence for such a problem is much more complex, and we present a simple heuristic to find an approximate solution. On the basis of a limited experiment, we observe that the heuristic is very effective in obtaining near-optimal solutions.
Original languageEnglish
Pages (from-to)1129-1135
Number of pages7
JournalJournal of the Operational Research Society
Volume40
Issue number12
DOIs
Publication statusPublished - 1 Jan 1989
Externally publishedYes

Keywords

  • Due-date assignment
  • Scheduling
  • Sequencing

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Cite this