본문 바로가기
KERD
논문KCI 등재

이종 병렬설비 공정의 납기지연시간 최소화를 위한 유전 알고리즘

A Genetic Algorithm for Minimizing Total Tardiness with Non-identical Parallel Machines

0

조회

0

다운로드

2

인용

0

참고문헌

키워드

주제분류산업공학

초록

This paper considers a parallel-machine scheduling problem with dedicated and common processing machines using GA (Genetic Algorithm). Non-identical setup times, processing times and order lot size are assumed for each machine. The GA is proposed to minimize the total-tardiness objective measure. In this paper, heuristic algorithms including EDD (Earliest Due-Date), SPT (Shortest Processing Time) and LPT (Longest Processing Time) are compared with GA. The effectiveness and suitability of the GA are derived and tested through computational experiments.

Abstract

This paper considers a parallel-machine scheduling problem with dedicated and common processing machines using GA (Genetic Algorithm). Non-identical setup times, processing times and order lot size are assumed for each machine. The GA is proposed to minimize the total-tardiness objective measure. In this paper, heuristic algorithms including EDD (Earliest Due-Date), SPT (Shortest Processing Time) and LPT (Longest Processing Time) are compared with GA. The effectiveness and suitability of the GA are derived and tested through computational experiments.

참고문헌 (25)

  1. Baker, K.R., "Introduction to sequencing and scheduling, Vol. 31" (1974), Wiley
  2. Balin, S., "Non-identical parallel machine scheduling using genetic algorithm", Expert Systems with Applications, 38(6), pp.6814~6821 (2011)
  3. Bilge, U., "A tabu search algorithm for parallel machine total tardiness problem", Computers and Operations Research, 31(3), pp.397~414 (2004)
  4. Cheng, T.C.E., "A state-of-the-art review of parallel-machine scheduling research", European Journal of Operational Research, 47(3), pp.271~292 (1990)
  5. 최유준, "이종 병렬설비 공정의 작업완료시간 최소화를 위한 유전 알고리즘", 경영과학, 30(3), pp.81~97 (2013), 한국경영과학회[DOI]
  6. 최유준, "병렬설비를 가지는 열처리공정에서의 배치일정계획 수립 연구", 한국생산관리학회지, 22(4), pp.451~467 (2011), 한국생산관리학회
  7. The batch loading and scheduling problem, "Dobson, G.", Simon Graduate School of Business Administration, University of Rochester, ~ (1992)
  8. Du, J., "Minimizing total tardiness on one machine is NP-hard", Mathematics of operations research, 15(3), pp.483~495 (1990)
  9. Garey, M.R., "Computer and intractability : A guide to the theory of NP-completeness" (1979), W. H. Freeman
  10. Hall, N. G., "Single-and multiple-processor models for minimizing completion time variance", Naval Research Logistics Quarterly, 33(1), pp.49~54 (1986)
  11. Jeon, T.J., "A Proof of Transitivity of Job-Pair Comparison Rule to Minimize Total Tardiness in a Single Machine", Korean Management Science Review, 18(1), pp.147~153 (2001)
  12. Kanet, J. J., "Minimizing the average deviation of job completion times about a common due date", Naval Research Logistics Quarterly, 28(4), pp.643~651 (1981)
  13. Lawler, E. L., "A pseudo-polynomial algorithm for sequencing jobs to minimize total tardiness", Annals of Discrete Mathematics, 1, pp.331~342 (1997)
  14. Lee, Y.H., "Scheduling jobs on parallel machines with sequence-dependent setup times", European Journal of Operational Research, 100(3), pp.464~474 (1997)
  15. Lenstra, J.K., "Complexity of scheduling under precedence constraints", Operations Research, 26, pp.22~35 (1978)
  16. Lenstra, J. K., "Complexity of machine scheduling problems", Ann. Discrete Math, 1, pp.343~362 (1977)
  17. Leung, J.Y.T., "Minimizing total tardiness on a single machine with precedence constraints", ORSA Journal on Computing, 2(4), pp.346~352 (1990)
  18. Logendran, R., "Scheduling unrelated parallel machines with sequence-dependent setups", Computers and Operations Research, 34(11), pp.3420~3438 (2007)
  19. Min, L., "A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines", Artificial Intelligence in Engineering, 13, pp.399~403 (1999)
  20. Monma, C.L., "On the complexity of scheduling with batch setup time", Operations Research, 37(5), pp.798~804 (1989)
  21. Park, M. W., "A Genetic Algorithm for the Parallel-Machine Total Weighted Tardiness Problem", Journal of the Korean Institute of Industrial Engineers, 26(2), pp.183~192 (2000)
  22. Piersma, N., "A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search", Mathematical and Computer Modelling, 24(9), pp.11~19 (1996)
  23. Rinnooy, Kan A. H. G, "Machine scheduling problems :Classification, complexity and computations" (1976), Martinus Nijhoff
  24. Schutten, J.M.J., "Parallel machine scheduling with release dates, due dates and family setup times", International Journal of Production Economics, 46, pp.119~125 (1996)
  25. Wilkerson, L.J., "An improved method for scheduling independent tasks", AIIE Transactions, 3(3), pp.239~245 (1971)

관련 논문AI추천

이 간행물의 다른 논문 (21건)