Minimizing flowtime and missed due-dates in single-machine sequencing

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

Given a set of simultaneously available jobs, each assigned a due-date, to be processed on a single machine, the problem is to find an optimal order to process the jobs that minimizes a penalty function. Since the effectiveness of a schedule is primarily evaluated on the basis of its effects on the WIP inventory and order delivery performance, we employ a bicriterion penalty function defined as the weighted sum of the flowtime and earliness and tardiness values of each job. This sequencing problem is shown to be NP-complete, so it is doubtful that a polynomial bound solution algorithm exists. In this paper, a dynamic programming (DP) formulation of the problem is presented and the optimal job sequence is determined by implicit enumeration in accordance with the DP optimality principle.
Original languageEnglish
Pages (from-to)71-77
Number of pages7
JournalMathematical and Computer Modelling
Volume13
Issue number5
DOIs
Publication statusPublished - 1 Jan 1990
Externally publishedYes

ASJC Scopus subject areas

  • Modelling and Simulation
  • Computer Science Applications

Cite this