Scheduling multi-colour print jobs with sequence-dependent setup times

详细信息    查看全文

• 作者：A. P. Burger (1)
  C. G. Jacobs (1)
  J. H. van Vuuren (2)
  S. E. Visagie (1)
  
  1. Department of Logistics ; Stellenbosch University ; Private Bag X1 ; Matieland ; 7602 ; South Africa
  2. Department of Industrial Engineering ; Stellenbosch University ; Private Bag X1 ; Matieland ; 7602 ; South Africa
  
• 关键词：Job grouping ; Job scheduling ; Job sequencing ; Tool switching ; 90B35 ; 05A18 ; 05C15
• 刊名：Journal of Scheduling
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：18
• 期：2
• 页码：131-145
• 全文大小：367 KB
• 参考文献：1. Allahverdi, A, Gupta, JND, Aldowaisan, T (1999) A review of scheduling research involving setup considerations. Omega International Journal of Management Science 27: pp. 219-239 CrossRef
  2. Allahverdi, A, Ng, CT, Cheng, TCE, Kovalyov, MY (2008) A survey of scheduling problems with setup times or costs. European Journal of Operational Research 187: pp. 985-1032 CrossRef
  3. Avci, S, Akturk, MS (1996) Tool magazine arrangement and operations sequencing on CNC machines. Computers and Operations Research 23: pp. 1069-1081 CrossRef
  4. Balakrishnan, N, Chakravarty, AK (2001) Opportunistic retooling of a flexible machine subject to failure. Naval Research Logistics 48: pp. 79-97 CrossRef
  5. Balas, E A class of location, distribution and scheduling problems: Modeling and solution methods. In: Gray, R, Yuanzhang, L eds. (1983) Proceedings of the Chinese鈥揢S Symposium on systems analysis. Wiley, New York
  6. Ball, MO, Magnanti, TL, Monma, CL, Nemhauser, GL Network models. In: Nemhauser, GL, Rinnoy Kan, AHG eds. (1995) Handbooks in operations research and management science. Elsevier, Amsterdam
  7. Bard, JF (1988) A heuristic for minimizing the number of tool switches on a flexible machine. IIE Transactions 20: pp. 382-391 CrossRef
  8. Belady, LA (1966) A study of replacement algorithms for virtual storage computers. IBM Systems Journal 5: pp. 78-101 CrossRef
  9. Blazewicz, J, Finke, G (1994) Scheduling with resource management in manufacturing systems. European Journal of Operational Research 76: pp. 1-14 CrossRef
  10. Ceria, S, Nobili, P, Sassano, A Set covering problem. In: Dell鈥橝mico, M, Maffioli, F, Martello, S eds. (1997) Annotated bibliographies in combinatorial optimization. Wiley, Chichester, pp. 415-428
  11. Crama, Y, Kolen, AWJ, Oerlemans, AG, Speksma, FCR (1994) Minimizing the number of tool switches on a flexible machine. International Journal of Flexible Manufacturing Systems 6: pp. 33-54 CrossRef
  12. Crama, Y, Oerlemans, AG (1994) A column generation apporach to job grouping for flexible manufacturing systems. Europena Journal of Operational Research 78: pp. 58-80 CrossRef
  13. Crama, Y (1997) Combinatorial optimization models for production scheduling in automated manufacturing systems. European Journal of Operational Research 99: pp. 136-153 CrossRef
  14. Crama, Y, Klundert, J, Spieksma, FCR (2002) Production planning problems in printed circuit board assembly. Discrete Applied Mathematics 123: pp. 339-361 CrossRef
  15. Dantzig, GB, Fulkerson, DR, Johnson, SM (1954) Solution of a large-scale traveling salesman problem. Operations Research 2: pp. 393-410
  16. Follonier, J-P (1994) Minimization of the number of tool switches on a flexible machine. Belgian Journal of Operations Research, Statistics and Computer Science 34: pp. 55-72
  17. Garey, MR, Johnson, DS (1979) Computers and intractability: A guide to the theory of NP-completeness. Freeman, New York
  18. Ghiani, G, Grieco, A, Guerriero, E (2010) Solving the job sequencing and tool switching problem as a nonlinear least cost hamiltonian cycle problem. Networks 55: pp. 379-385 CrossRef
  19. Gray, AE, Seidmann, A, Stecke, KE (1993) A synthesis of decision models for tool management in automated manufacturing. Management Science 39: pp. 549-567 CrossRef
  20. Gutin, G, Punnen, AP (2002) The travelling salesman problem and its variations. Combinatorial optimization series. Springer, New York
  21. Hertz, A, Widmer, M (1993) An improved tabu search approach for solving the job shop scheduling problem with tooling constraints. Discrete Applied Mathematics 65: pp. 319-345 CrossRef
  22. Hertz, A, Laporte, G, Mittaz, M, Stecke, KE (1998) Heuristics for minimizing tool switches when scheduling part types on a flexible machine. IIE Transactions 30: pp. 689-694
  23. International Business Machines. (2013). CPLEX Optimizer, October 17th 2013. oftware/commerce/optimization/cplex-optimizer/" class="a-plus-plus">http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/
  24. Kiran, AS, Krason, RJ (1988) Automated tooling in a flexible manufacturing system. Industrial Engineering 20: pp. 52-57
  25. Knuutila, T, Hirvikorpi, M, Johnsson, M, Nevalainen, O (2002) Grouping PCB assembly jobs with typed component feeder units. Technical Report 460. Turku Centre for Computer Science, Finland
  26. Laporte, G, Salazar-Gonz谩lez, JJ, Semet, F (2004) Exact algorithms for the job sequencing and tool switching problem. IIE Transactions 36: pp. 37-45 CrossRef
  27. McGeoch, L. A., & Sleator, D. D. (1991). A strongly competitive randomized paging algorithm. / Algorithmica, / 6, 816鈥?25.
  28. Nemhauser, G. L., Trotter, L. E., & Nauss, R. M. (1972). Set partitioning and chain decomposition. / Management Science, / 20(22), 1413鈥?423.
  29. Oerlemans, A. G. (1992). Production planning for flexible manufacturing systems. PhD Dissertation, University of Limburg, Maastricht.
  30. Privault, P., & Finke, G. (2000). / k-Server problems with bulk requests: An application to tool switching in manufacturing. / Annals of Operations Research, / 96, 255鈥?69.
  31. Rosen, KH (2000) Handbook of discrete and combinatorial mathematics. CRC Press, Boca Raton, FL
  32. Salonen, K, Smed, J, Johnsson, M, Nevalainen, O (2006) Grouping and sequencing PCB assembly jobs with minimum feeder setups. Robotics and Computer-integrated Manufacturing 22: pp. 297-305 CrossRef
  33. Sodhi, MS, Askin, RG, Sen, S (1994) Multiperiod tool and production assignment in flexible manufacturing systems. International Journal of Production Research 32: pp. 1281-1294 CrossRef
  34. Tang, CS, Denardo, EV (1988) Models arising from a flexible manufacturing machine Part I: Minimization of the number of tool switches. Operations Research 36: pp. 767-777 CrossRef
  35. Veen, JAA, Woeginger, GJ, Zhang, S (1998) Sequencing jobs that require common resources on a single machine: A solvable case of the TSP. Mathematical Programming 82: pp. 235-254
  36. Weisstein, EW (2003) CRC concise encyclopedia of mathematics. Chapman & Hall/CRC, Boca Raton, FL
  37. Yildirim, MB, Duman, E, Krishna, K, Senniappan, K (2007) Parallel machine scheduling with load balancing and sequence dependent setup times. International Journal of Operations Research 4: pp. 42-49
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Calculus of Variations and Optimal Control
  Optimization
  Artificial Intelligence and Robotics
  Production and Logistics
  
• 出版者：Springer Netherlands
• ISSN：1099-1425

文摘

In this paper, a scheduling problem is considered which arises in the packaging industry. Plastic and foil wrappers used for packaging candy bars, crisps and other snacks typically require overlay printing with multiple colours. Printing machines used for this purpose usually accommodate a small number of colours which are loaded into a magazine simultaneously. If two consecutively scheduled print jobs require significantly different colour overlays, then substantial down times are incurred during the transition from the former magazine colour configuration to the latter, because ink cartridges corresponding to colours not required for the latter job have to be cleaned after completion of the former job. The durations of these down times are therefore sequence dependent (the washing and refilling time is a function of the number of colours in which two consecutive printing jobs differ). It is consequently desirable to schedule print jobs so that the accumulated down times associated with all magazine colour transitions are as short as possible for each printing machine. We show that an instance of this scheduling problem can be modelled as the well-known tool switching problem, which is tractable for small instances only. The problem can, however, be solved rather effectively in heuristic fashion by decomposing it into two subproblems: a job grouping problem (which can be modelled as a unicost set covering problem) and a group sequencing problem (which is a generalisation of the celebrated travelling salesman problem). We solve the colour print scheduling problem both exactly and heuristically for small, randomly generated test problem instances, studying the trade-off between the time efficiency and solution quality of the two approaches. Finally, we apply both solution approaches to real problem data obtained from a printing company in the South African Western Cape as a special case study.