잉크 색상 변화가 존재하는 인쇄 공정의 스케줄링 = Scheduling of Printing Process in which Ink Color Changes Exist

다국어 초록 (Multilingual Abstract)

The printing process can have to print various colors with a limited capacity of printing facility such as ink containers that are needed cleaning to change color. In each container, cleaning time exists to assign corresponding inks, and it is considered as the setup cost required to reduce the increasing productivity. The existing manual method, which is based on the worker’s experience or intuition, is difficult to respond to the diversification of color requirements, mathematical modeling and algorithms are suggested for efficient scheduling. In this study, we propose a new type of scheduling problem for the printing process. First, we suggest a mathematical model that optimizes the color assignment and scheduling. Although the suggested model guarantees global optimality, it needs a lot of computational time to solve. Thus, we decompose the original problem into sequencing orders and allocating ink problems. An approximate function is used to compute the job scheduling, and local search heuristic based on 2-opt algorithm is suggested for reducing computational time. In order to verify the effectiveness of our method, we compared the algorithms performance. The results show that the suggested decomposition structure can find acceptable solutions within a reasonable time. Also, we present schematized results for field application.

목차 (Table of Contents)

• Ⅰ. 서론 Ⅱ. 관련 연구 Ⅲ. 문제 소개 및 수리모형 Ⅳ. 해법 Ⅴ. 실험 및 결과 분석 Ⅵ. 결론 Acknowledgements References

참고문헌 (Reference)

1 주철민, "작업투입시점과 순서의존적인 준비시간이 존재하는 병렬기계 일정계획을 위한 개선 개미군집 시스템" 대한산업공학회 35 (35): 218-225, 2009

2 유성열, "작업순서에 따라 달라지는 준비 비용을 갖는 PCB 생산 공정의 일정계획" 대한경영정보학회 34 (34): 67-78, 2015

3 유우식, "작업 준비비용 최소화를 고려한 강화학습 기반의 실시간 일정계획 수립기법" 한국전자거래학회 25 (25): 15-27, 2020

4 유우식, "납기와 작업준비비용을 고려한 병렬기계에서 딥러닝 기반의 일정계획 생성 모델" 한국전자거래학회 24 (24): 99-110, 2019

5 이주용, "긴급주문과 순서의존준비시간이 있는 흐름공정의 일정계획 휴리스틱 알고리즘 연구" 한국경영과학회 37 (37): 47-60, 2020

6 "WIKIPEDIA"

7 Laporte, G., "The traveling salesman problem : An overview of exact and approximate algorithms" 59 (59): 231-247, 1992

8 Garfinkel, R. S., "Technical Note-On Partitioning the Feasible Set in a Branch-and-Bound Algorithm for the Asymmetric Traveling-Salesman Problem" 21 (21): 340-343, 1973

9 Glover, F., "Tabu Search-Part Ⅱ ORSA" 2 (2): 4-32, 1990

10 Glover, F., "Tabu Search-Part Ⅰ ORSA" 1 (1): 190-206, 1989

11 Kirkpatrick, S., "Optimization by Simulated Annealing" 220 (220): 671-680, 1983

12 Vela, C. R., "Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times" 16 (16): 139-165, 2010

13 Gupta, J. N. D., "Flowshop Schedules With Sequence Dependent Setup TIMES" 29 (29): 206-219, 1986

14 Bellman, R., "Dynamic Programming Treatment of the Travelling Salesman Problem" 9 (9): 61-63, 1962

15 Lin, S., "An effective heuristic algorithm for the traveling-salesman problem" 21 (21): 498-516, 1973

16 Rosenkrantz, D. J., "An analysis of several heuristics for the traveling salesman problem" 6 (6): 563-581, 1977

17 Nadesri, B., "A high performing metaheuristic for job shop scheduling with sequence-dependent setup times" 10 (10): 703-710, 2010

18 Artigues, C., "A branch and bound method for the job-shop problem with sequence-dependent setup times" 159 (159): 135-159, 2008

19 Shin, H. J., "A Tabu Search Algorithm for Single Machine Scheduling Problem with Job Release Times and Sequence-dependent Setup Times" 27 (27): 158-168, 2001