Heuristics for minimizing total weighted tardiness in flexible flow shops

✍ Scribed by Ya Yang; Stephan Kreipl; Michael Pinedo

• Publisher: Springer US
• Year: 2000
• Tongue: English
• Weight: 156 KB
• Volume: 3
• Category: Article
• ISSN: 1094-6136
• DOI: 10.1002/(sici)1099-1425(200003/04)3:2<89::aid-jos36>3.0.co;2-n

✦ Synopsis

Consider a #exible #ow shop with s stages in series and at each stage a number of identical machines in parallel. There are n jobs to be processed and each job has to go through the stages following the same route. Job j has release date r H , due date d H , weight w H and a processing time p HJ at stage l, l"1, 2 , s. The objective is to minimize the total weighted tardiness of the n jobs. In this paper we describe and analyse three heuristics. The "rst one is a decomposition algorithm that solves the problem by decomposing the #exible #ow shop problem into a series of single-stage scheduling subproblems. The second one is an algorithm based on local search. The third heuristic is a hybrid algorithm that combines the "rst two. We conclude with a comparative study of the three heuristics.