首页 | 本学科首页   官方微博 | 高级检索  
     检索      

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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号