A bicriteria two-machine permutation flowshop problem

✍ Scribed by Funda Sivrikaya-Şerifoğlu; Gündüz Ulusoy

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 263 KB
• Volume: 107
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(97)00338-x

✦ Synopsis

The problem attacked in this paper is the scheduling of n jobs on two machines which are assumed to be continuously available. All jobs are available at the beginning of the scheduling period. Setup times are included in the processing times. No preemption of jobs is allowed. The objective is the minimization of a weighted combination of the average job ¯owtime and the schedule makespan. Three branch and bound (B&B) approaches are compared which differ mainly in their branching strategies. One of them is the conventional B&B approach called the forward approach, and the other two are referred to as the backward and the double-sided approaches, respectively. To obtain an upper bound, a ¯owshop heuristic (FSH1) is employed and is subjected to 2-opt and 3-opt. Lower bounds for each approach are developed. In each case, the lower bound is taken as the weighted sum of the lower bounds for the average ¯owtime and for the makespan. A computational study is performed to evaluate the three dierent B&B approaches on a testbed consisting of 30 problems each for n 10, n 14, and n 18; and each one of these problems is solved for ®ve dierent levels of the weighting factor. An analysis into the resulting ecient points is also included. An improved version of FSH1 (called FSH2) is developed and both heuristics are subjected to extensive numerical experimentation.