[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.
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.