The Journal of Information Systems (한국정보시스템학회지:정보시스템연구)

Korea Association of Information Systems (한국정보시스템학회)
권호 표지
DOI QR코드

DOI QR Code

Solving the Constrained Job Sequencing Problem using Candidate Order based Tabu Search

후보순위 기반 타부 서치를 이용한 제약 조건을 갖는 작업 순서결정 문제 풀이

  • 정성욱 (동아대학교 일반대학원 산업경영공학과) ;
  • 김준우 (동아대학교 산업경영공학과)
  • Received : 2015.11.27
  • Accepted : 2016.03.16
  • Published : 2016.03.31
Download PDF
⟨ Previous Next ⟩

Abstract

Purpose This paper aims to develop a novel tabu search algorithm for solving the sequencing problems with precedence constraints. Due to constraints, the traditional meta heuristic methods can generate infeasible solutions during search procedure, which must be carefully dealt with. On the contrary, the candidate order based tabu search (COTS) is based on a novel neighborhood structure that guarantees the feasibility of solutions, and can dealt with a wide range of sequencing problems in flexible manner. Design/methodology/approach Candidate order scheme is a strategy for constructing a feasible sequence by iteratively appending an item at a time, and it has been successfully applied to genetic algorithm. The primary benefit of the candidate order scheme is that it can effectively deal with the additional constraints of sequencing problems and always generates the feasible solutions. In this paper, the candidate order scheme is used to design the neighborhood structure, tabu list and diversification operation of tabu search. Findings The COTS has been applied to the single machine job sequencing problems, and we can see that COTS can find the good solutions whether additional constraints exist or not. Especially, the experiment results reveal that the COTS is a promising approach for solving the sequencing problems with precedence constraints. In addition, the operations of COTS are intuitive and easy to understand, and it is expected that this paper will provide useful insights into the sequencing problems to the practitioners.

Keywords

References

  1. 김여근, 윤복식, 이상복, "메타휴리스틱," 영지 문화사, 1997.
  2. Ahrned, I., and Fisher, W. W., "Due date assignment, job order release and sequencing interaction in job shop scheduling," Decision Sciences, Vol23, No.3, 1992, pp.633-647. https://doi.org/10.1111/j.1540-5915.1992.tb00409.x
  3. Baker, K., "Introduction to sequencing and scheduling," Wiley, 1974.
  4. Chakhlevitch, K., Cowling, P., "Hyperheuristics: recent developments", In: Adaptive and multilevel metaheuristics, Springer Berlin Heidelberg, 2008, pp.3-29.
  5. Colin R. R., "Improving the efficiency of tabu search for machine sequencing problems," Journal of the Operational Research Society, Vol.44, No.4, 1993, pp.375-382. https://doi.org/10.1057/jors.1993.67
  6. Cordreau, J. F., Laporte G., and Pasin, F., "Iterated tabu search for the car sequencing problem," European Journal of Operations Research, Vol.191, No.3, 2008, pp.945-956. https://doi.org/10.1016/j.ejor.2007.04.048
  7. Cordeau, J. F., and Maischberger, M., "A parallel iterated tabu search heuristic for vehicle routing problems," Computers and Operations Research, Vol.39, No.9, 2012, pp.2033-2050. https://doi.org/10.1016/j.cor.2011.09.021
  8. Gendreau, M., Hertz, A., and Laporte, G., "Tabu search heuristic for the vehicle routing problem," Management Science, Vol.40, No10, 1994, pp.1276-1290. https://doi.org/10.1287/mnsc.40.10.1276
  9. Gendreau, M., Laporte, G., and Semet, F., "A tabu search heuristic for the undirected selective traveling salesman problem," European Journal of Operations Research, Vol.106, No.2, 1998, pp.539-545. https://doi.org/10.1016/S0377-2217(97)00289-0
  10. Gao, J., Chen, R., and Deng, W., "An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem," International Journal of Production Research, Vol.51, No.3, 2013, pp.641-651. https://doi.org/10.1080/00207543.2011.644819
  11. Glover, F., "Tabu search: a tutorial," Interfaces, Vol.20, No.4, 1990, pp.74-94. https://doi.org/10.1287/inte.20.4.74
  12. Hertz, A., "Tabu search for large scale timetabling problems," European Journal of Operational Research, Vol.54, No.1, 1991, pp.39-47. https://doi.org/10.1016/0377-2217(91)90321-L
  13. Hopper, E. B. C. H., and Turton, B. C., "An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem", European Journal of Operational Research, Vol.129, No.1, 2001, pp.34-57.
  14. Johnson, L. A., and Montgomery, D. C., "Operations research in production planning, scheduling, and inventory control." Wiley, 1974.
  15. Kennedy, J., and Eberhaart, R., "Particle swarm optimization," In: Proceedings of IEEE International Conference on Neural Networks, Vol.4, 1995, pp.1942 -1948.
  16. Kim, J. W., "Developing a job shop scheduling system through integration of graphic user interface and genetic algorithm," Multimedia Tools and Applications, Vol.74, No.10, 2015, pp.3329-3343. https://doi.org/10.1007/s11042-014-1965-7
  17. Kim, J. W., "Candidate order based genetic algorithm (COGA) for constrained sequencing problems", International Journal of Industrial Engineering, 2016, forthcoming.
  18. Kirkpatrick, S., "Optimization by simulated annealing: quantitative studies," Journal of Statistical Physics, Vol.34, No.5-6, pp.975-986. https://doi.org/10.1007/BF01009452
  19. Koh, S. H. and Lim, D. J., "Single machine scheduling for minimizing earliness/ tardiness penalties," Journal of Korea Management Engineers Society, Vol.19, No.1 2014, pp.109-119.
  20. Kovalyov, M., Musial, J., Urbanski, A., and Wojciechowski, A., "Internet shopping optimization problem," International Journal of Applied Mathematics and Computer Science, Vol.20, No.2, 2010, pp.385-390. https://doi.org/10.2478/v10006-010-0028-0
  21. Kowalczyk, R., "Constraint consistent genetic algorithms," In: IEEE International Conference on Evolutionary Computation, 1997, pp.343-348.
  22. Laporte, G., "The vehicle routing problem: an overview of exact and approximate algorithms," European Journal of Operational Research, Vol.59, No.3, 1992, pp.345-358. https://doi.org/10.1016/0377-2217(92)90192-C
  23. Lenstra, J. K., "Local search in combinatorial optimization," Princeton University Press, 1997.
  24. Lu, Z., and Hao, J. K., "Adaptive tabu search for course timetabling," European Journal of Operations Research, Vol.200, No/1, 2010, pp.235-244. https://doi.org/10.1016/j.ejor.2008.12.007
  25. Lawler, E. L., "Sequencing jobs to minimize total weighted completion time subject to precedence constraints," Annals of Discrete Mathematics, Vol.2, 1978, pp.75-90. https://doi.org/10.1016/S0167-5060(08)70323-6
  26. Lee, K. S., and Geem, Z. W., "A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice," Computer Methods in Applied Mechanics and Engineering, Vol.194, No.36, pp.3902- 3933. https://doi.org/10.1016/j.cma.2004.09.007
  27. Lenstra, J. K., and Kan, A. R., "Complexity of scheduling under precedence constrains," In: International Conference on Knowledge based Intelligent Electronics Systems, Vol.2, 1978, pp.60-66.
  28. Lopez-Loces, M. C., Rege, K., Pecero, J. E., Bouvry, P., and Huacuja, H. J. F., "Trajectory metaheuristics for the internet shopping optimization problem," In: Design of Intelligent Systems Based on Fuzzy Logic, Neural Networks and Nature-Inspired Optimization. Springer International Publishing, 2015, pp.527-536.
  29. Meeran, S., and Morshed, M. S., "A hybrid genetic tabu search algorithm for solving job shop scheduling problems: a case study," Journal of Intelligent Manufacturing, Vol.23, No.4, 2012, pp.1063-1078. https://doi.org/10.1007/s10845-011-0520-x
  30. Misevicius, A., "Using iterated tabu search for the traveling salesman problem," Information Technology and Control, Vol.32, No.3, 2015, pp.29-40.
  31. Nowicki, E., and Smutnicki, C., "A fast tabu search algorithm for the permutation flow-shop problem," European Journal of Operational Research, Vol.91, No.1, 1996, pp.160-175. https://doi.org/10.1016/0377-2217(95)00037-2
  32. Pezzella, F., and Merelli, E., "A tabu search method guided by shifting bottleneck for the job shop scheduling problem," European Journal of Operational Research, Vol.120, No.2, 2000, pp.297-310. https://doi.org/10.1016/S0377-2217(99)00158-7
  33. Sule, D. R., "Industrial Scheduling," PWS publishing, 1997.
  34. Toth, P., and Vigo, D., "The granular tabu search and its application to the vehicle-routing problem," Informs Journal on Computing, Vol.15, No.4, 2003, pp.333-346. https://doi.org/10.1287/ijoc.15.4.333.24890

Cited by

  1. The Decoding Approaches of Genetic Algorithm for Job Shop Scheduling Problem vol.25, pp.4, 2016, https://doi.org/10.5859/KAIS.2016.25.4.105