Two heads are better than one: an AIS- and TS-based hybrid strategy for job shop scheduling problems
详细信息 查看全文
- 作者：Xingquan Zuo (1) zuoxq@bupt.edu.cn
Chunlu Wang (1)
Wei Tan (2) - 关键词：Job shop scheduling – ; Artificial immune systems – ; Tabu search – ; Hybrid scheduling algorithms
- 刊名：The International Journal of Advanced Manufacturing Technology
- 出版年：2012
- 出版时间：November 2012
- 年：2012
- 卷：63
- 期：1-4
- 页码：155-168
- 全文大小：318.0 KB
- 参考文献：1. Lenstra JK, Kan AHGR (1979) Computational complexity of discrete optimization problems. Ann Discrete Math 4:121–140
2. Lopez P, Roubellat F (2008) Production scheduling. Wiley, Hoboken
3. Mazdeh MM, Sarhadi M, Hindi KS (2008) A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times. Comput Oper Res 35(4):1099–1111
4. Allahverdi A, Al-Anzi FS (2006) A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times. Eur J Oper Res 169(3):767–780
5. Tuong NH, Soukhal A, Billaut JC (2010) A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines. Eur J Oper Res 202(3):646–653
6. Tang L, Xuan H, Liu J (2007) Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling. Comput Oper Res 34(9):2625–2636
7. Buddhakulsomsiri J, Kim DS (2007) Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. Eur J Oper Res 178(2):374–390
8. Chtourou H, Haouari M (2008) A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling. Comput Ind Eng 55(1):183–194
9. Goldberg DE (1989) Genetic algorithm in search, optimization and machine learning. Addison-Wesley, MA
10. Liu TK, Tsai JT, Chou JH (2005) Improved genetic algorithm for the job-shop scheduling problem. Int J Adv Manuf Technol 27(9–10):1021–1029
11. Van Laarboven PJM, Aarts EHL, Lenstra JK (1992) Job shop scheduling by simulated annealing. Oper Res 40:113–125
12. Low C, Yeh JY, Huang KI (2004) A robust simulated annealing heuristic for flow shop scheduling problems. Int J Adv Manuf Technol 23(9–10):762–767
13. Taillard ED (1994) Parallel taboo search techniques for the job shop scheduling problem. ORSA J Comput 6:108–117
14. Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manag Sci 42(6):797–813
15. Agarwal A, Colak S, Jacob VS, Pirkul H (2006) Heuristics and augmented neural networks for task scheduling with non-identical machines. Eur J Oper Res 175:296–317
16. Yagmahan B, Yenisey MM (2008) Ant colony optimization for multi-objective flow shop scheduling problem. Comput Ind Eng 54:411–420
17. Udhayakumar P, Kumanan S (2010) Sequencing and scheduling of job and tool in a flexible manufacturing system using ant colony optimization algorithm. Int J Adv Manuf Technol 50(9–12):1075–1084
18. Li BB, Wang L, Liu B (2008) An effective PSO-based hybrid algorithm for multi-objective permutation flow shop scheduling. IEEE Trans Syst Man Cybern Syst Hum 38(4):818–831
19. Ge HW, Sun L, Liang YC, Qian F (2008) An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling. IEEE Trans Syst Man Cybern Syst Hum 38(2):358–368
20. Wang L, Zheng DZ (2001) An effective hybrid optimization strategy for job-shop scheduling problems. Comput Oper Res 28:585–596
21. Ombuki BM, Ventresca M (2004) Local search genetic algorithms for the job shop scheduling problem. Appl Intell 21(1):99–109
22. Goncalves JF, Mendes JJDM, Resende MGC (2005) A hybrid genetic algorithm for the job shop scheduling problem. Eur J Oper Res 167(1):77–95
23. Tavakkoli-Moghaddam R, Safaei N, Sassani F (2009) A memetic algorithm for the flexible flow line scheduling problem with processor blocking. Comput Oper Res 36:402–414
24. Caumond A, Lacomme P, Tchernev N (2008) A memetic algorithm for the job-shop with time-lags. Comput Oper Res 35:2331–2356
25. Rego C, Duarte R (2009) A filter-and-fan approach to the job shop scheduling problem. Eur J Oper Res 194:650–662
26. De Castro JN, Timmis J (2002) Artificial immune systems: a new computational intelligence approach. Springer, Heidelberg
27. Mo HW, Zuo XQ (2009) Artificial immune systems. Science Press, Beijing
28. Coello Coello AC, Rivera DC, Cortes NC (2003) Use of an artificial immune system for job shop scheduling. In: The 2nd International Conference on Artificial Immune System, Edinburgh, UK, pp 1–10
29. Luh GC, Chueh CH (2009) A multi-modal immune algorithm for the job-shop scheduling problem. Inform Sci 179:1516–1532
30. Chandrasekaran M, Asokan P, Kumanan S, Balamurugan T, Nickolas S (2006) Solving job shop scheduling problems using artificial immune system. Int J Adv Manuf Tech 31:580–593
31. Xu X, Li C (2007) Research on immune genetic algorithm for solving the job-shop scheduling problem. Int J Adv Manuf Tech 34:783–789
32. Zuo XQ, Mo HW, Wu JP (2009) A robust scheduling method based on multi-objective immune algorithm. Inform Sci 179(19):3359–3369
33. Dell'Amico M, Trubian M (1993) Applying tabu-search to the job-shop scheduling problem. Ann Oper Res 4:231–252
34. Balas E (1969) Machine sequencing via disjunctive graph: an implicit enumeration algorithm. Oper Res 17:941–957
35. Liaw CF (2000) A hybrid genetic algorithm for the open shop scheduling problem. Eur J Oper Res 124:28–42
36. Zuo XQ, Fan YS (2006) A chaos search immune algorithm with its application to neuro-fuzzy controller design. Chaos, Solitons and Fractals 30:94–109
37. Lawrence S (1984) Supplement to resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques. Dissertation, Carnegie-Mellon University, Pittsburgh, USA
38. Fisher H, Thompson GL (1963) Probabilistic learning combinations of local job shop scheduling rules. In: Muth JF, Thompson GL (eds) Industrial scheduling. Prentice Hall, Englewood Cliffs, pp 225–251
39. Binato S, Hery WJ, Loewenstern DM, Resende MGC (2002) A GRASP for job shop scheduling. In: Ribeiro CC, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer, Norwell
40. Aiex RM, Binato S, Resende MGC (2003) Parallel GRASP with path-relinking for job shop scheduling. Parallel Comput 29:393–430
41. Sabuncuoglu I, Bayiz M (1999) Job shop scheduling with beam search. Eur J Oper Res 118:390–412
42. Mejtsky GJ (2008) The improved sweep metaheuristic for simulation optimization and application to job shop scheduling. In: The Winter Simulation Conference, Miami, Florida, USA, pp 731–739 - 作者单位：1. Computer School, Beijing University of Posts and Telecommunications, Beijing, People鈥檚 Republic of China2. IBM T. J. Watson Research Center, Hawthorne, NY, USA
- ISSN：1433-3015
文摘
Job shop problems (JSPs) widely exist in many fields and are usually very hard to solve. Despite the fact that many scheduling algorithms have been studied, it is still challenging to find optimal solutions for certain JSPs. Some studies have shown that it is difficult to solve these JSPs by only using a single search technique, while the hybrid of different ones is usually more effective. In this paper, a hybrid algorithm combining artificial immune system (AIS) with tabu search (TS) is proposed. The AIS is based on the clonal selection principle of biological immune systems and is used to find the solution space with potential high evaluation values. The TS is used to exploit the local solution space to further improve the quality of a solution. The neighborhood of the TS is based on a disjunctive graph model, and a smaller neighborhood structure is adopted to reduce the computational cost of the neighborhood search. To reduce the solution space of JSPs and balance convergence speed and solution quality, scheduling solutions are restricted in the set of parameterized active schedules, i.e., a subset of active schedules. Forty-three benchmark instances are used to evaluate the proposed hybrid algorithm, and experimental results are compared with those of other algorithms. Results show that the hybrid algorithm is very effective for JSPs.