[논문]지연 스케쥴을 허용하는 납기최소화 잡샵 스케쥴링 알고리즘

김재곤; 방준영

doi:10.11627/jkise.2019.42.1.033

지연 스케쥴을 허용하는 납기최소화 잡샵 스케쥴링 알고리즘
Dispatching Rule based Job-Shop Scheduling Algorithm with Delay Schedule for Minimizing Total Tardiness 원문보기

Journal of Korean Society of Industrial and Systems Engineering = 한국산업경영시스템학회지, v.42 no.1, 2019년, pp.33 - 40

김재곤 (인천대학교 산업경영공학과) , 방준영 (성결대학교 산업경영공학부)

Abstract ▼ AI-Helper

This study focuses on a job-shop scheduling problem with the objective of minimizing total tardiness for the job orders that have different due dates and different process flows. We suggest the dispatching rule based scheduling algorithm to generate fast and efficient schedule. First, we show the delay schedule can be optimal for total tardiness measure in some cases. Based on this observation, we expand search space for selecting the job operation to explore the delay schedules. That means, not only all job operations waiting for process but also job operations not arrived at the machine yet are considered to be scheduled when a machine is available and it is need decision for the next operation to be processed. Assuming each job operation is assigned to the available machine, the expected total tardiness is estimated, and the job operation with the minimum expected total tardiness is selected to be processed in the machine. If this job is being processed in the other machine, then machine should wait until the job arrives at the machine. Simulation experiments are carried out to test the suggested algorithm and compare with the results of other well-known dispatching rules such as EDD, ATC and COVERT, etc. Results show that the proposed algorithm, MET, works better in terms of total tardiness of orders than existing rules without increasing the number of tardy jobs.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 연구는 총지연도를 최소화하는 잡샵(job shop) 일정계획 문제를 다룬다. 본 문제에 대하여 총지연도를 추정하여 총 지연도를 최소화할 수 있도록 하는 디스패칭 기반의 휴리스틱 알고리즘을 제안하였다.
본 연구에서는 일반적인 잡샵 일정계획 문제에 대하여 총지연도를 최소화하기 위하여 디스패칭 방식의 작업 할당 알고리즘을 제안하였다. 본 연구에서 제안하는 알고리즘은 설비가 작업을 마치고 가용 상태가 되어 다음으로 진행할 작업을 선택할 때, 설비 앞에 대기하고 있는 작업을 포함하여 본 설비에 아직 도착하지 않은 작업들도 선택 후보로 고려한다.
또한 최적해를 구하는 알고리즘은 문제의 크기가 커짐에 따라 기하급수적으로 계산 시간이 증가하는 단점이 있다. 본 연구에서는 잡샵에서 총지연도를 최소화하기 위하여 지연 일정계획을 고려한 디스패칭 기반의 효율적이고 효과적인 알고리즘을 제안하였다.
본 연구에서는 총지연도를 최소화하기 위한 목적의 일반적인 잡샵 문제를 다루었다. 이 문제에 대해서 할당할 수 있는 작업이 대기하고 있는 상황에서도 다른 작업을 진행하기 위해 설비가 대기하는 지연 일정계획에서 최적 해가 나타날 수 있음을 보였다.
위 작업들 중 임의의 작업이 설비에 할당되었다고 가정할 때 나머지 작업들의 납기 지연도를 추정한다. 이 총지연도의 추정치가 최소가 되는 작업을 선택하여 설비에서 작업을 진행하는 방법을 제안하였다. 아직 도착하지 않은 작업이 선택되는 경우, 설비는 이 작업이 도착할 때까지 다른 작업을 진행하지 않고 대기하게 되는 지연 일정계획이 작성된다.

가설 설정

[Figure 3] 의 Case B와 같이 의사결정 시점에 이미 지연 작업으로 확정된 작업 k에 대해서는 식 (1)로 계산되는 납기 대비 지연된 시간을 총지연도 추정량에 그대로 반영한다. 여기에서 작업 k의 지연도 추정치를 계산할 때 모든 공정이 지연 없이 설비에 할당 된다고 가정하여 종료시점을 추정하므로 실제 일정계획의 결과보다 보수적으로 산정하여 실제보다 적은 값이 된다.

제안 방법

다음 장에서 지연 일정계획 방법에서 최적해가 존재할 수 있는 성질에 대해서 소개하고 그 효과를 예제로 보여 주었다. 제 3장에서는 총지연도를 추정하는 방법과 본 연구에서 제안하는 일정계획 알고리즘을 기술하였다.
다음은 위의 추정 지연도를 활용하여 지연 일정계획을 작성할 수 있는 알고리즘을 정리하였다.
본 연구는 총지연도를 최소화하는 잡샵(job shop) 일정계획 문제를 다룬다. 본 문제에 대하여 총지연도를 추정하여 총 지연도를 최소화할 수 있도록 하는 디스패칭 기반의 휴리스틱 알고리즘을 제안하였다. 본 연구에서 제안한 일정계획 방법론은 설비에 할당할 다음 작업을 선택할 때 아직 설비에 도착하지 않은 작업들을 선택 후보에 포함시켜 총지연도 추정치가 최소가 되도록 일정계획을 작성함으로써 지연 일정계획 생성이 가능하도록 하였다.
본 연구에서는 일반적인 잡샵 일정계획 문제에 대하여 총지연도를 최소화하기 위하여 디스패칭 방식의 작업 할당 알고리즘을 제안하였다. 본 연구에서 제안하는 알고리즘은 설비가 작업을 마치고 가용 상태가 되어 다음으로 진행할 작업을 선택할 때, 설비 앞에 대기하고 있는 작업을 포함하여 본 설비에 아직 도착하지 않은 작업들도 선택 후보로 고려한다. 위 작업들 중 임의의 작업이 설비에 할당되었다고 가정할 때 나머지 작업들의 납기 지연도를 추정한다.
잡샵 문제에 대해서 디스패칭 규칙 기반의 접근 방법은 설비가 가용 상태가 되었을 때, 현재 대기하고 있는 작업(operation)들의 우선순위를 계산하여 가장 높은 우선순위를 갖는 작업을 해당 설비에 할당하여 진행하는 방식이다. 본 연구에서 제안하는 알고리즘은 해당 설비 에서 진행해야하는 모든 작업의 우선순위를 계산한다. 즉, 설비 앞에 도착하지 않은 작업의 경우에도 우선순위가 높으면 설비가 해당 작업을 진행하기 위해 유휴 상태로그 작업이 도착할 때까지 대기하게 된다.
본 연구에서 제안한 MET 알고리즘을 생산 현장에서 보편적으로 사용한 납기기반의 디스패칭 규칙들인 EDD, Slack, MDD, COVERT, ATC와 성능을 비교하였다. 각 디스패칭 규칙을 요약하면 다음과 같다.
본 연구에서 제안한 알고리즘의 성능을 평가하기 위하여 다양한 문제에 대해서 일반적으로 총지연도를 최소화하는데 사용하는 디스패칭 규칙들과 결과를 비교하는 실험을 수행하였다. 총지연도 지표에 관하여서는 다른 디스패칭 규칙들보다 우수한 결과를 보였다.
본 문제에 대하여 총지연도를 추정하여 총 지연도를 최소화할 수 있도록 하는 디스패칭 기반의 휴리스틱 알고리즘을 제안하였다. 본 연구에서 제안한 일정계획 방법론은 설비에 할당할 다음 작업을 선택할 때 아직 설비에 도착하지 않은 작업들을 선택 후보에 포함시켜 총지연도 추정치가 최소가 되도록 일정계획을 작성함으로써 지연 일정계획 생성이 가능하도록 하였다.
연구에서 제안한 일정계획 알고리즘 MET의 성능을 평가하기 위하여 각 조건에 따라 임의의 잡샵 일정계획 문제 300개를 생성하였다. 생성된 실험 문제는 5개 수준의 작업 개수(10, 20, 30, 40, 50개), 3개 수준의 납기 tightness factor(loose, normal, tight)로 하여 15개의 조합으로 구성하였다. 각 실험 조합에 대해서 20개씩의 반복 실험을 시행하여 총 300개의 문제에 대해서 실험을 진행 하였다.
이 문제에 대해서 할당할 수 있는 작업이 대기하고 있는 상황에서도 다른 작업을 진행하기 위해 설비가 대기하는 지연 일정계획에서 최적 해가 나타날 수 있음을 보였다. 이를 기반으로 빠르고 효율적인 솔루션으로 지연 일정계획을 고려한 디스패칭 규칙 기반의 알고리즘을 제안하였다. 기존의 디스패칭 규칙 기반의 스케쥴링 알고리즘은 대기하고 있는 작업의 우선순위를 계산하여 일정계획을 수립하기 때문에 지연 일정계획이 해에서 배제되어 있다.

대상 데이터

생성된 실험 문제는 5개 수준의 작업 개수(10, 20, 30, 40, 50개), 3개 수준의 납기 tightness factor(loose, normal, tight)로 하여 15개의 조합으로 구성하였다. 각 실험 조합에 대해서 20개씩의 반복 실험을 시행하여 총 300개의 문제에 대해서 실험을 진행 하였다. 각 실험 문제에서 관련 데이터는 다음의 파라메 터로 확률적으로 생성하였다.
연구에서 제안한 일정계획 알고리즘 MET의 성능을 평가하기 위하여 각 조건에 따라 임의의 잡샵 일정계획 문제 300개를 생성하였다. 생성된 실험 문제는 5개 수준의 작업 개수(10, 20, 30, 40, 50개), 3개 수준의 납기 tightness factor(loose, normal, tight)로 하여 15개의 조합으로 구성하였다.

데이터처리

위의 실험 문제를 대상으로 본 연구에서 제안한 지연을 고려한 일정계획 알고리즘 MET와 실제 현장에서 많이 사용하는 디스패칭 기반의 알고리즘 EDD, Slack, MDD, COVERT, ATC와 비교하였다.

이론/모형

Singer and Pinedo[12]가 총지연도를 최소화하는 분지 한계법을 제안하였다. 이어서 동일한 문제에 대하여 shift bottleneck 방법론을 제안하여 적용하였다[11]. 이와 관련하여 Jayamohan and Rajendran[8]가 관련 연구를 체계적으로 정리하였다.

성능/효과

따라서, 제안된 MET 알고리즘은 합리적인 납기가 설정되어 있는 경우에 총지연도에서 다른 알고리즘에 비해 좋은 결과를 보여 준다. 또한, 지연 주문의 비율 지표에 대해서는 다른 알고리즘에 대해서 성능저하 없는 결과를 보여주는 것으로 확인되었다.
따라서, 제안된 MET 알고리즘은 합리적인 납기가 설정되어 있는 경우에 총지연도에서 다른 알고리즘에 비해 좋은 결과를 보여 준다. 또한, 지연 주문의 비율 지표에 대해서는 다른 알고리즘에 대해서 성능저하 없는 결과를 보여주는 것으로 확인되었다.
[Table 4]와 [Table 5]는 MET 알고리즘과 나머지 rule 을 적용한 경우에 대해서 전체 주문들 중 지연된 주문 수의 비율인 지연 주문 비율을 비교한 것이다. 이 목적 함수에 대해서는 MDD가 가장 좋은 결과를 보이고 SLACK이 가장 나쁜 결과를 보인다. 주문의 수가 적거나 납기에 충분한 여유가 있는 경우에만 MET 알고리즘의 성능이 우위에 있는 것으로 나타났다.
이 목적 함수에 대해서는 MDD가 가장 좋은 결과를 보이고 SLACK이 가장 나쁜 결과를 보인다. 주문의 수가 적거나 납기에 충분한 여유가 있는 경우에만 MET 알고리즘의 성능이 우위에 있는 것으로 나타났다.
[Table 2]에서 주문의 수에 따라서 전반적으로 MET 알고리즘이 좋은 결과를 주는 것을 확인할 수 있다. 특히 주문의 수가 적을 때(10개~30개)에 MET 알고리즘의 성능이 다른 규칙에 비해 월등한 성능을 보여준다. 주문의 수가 많은 경우(40개~50개)에서는 COVER 규칙과 MET 알고리즘이 유사한 성능을 보여 준다.

후속연구

연구에서 제시한 디스패칭 알고리즘을 실제 상황에 적용하기 위해서는 작업시간 정보, 현재 진행 중인 작업 상태 정보 등과 같은 기준 정보와 실시간 운영 정보의 정합성 확보가 선행되어야 한다. 또한 제안된 알고리즘에서 계산하는 총지연도의 추정치에 대하여 현장의 특성을 반영한 다양한 후보군을 만들어 평가 및 개선하는 연구가 수반되어야 한다.
기존의 디스패칭 규칙 기반의 스케쥴링 알고리즘은 대기하고 있는 작업의 우선순위를 계산하여 일정계획을 수립하기 때문에 지연 일정계획이 해에서 배제되어 있다. 본 연구에서 개발한 알고리즘에서는 임의의 작업이 설비에 할당될 때 총지연도의 추정치를 예측하여 총지연도가 최소화 될 수 있도록 작업을 선택한다. 이때 아직 도착하지 않은 작업도 설비에 할당할 대상에 포함시켜 지연도의 추정치를 계산함으로써 이런 작업이 지연도를 최소화하는 것으로 선택되었을 때는 지연 일정계획이 생성될 수 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	총지연도를 최소화하는 것은 무엇인가?	본 연구는 총지연도를 최소화하는 잡샵(job shop) 일정계획 문제를 다룬다. 본 문제에 대하여 총지연도를 추정하여 총 지연도를 최소화할 수 있도록 하는 디스패칭 기반의 휴리스틱 알고리즘을 제안하였다.
	총 지연도를 최소화할 수 있는 휴리스틱 알고리즘은 무엇의 기반인가?	본 연구는 총지연도를 최소화하는 잡샵(job shop) 일정계획 문제를 다룬다. 본 문제에 대하여 총지연도를 추정하여 총 지연도를 최소화할 수 있도록 하는 디스패칭 기반의 휴리스틱 알고리즘을 제안하였다. 본 연구에서 제안한 일정계획 방법론은 설비에 할당할 다음 작업을 선택할 때 아직 설비에 도착하지 않은 작업들을 선택 후보에 포함시켜 총지연도 추정치가 최소가 되도록 일정계획을 작성함으로써 지연 일정계획 생성이 가능하도록 하였다.
	기업의 생산 현장이 다품종 소량 생산으로 빠르게 전환되는 원인은?	최근의 시장의 흐름은 소비자의 다양성과 트렌드 변화에 주목하는 기업들이 수익을 안정적으로 확보하고 있다. 이에 따라 각 기업의 생산 현장은 기존의 소품종 대량생산 체계에서 다품종 소량 생산으로 빠르게 전환되어가고 있다.

참고문헌 (17)

10.1016/S0925-5273(99)00014-6 Armentano, V.A. and Scrich, C.R., Tabu search for minimizing total tardiness in a job shop, International Journal of Production Economics , 2000, Vol. 63, No. 2, pp. 131-140.

상세보기
10.11627/jkise.2015.38.4.159 Bang, J.-Y., Two-Level Hierarchical Production Planning for a Semiconductor Probing Facility, Journal of Society of Korea Industrial and Systems Engineering , 2015, Vol. 38, No. 4, pp. 159-167.

원문보기 상세보기
10.1007/s10951-012-0305-x Braune, R., Zapfel, G., and Affenzeller, M., Enhancing local search algorithms for solving job shops with minsum objectives by approximate move evaluation, Journal of Scheduling , 2013, Vol. 16, No. 5, pp. 495-518.

상세보기
10.1016/j.cor.2010.09.015 Bulbul, K., A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem, Computers and operations Research , 2011, Vol. 38, No. 6, pp. 967-983.

상세보기
10.1111/itor.12199 Chaudhry, I.A. and Khan, A.A., A research survey : review of flexible job shop scheduling techniques, International Transactions in Operational Research , 2016, Vol. 23, No. 3, pp. 551-591.

상세보기
10.1007/s10951-005-4779-7 de Bontridder, K.M.J., Minimizing total weighted tardiness in a generalized job shop, Journal of Scheduling , 2005, Vol. 8, No. 6, pp. 479-496.

상세보기
10.1016/j.cor.2006.12.019 Essafi, I., Mati, Y., and Dauzere-Peres, S., A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem, Computers and Operations Research , 2008, Vol. 35, No. 8, pp. 2599-2616.

상세보기
10.1080/002075400189301 Jayamohan, M.S. and Rajendran, C., New dispatching rules for job shop scheduling : A step forward, International Journal of Production Research , 2000, Vol. 38, No. 3, pp. 563-586.

상세보기
10.1016/S0377-2217(03)00016-X Mattfeld, D.C. and Bierwirth, C., An efficient genetic algorithm for job shop scheduling with tardiness objectives, European Journal of Operational Research , 2004, Vol. 155, No. 3, pp. 616-630.

상세보기
10.5762/KAIS.2016.17.5.305 Park, K.M. and Jeong, S.J., A study on the improvement of work flow and productivity in complex manufacturing line by employing the effective process control methods, Journal of the Korea Academia-Industrial Cooperation Society , 2016, Vol. 17, No. 5 pp. 305-315.

원문보기 상세보기
10.1002/(SICI)1520-6750(199902)46:1@@ @@3.3.CO;2-R Pinedo, M.L. and Singer, M., A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop, Naval Research Logistics , 1999, Vol. 46, No. 1, pp. 1-17.
10.1080/07408179808966443 Singer, M. and Pinedo, M.L., Computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops, IIE Transactions , 1998, Vol. 30, pp. 109-119.

상세보기
10.1287/mnsc.33.8.1035 Vepsalainen, A.P.J. and Morton, T.E., Priority rules for job shops with weighted tardiness costs, Management Science , 1987, Vol. 33, No. 8, pp. 1035-1047.

상세보기
10.1093/imaman/dps020 Zhang, R. and Wu, C., A neighbourhood property for the ob shop scheduling problem with application to hybrid particle swarm optimization, IMA Journal of Management Mathematics , 2013, Vol. 24, No. 1, pp. 111-134.

상세보기
10.1155/2012/623230 Zhang, R. and Wu, C., A PMBGA to optimize the selection of rules for job shop scheduling based on the Giffler-Thompson algorithm, Journal of Applied Mathematics , 2012, Vol. 2012, pp. 1-17.

상세보기
10.1016/j.cor.2010.09.014 Zhang, R. and Wu, C., A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective, Computers and Operations Research , 2011, Vol. 38, No. 5, pp. 854-867.

상세보기
10.1016/j.ijpe.2012.03.035 Zhang, R., Song, S., and Wu, C., A hybrid artificial bee colony algorithm for the job shop scheduling problem, International Journal of Production Economics , 2013, Vol. 141, No. 1, pp. 167-178.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증