Premium
A total tardiness problem with preprocessing included
Author(s) -
Koulamas Christos
Publication year - 1996
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199608)43:5<721::aid-nav8>3.0.co;2-7
Subject(s) - tardiness , preprocessor , computer science , mathematical optimization , due date , heuristic , a priori and a posteriori , retard , algorithm , scheduling (production processes) , job shop scheduling , mathematics , artificial intelligence , psychology , philosophy , schedule , epistemology , psychiatry , queue , programming language , operating system
A special case of the two‐machine flow‐shop total tardiness problem is defined by assuming that the first machine is dedicated to preprocessing and that the second machine performs the main operation, which is longer than preprocessing for each job. It is also assumed that customer orders (jobs) contain varying numbers of otherwise similar parts; therefore orders with longer main processing times have longer preprocessing times as well. The new problem ( F 2/ppc/ T ) is solved by exploiting its structure and its relationship to the single‐machine (1// T ) and the two‐machine flow‐shop ( F2//T¯ ) total tardiness problems. It is shown that shortest‐processing‐time ordering minimizes the average job completion time in the F 2/ppc/ T setting. This result leads to the development of dominance conditions to determine a priori the order of some jobs in an optimal F 2/ppc/ T sequence. These dominance conditions are then embedded in a branch‐and‐bound algorithm, which is shown to be computationally efficient. A polynomial‐time heuristic is also developed for F 2/ppc/ T . It is concluded that the additional structure of F 2/ppc/ T (compared to the general F 2// T problem) results in highly efficient solution algorithms for it. © 1996 John Wiley & Sons, Inc.