잉크 색상 변화가 존재하는 인쇄 공정의 스케줄링
Scheduling of Printing Process in which Ink Color Changes Exist
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (19)
- Artigues, C., "A branch and bound method for the job-shop problem with sequence-dependent setup times", Annals of Operations Research, 159(1), pp.135~159 (2008)
- Bellman, R., "Dynamic Programming Treatment of the Travelling Salesman Problem", Journal of the ACM, 9(1), pp.61~63 (1962)
- Garfinkel, R. S., "Technical Note-On Partitioning the Feasible Set in a Branch-and-Bound Algorithm for the Asymmetric Traveling-Salesman Problem", Operations Research, 21(1), pp.340~343 (1973)
- Glover, F., "Tabu Search-Part Ⅰ ORSA", Journal on Computing, 1(3), pp.190~206 (1989)
- Glover, F., "Tabu Search-Part Ⅱ ORSA", Journal on Computing, 2(1), pp.4~32 (1990)
- Gupta, J. N. D., "Flowshop Schedules With Sequence Dependent Setup TIMES", Journal of the Operations Research Society of Japan, 29(3), pp.206~219 (1986)
- 주철민, "작업투입시점과 순서의존적인 준비시간이 존재하는 병렬기계 일정계획을 위한 개선 개미군집 시스템", 대한산업공학회지, 35(4), pp.218~225 (2009), 대한산업공학회
- Kirkpatrick, S., "Optimization by Simulated Annealing", Science, 220(4598), pp.671~680 (1983)
- Laporte, G., "The traveling salesman problem : An overview of exact and approximate algorithms", European Journal of Operational Research, 59(2), pp.231~247 (1992)
- 이주용, "긴급주문과 순서의존준비시간이 있는 흐름공정의 일정계획 휴리스틱 알고리즘 연구", 경영과학, 37(1), pp.47~60 (2020), 한국경영과학회[DOI]
- Lin, S., "An effective heuristic algorithm for the traveling-salesman problem", Operations Research, 21(2), pp.498~516 (1973)
- Nadesri, B., "A high performing metaheuristic for job shop scheduling with sequence-dependent setup times", Applied Soft Computing, 10(3), pp.703~710 (2010)
- Rosenkrantz, D. J., "An analysis of several heuristics for the traveling salesman problem", SIAM Journal on Computing, 6(3), pp.563~581 (1977)
- Shin, H. J., "A Tabu Search Algorithm for Single Machine Scheduling Problem with Job Release Times and Sequence-dependent Setup Times", Journal of the Korean Institute of Industrial Engineers, 27(2), pp.158~168 (2001)
- Vela, C. R., "Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times", Journal of Heuristics, 16(1), pp.139~165 (2010)
- "WIKIPEDIA"[URL]
- 유우식, "작업 준비비용 최소화를 고려한 강화학습 기반의 실시간 일정계획 수립기법", 한국전자거래학회지, 25(2), pp.15~27 (2020), 한국전자거래학회[DOI]
- 유우식, "납기와 작업준비비용을 고려한 병렬기계에서 딥러닝 기반의 일정계획 생성 모델", 한국전자거래학회지, 24(3), pp.99~110 (2019), 한국전자거래학회[DOI]
- 유성열, "작업순서에 따라 달라지는 준비 비용을 갖는 PCB 생산 공정의 일정계획", 경영과 정보연구, 34(2), pp.67~78 (2015), 대한경영정보학회[DOI]