| AN IMPROVED BRANCH-AND-BOUND ALGORITHM TO MINIMIZE THE WEIGHTED FLOWTIME ON IDENTICAL PARALLEL MACHINES WITH FAMILY SETUP TIMES |
| |
| 作者姓名： | Belgacem BETTAYEB Imed KACEM Kondo H.ADJALLAH LOSI-ICD CNRS FRE Universitéde technologie de Troyes France |
| |
| 基金项目： | This work was supported in part by Regional Council of Champagne-Ardenne （France）.Acknowledgement The authors would like to thank the anonymous referees for their helpful suggestions that have improved the presentation of this paper. |
| |
| 摘 要： | This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.
|
| 关 键 词： | 并行机 调度安排 目标函数 分支跳跃算法 |
An improved branch-and-bound algorithm to minimize the weighted flowtime on identical parallel machines with family setup times |
| |
| Belgacem?Bettayeb,Imed?Kacem,Kondo?H.?Adjallah.AN IMPROVED BRANCH-AND-BOUND ALGORITHM TO MINIMIZE THE WEIGHTED FLOWTIME ON IDENTICAL PARALLEL MACHINES WITH FAMILY SETUP TIMES[J].Journal of Systems Science and Systems Engineering,2008,17(4):446-459. |
| |
| Authors: | Belgacem Bettayeb Imed Kacem Kondo H Adjallah |
| |
| Institution: | LOSI-ICD CNRS FRE 2848,Université de technologic de Troyes,France |
| |
| Abstract: | This article investigates identical parallel machines scheduling with family setup times.The objective function being the weighted sum of completion times,the problem is known to be strongly NP-hard.We propose a constructive heuristic algorithm and three complementary lower bounds.Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family,while the third one is based on a lagrangian relaxation.The bounds and the heuristic are incorporated into a branch-and-bound algorithm.Experimental results obtained outperform those of the methods presented in previous works,in term of size of solved problems. |
| |
| Keywords: | Scheduling heuristic lower bound branch-and-bound algorithm identical parallel machines family setup times |
| 本文献已被 维普 万方数据 SpringerLink 等数据库收录！ |
