《1998 Minimizing tardy jobs in a two-stage hybrid flowshop》.pdf

int j prod res vol no . . . ., 1998, . 36, . 9, 2397± 2417 Minimizing tardy jobs in a two-stage hybrid ¯ owshop J. N. D. GUPTA² * and E. A. TUNC² We consider the two-stage hybrid ¯ owshop problem with the objective of mini- mizing the total number of tardy jobs. Since this problem is strongly NP-hard, several heuristic algorithms are developed to ® nd optimal or near optimal sche- dule for the case when the ® rst stage contains only one machine and the second stage contains m identical parallel machines. Results of computational tests in solving problems up to 100 jobs are reported and directions for future research are provided. 2 1 0 2 y r a u r 1. Introduction b e F Consider the following scenario: a set of jobs N = 1 . . . n is to be processed on { , , } 7 two stages where each job has to be processed ® rst on stage 1 and then on stage 2. 0 7 There is only one machine at stage 1 while stage 2 consists of m identical parallel 5 : 1 machines. Associated with each job i Î N, are processing times ai and bi at ® rst and 2 t a second stage respectively and a due date d . If job i is completed after its due date, it i ] y ( ( ) ( ) ( )) is called tardy, otherwise it is considered early. Let p = p 1 p 2 . . . p n be a e