An efficient heuristic for a real-life OAS problem

• Authors: ANHOLCER Marcin , ŻAK Andrzej
• Languages of publication: EN

Abstracts

EN

Inspired by a real-life manufacturing problem, we present a mathematical model and a heuristic that solves it. A desired solution needs not only to maximize the company’s profit but must also be easy to interpret by the members of the management. The considered problem is thus a variant of the order acceptance and scheduling (OAS) problem, which can be solved using known heuristics. Our approach is different because we study the mechanism by which setup times arise, unlike other approaches where setup times are treated as parts of the instance. This enables us to develop a very fast and efficient heuristic, formulate a MILP model that can be applied to solve much larger problems than previously known methods, and ultimately meet decision-makers’ expectations. We prove the efficiency of the presented method by comparing its results with the optimum obtained by a state-of-the-art solver. We also briefly discuss a case study that arose in a food industry company in Poland.

Keywords

EN

order acceptance and scheduling; sequence-dependence; greedy heuristics

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2025
• Volume: 35
• Issue: 1
• Pages: 1-20

Contributors

author

ANHOLCER Marcin

• Institute of Informatics and Electronic Economics, Poznań University of Economics and Business, Poznań, Poland

author

ŻAK Andrzej

• Faculty of Applied Mathematics, AGH University, Kraków, Poland

References

• Blocher, J. D., Chand, S., and Sengupta, K. The changeover scheduling problem with time and cost considerations: Analytical results and a forward algorithm. Operations Research 47, 4 (1999), 559–569.
• Bowers, M. R., Groom, K., Ng, W. M., and Zhang, G. Cluster analysis to minimize sequence dependent changeover times. Mathematical and Computer Modelling 21, 11 (1995), 89–95.
• Brunaud, B., Perez, H. D., Amaran, S., Bury, S., Wassick, J., and Grossmann, I. E. Batch scheduling with quality-based changeovers. Computers & Chemical Engineering 132 (2020), 106617.
• Casado, S., Laguna, M., Pacheco, J., and Puche, J. C. Grouping products for the optimization of production processes: A case in the steel manufacturing industry. European Journal of Operational Research 286, 1 (2020), 190–202.
• Castro, P. M. Optimal scheduling of a multiproduct batch chemical plant with preemptive changeover tasks. Computers & Chemical Engineering 162 (2022), 107818.
• Castro, P. M., Grossmann, I. E., and Zhang, Q. Expanding scope and computational challenges in process scheduling. Computers & Chemical Engineering 114 (2018), 14–42.
• Castro, P. M., Harjunkoski, I., and Grossmann, I. E. Greedy algorithm for scheduling batch plants with sequence-dependent changeovers. AIChE Journal 57, 2 (2011), 373–387.
• Charnsirisakskul, K., Griffin, P. M., and Keskinocak, P. Order selection and scheduling with leadtime flexibility. IIE Transactions 36, 7 (2004), 697–707.
• Chen, Y.-W., Lu, Y.-Z., and Yang, G.-K. Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization for production scheduling. The International Journal of Advanced Manufacturing Technology 36, 9-10 (2008), 959–968.
• Cplex, I. I. IBM ILOG CPLEX V12.1: User’s Manual for CPLEX. International Business Machines Corporation Armonk, NY, USA, 2009.
• Díaz-Ramírez, J., and Huertas, J. I. A continuous time model for a short-term multiproduct batch process scheduling. Ingeniería e Investigación 38, 1 (2018), 96–104.
• Duncan, W. P. Methods for Reducing Changeover Times Through Scheduling. Master’s thesis, University of Rhode Island, Kingston, RI, USA, 2011.
• Emami, S., Moslehi, G., and Sabbagh, M. A Benders decomposition approach for order acceptance and scheduling problem: a robust optimization approach. Computational and Applied Mathematics 36, 4 (2017), 1471–1515.
• Emami, S., Sabbagh, M., and Moslehi, G. A Lagrangian relaxation algorithm for order acceptance and scheduling problem: A globalised robust optimisation approach. International Journal of Computer Integrated Manufacturing 29, 5 (2016), 535–560.
• Engelmann, B., Schmitt, S., Miller, E., Bräutigam, V., and Schmitt, J. Advances in machine learning detecting changeover processes in cyber physical production systems. Journal of Manufacturing and Materials Processing 4, 4 (2020), 108.
• Geoffrion, A. M., and Graves, G. W. Scheduling parallel production lines with changeover costs: Practical application of a quadratic assignment/LP approach. Operations Research 24, 4 (1976), 595–610.
• Germs, R., and van Foreest, N. D. Order acceptance and scheduling policies for a make-to-order environment with family-dependent lead and batch setup times. International Journal of Production Research 51, 3 (2013), 940–951.
• Gurobi Optimization, LLC (2023). Gurobi Optimizer Reference Manual (accessed on 18 October 2023).
• He, C., Leung, J. Y.-T., Lee, K., and Pinedo, M. L. Improved algorithms for single machine scheduling with release dates and rejections. 4OR 14, 1 (2016), 41–55.
• Hong, S., Han, J., Choi, J. Y., and Lee, K. Accelerated dynamic programming algorithms for a car resequencing problem in automotive paint shops. Applied Mathematical Modelling 64 (2018), 285–297.
• Hu, X., Blocher, J. D., Heese, H. S., and Zhou, F. Scheduling products with subassemblies and changeover time. The Journal of the Operational Research Society 67, 8 (2016), 1025–1033.
• Kapadia, M. S., Uzsoy, R., Starly, B., and Warsing Jr., D. P. A genetic algorithm for order acceptance and scheduling in additive manufacturing. International Journal of Production Research 60, 21 (2022), 6373–6390.
• Konge, U., and Subramanian, S. Scheduling of process plants with equipment changeover. Computers & Chemical Engineering 162 (2022), 107812.
• Lawler, E. L. Fast approximation algorithms for Knapsack problems. Mathematics of Operations Research 4, 4 (1979), 339–356.
• Lee, H., and Maravelias, C. T. Discrete-time mixed-integer programming models for short-term scheduling in multipurpose environments. Computers & Chemical Engineering 107 (2017), 171–183.
• Lei, D., and Guo, X. A parallel neighborhood search for order acceptance and scheduling in flow shop environment. International Journal of Production Economics 165 (2015), 12–18.
• Li, Q., and Milne, R. J. A production scheduling problem with sequence-dependent changeover costs. International Journal of Production Research 52, 13 (2014), 4093–4102.
• Li, X., and Ventura, J. A. Exact algorithms for a joint order acceptance and scheduling problem. International Journal of Production Economics 223 (2020), 107516.
• Li, X., Ventura, J. A., and Bunn, K. A. A joint order acceptance and scheduling problem with earliness and tardiness penalties considering overtime. Journal of Scheduling 24, 1 (2021), 49–68.
• Liu, P., and Lu, X. New approximation algorithms for machine scheduling with rejection on single and parallel machine. Journal of Combinatorial Optimization 40, 4 (2020), 929–952.
• Lockett, A. G., and Muhlemann, A. P. Technical note—a scheduling problem involving sequence dependent changeover times. Operations Research 20, 4 (1972), 895–902.
• Montoya-Torres, J. R., Soto-Ferrari, M., and González-Solano, F. Production scheduling with sequence-dependent setups and job release times. DYNA 77, 163 (2010), 260–269.
• Ou, J. Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection. Journal of Scheduling 23, 5 (2020), 525–538.
• Ou, J., Lu, L., and Zhong, X. Parallel-batch scheduling with rejection: Structural properties and approximation algorithms. European Journal of Operational Research 310, 3 (2023), 1017–1032.
• Oğuz, C., Salman, F. S., and Yalçın, Z. B. Order acceptance and scheduling decisions in make-to-order systems. International Journal of Production Economics 125, 1 (2010), 200–211.
• Perea, F., Yepes-Borrero, J. C., and Menezes, M. B. C. Acceptance ordering scheduling problem: The impact of an order-portfolio on a make-to-order firm’s profitability. International Journal of Production Economics 264 (2023), 108977.
• Slotnick, S. A. Order acceptance and scheduling: A taxonomy and review. European Journal of Operational Research 212, 1 (2011), 1–11.
• Spindler, S., Steinhardt, C., and Klein, R. Exact solution approaches for order acceptance and scheduling decisions in m-machine open shops. Computers & Industrial Engineering 176 (2023), 108952.
• Sun, H., and Fan, S. Car sequencing for mixed-model assembly lines with consideration of changeover complexity. Journal of Manufacturing Systems 46 (2018), 93–102.
• Sun, H., and Han, J. A study on implementing color-batching with selectivity banks in automotive paint shops. Journal of Manufacturing Systems 44, (2017), 42–52.
• Tarhan, I., and Oğuz, C. Generalized order acceptance and scheduling problem with batch delivery: Models and metaheuristics. Computers & Operations Research 134 (2021), 105414.
• Tarhan, I., and Oğuz, C. A matheuristic for the generalized order acceptance and scheduling problem. European Journal ofOperational Research 299, 1 (2022), 87–103.
• Thevenin, S., and Zufferey, N. Learning variable neighborhood search for a scheduling problem with time windows and rejections. Discrete Applied Mathematics 261 (2019), 344–353.
• Van Rossum, G., and Drake Jr., F. L. Python Reference Manual. Centrum voor Wiskunde en Informatica, Amsterdam, 1995.
• Velez, S., Dong, Y., and Maravelias, C. T. Changeover formulations for discrete-time mixed-integer programming scheduling models. European Journal of Operational Research 260, 3 (2017), 949–963.
• Wang, Z., Qi, Y., Cui, H., and Zhang, J. A hybrid algorithm for order acceptance and scheduling problem in make-to-stock/make-to-order industries. Computers & Industrial Engineering 127 (2019), 841–852.
• Xu, L., Wang, Q., and Huang, S. Dynamic order acceptance and scheduling problem with sequence-dependent setup time. International Journal of Production Research 53, 19 (2015), 5797–5808.

Identifiers

DOI

10.37190/ord250101