[1] Zhu Xia, Li Xiaoping, Wang Qian,. Objective increment based metaheuristicfor total flowtime minimization in no-wait flowshops [J]. Journal of Southeast University (English Edition), 2008, 24 (2): 168-173. [doi:10.3969/j.issn.1003-7985.2008.02.009]
Copy
Objective increment based metaheuristicfor total flowtime minimization in no-wait flowshops(
)
基于目标增量的最小化总完工时间无等待流水调度智能算法
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 24
- Issue:
- 2008 2
- Page:
- 168-173
- Research Field:
- Automation
- Publishing date:
- 2008-06-03
Info
- Title:
- Objective increment based metaheuristicfor total flowtime minimization in no-wait flowshops
- 基于目标增量的最小化总完工时间无等待流水调度智能算法
- Author(s):
- Zhu Xia, Li Xiaoping, Wang Qian
- School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
- PACS:
- TP278
- DOI:
- 10.3969/j.issn.1003-7985.2008.02.009
- Abstract:
- To solve the NP-complete no-wait flowshop problems, objective increment properties are analyzed and proved for fundamental operations of heuristics.With these properties, whether a new generated schedule is better or worse than the original one is only evaluated by objective increments, instead of completely calculating objective values as the traditional algorithms do, so that the computational time can be considerably reduced.An objective increment-based hybrid genetic algorithm(IGA)is proposed by integrating the genetic algorithm(GA)with an improved various neighborhood search(VNS)as a local search.An initial solution generation heuristic(ISG)is constructed to generate one individual of the initial population.An expectation value-based selection mechanism and a crossover operator are introduced to the mating process.The IGA is compared with the traditional GA and two best-so-far algorithms for the considered problem on 110 benchmark instances.An experimental results show that the IGA outperforms the others in effectiveness although with a little more time consumption.
- 针对NP-完全的无等待流水作业调度问题, 改变传统求解调度序列目标函数的模式, 分析并证明启发式算法基本算子的目标增量性质, 通过目标函数变化量判断新解的优劣, 大大降低算法所需计算时间.提出将变化邻域搜索(VNS)作为一种局部搜索机制混合入遗传算法的智能算法IGA求解所考虑的问题, 根据问题特点构造ISG算法产生初始种群中的一个个体, 设计基于期望值的个体选择机制和进化过程交叉算子ILCS.采用110个经典Benchmark实例, 将所提出的IGA算法与传统遗传算法以及求解该问题目前最好的2种算法进行比较, 实验结果表明IGA算法在略有耗时的情况下, 性能上明显优于其他3种算法.
References:
[1] Pinedo M.Scheduling:theory, algorithm, and systems [M].Englewood Chills, NJ:Prentice-Hall, 1995.
[2] Hall N G, Sriskandarajah C.A survey of machine scheduling problems with blocking and no-wait in process [J].Operations Research, 1996, 44(3):510-525.
[3] Rajendran C.A no-wait flowshop scheduling heuristic to minimize makespan[J].Journal of the Operational Research Society, 1994, 45(4):472-478.
[4] Wang L, Zheng D Z.An effective hybrid optimization strategy for job-shop scheduling problem [J].Computer and Operation Research, 2001, 28(6):585-596.
[5] MacCarthy B L, Liu J.Addressing the gap in scheduling research:a review of optimization and heuristic methods in production scheduling [J].International Journal of Production Research, 1993, 31(1):59-79.
[6] van Deman J M, Baker K R.Minimizing mean flow time in the flowshop with no intermediate queues [J].AIIE Transactions, 1974, 6(1):28-34.
[7] Adiri I, Pohoryles D.Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times [J].Navel Research Logistics Quarterly, 1982, 29(3):495-504.
[8] van der Veen J A A, van Dal R.Solvable cases of the no-wait flowshop scheduling problem [J].Journal of the Operational Research Society, 1991, 42(11):971-980.
[9] Rajendran C, Chaudhuri D.Heuristic algorithms for continuous flow-shop problem [J].Naval Research Logistics, 1990, 37(5):695-705.
[10] Bonney M C, Gundry S W.Solutions to the constrained flow-shop sequencing problem [J].Operational Research Quart, 1976, 27(4):869-883.
[11] King J R, Spachis A S.Heuristics for flow-shop scheduling [J].International Journal of Production Research, 1980, 18(3):343-357.
[12] Bertolissi Edy.Heuristic algorithm for scheduling in the no-wait flow-shop [J].Journal of Materials Processing Technology, 2000, 107(1/2/3):459-465.
[13] Bertolissi Edy.A simple no-wait flow-shop scheduling heuristic for the no-wait flowshop problem[C]//Proceedings of the 15th International Conference on Computer-Aided Production Engineering, CAPE’99.Durham, UK, 1999.
[14] Chen C L, Neppalli R V, Aljaber N.Generic algorithms applied to the continuous flow shop problem [J].Computers and Industrial Engineering, 1996, 30(4):919-929.
[15] Fink A, Voβ S.Solving the continuous flow-shop scheduling heuristic to minimize makespan[J].Journal of the Operational Research, 2003, 151(3):400-414.
[16] Taillard E.Benchmarks for basic scheduling problems [J].European Journal of Operational Research, 1993, 64(2):278-285.
[17] Aldowaisan T, Allahverdi A.New heuristics for m-machine no-wait flowshop to minimize total completion time [J].OMEGA, 2004, 32(5):345-352.
[18] Ruiz Rubén, Maroto Concepción, Alcaraz Javier.Two new robust algorithms for the flowshop scheduling problem [J].OMEGA, 2006, 34(5):461-476.
[19] Iyer Srikanth K, Saxena Barkha.Improved genetic algorithm for the permutation flowshop scheduling problem [J].Computers and Operations Research, 2004, 31(4):593-606.
[20] Blum Christian, Andrea Roli.Metaheuristics in combinatorial optimization:overview and conceptual comparison [J].ACM Computing Surveys, 2003, 35(3):268-308.
[21] Li Xiaoping.Heuristic for no-wait flow shops with makespan minimization [J].International Journal of Production Research, 2008, 46(9):2519-2530.
[22] Rajendran C, Ziegler H.An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs [J].European Journal of Operational Research, 1997, 103(1):129-138.
[23] Abramson N.Information theory and coding [M].New York:McGraw-Hill, 1963:129.
Memo
- Memo:
-
Biographies: Zhu Xia(1982—), female, graduate;Wang Qian(corresponding author), female, doctor, professor, qianwang6491@263.net.
Foundation items: The National Natural Science Foundation of China(No.60504029, 60672092), the National High Technology Research and Development Program of China(863 Program)(No.2008AA04Z103).
Citation: Zhu Xia, Li Xiaoping, Wang Qian.Objective increment based metaheuristic for total flowtime minimization in no-wait flowshops[J].Journal of Southeast University(English Edition), 2008, 24(2):168-173.