This paper introduces a batch processing method for constraint programming to improve solution performance. The method is demonstrated in an example of a production scheduling problem. Transformations from mass production of standardized products toward small-scale, customized orders in the manufacturing sector introduce a new challenge of handling extensive input data. Modern production scheduling systems struggle to handle BigData loads caused by the limitations of state-of-the-art scheduling algorithms. Therefore, the development of highly adaptive algorithms and models capable of efficiently managing numerous unique orders while maintaining the ability to adapt to dynamic constraints and objectives becomes critically important. The baseline discrete constraint programming approach is chosen for its flexibility and extensibility, allowing it to model various realistic manufacturing scenarios. The proposed method splits large input into smaller subsets, each scheduled independently by repeatedly involving the constraint solver in different portions of the input data, significantly improving performance compared to allocating the whole input in a single step. Computational experiments with Google’s OR-Tools CP-SAT solver evaluated the method’s effectiveness. Time and memory usage reductions were shown. The proposed method demonstrates the possibility of solving problems of much larger size using the same constraint model and solver. It combines the advantages of the greedy algorithm and the exact integer programming approach.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Divide and Conquer Method for Constrained Programming Applied to Large Scale Production Scheduling Problems

  • Kostiantyn Hrishchenko,
  • Oleksii Pysarchuk,
  • Danylo Baran

摘要

This paper introduces a batch processing method for constraint programming to improve solution performance. The method is demonstrated in an example of a production scheduling problem. Transformations from mass production of standardized products toward small-scale, customized orders in the manufacturing sector introduce a new challenge of handling extensive input data. Modern production scheduling systems struggle to handle BigData loads caused by the limitations of state-of-the-art scheduling algorithms. Therefore, the development of highly adaptive algorithms and models capable of efficiently managing numerous unique orders while maintaining the ability to adapt to dynamic constraints and objectives becomes critically important. The baseline discrete constraint programming approach is chosen for its flexibility and extensibility, allowing it to model various realistic manufacturing scenarios. The proposed method splits large input into smaller subsets, each scheduled independently by repeatedly involving the constraint solver in different portions of the input data, significantly improving performance compared to allocating the whole input in a single step. Computational experiments with Google’s OR-Tools CP-SAT solver evaluated the method’s effectiveness. Time and memory usage reductions were shown. The proposed method demonstrates the possibility of solving problems of much larger size using the same constraint model and solver. It combines the advantages of the greedy algorithm and the exact integer programming approach.