A heuristic algorithm for sequencing jobs of unequal importance to minimize total tardiness

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

The problem of determining a “good” sequence that minimizes total tardiness for a set of jobs with unequal importance on a single machine is addressed in this paper. The term unequal importance is interpreted here to mean that there is one job in the set of jobs which is not allowed to be tardy. To find an optimal solution for this kind of non-linear and NP- complete problem, it is necessary to rely on the concepts of combinatorial optimization. Commonly used methods include dynamic programming and branch and bound. These enumerative methods are computationally inefficient, and no easy method has yet been found. This paper applies the algorithm of Ref. [15] as the basis for developing a heuristic algorithm to obtain a sequence for a set of jobs. A comparative evaluation of the proposed algorithm with the dynamic programming method is provided in the later sections of this paper.

Original languageEnglish
Pages (from-to)83-88
Number of pages6
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume13
Issue number1
DOIs
Publication statusPublished - 1990 Jan 1

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'A heuristic algorithm for sequencing jobs of unequal importance to minimize total tardiness'. Together they form a unique fingerprint.

  • Cite this