KSP-SCOS: new Karp-Steele patching based streamlined customer order scheduling approach
DOI:
https://doi.org/10.38152/bjtv8n1-014Keywords:
customer order scheduling, Karp-Steele patching, KSP-SCOS, scheduling optimization, computational efficiency, resource managementAbstract
Customer order scheduling (COS) encapsulates one of the most intricate problems in operational optimization, primarily due to the multifaceted interplay of constraints such as temporal dependencies, resource limitations, and cost minimization. This paper introduces the Karp-Steele Patching for Streamlined COS (KSP-SCOS), a cutting-edge framework designed to address these complexities with unparalleled precision and efficiency. By incorporating the dynamic problem decomposition capabilities of Karp-Steele Patching, KSP-SCOS enhances the scheduling landscape through systematic exploration of feasible solutions while eliminating suboptimal paths through strategic pruning. The proposed approach was subjected to rigorous testing across diverse datasets representing a broad spectrum of real-world operational scenarios. These scenarios range from minimally constrained environments to those characterized by extensive resource contention and tight scheduling windows. Experimental findings reveal that KSP-SCOS consistently delivers near-optimal solutions, demonstrating robust scalability and significant reductions in computational overhead, regardless of the problem complexity. This research makes several noteworthy contributions to COS optimization : (1) The integration of the Karp-Steele Patching method within COS, ensuring a systematic yet adaptable solution process. (2) An empirical analysis across datasets of varying complexity, illustrating the algorithm’s effectiveness in balancing computational efficiency and scheduling quality. (3) An exploration of cost-time trade-offs, shedding light on the practical implications of for resource allocation in dynamic operational settings. The adaptability of KSP-SCOS establishes it as a groundbreaking for industries demanding dynamic, accurate, and resource-efficient scheduling strategies. Its capability to seamlessly adjust to evolving operational constraints underscores its critical relevance in scenarios requiring immediate and responsive decision-making. This study marks a pivotal advancement in resolving the pressing challenges of modern COS, paving the way for elevated operational efficacy and adaptability in increasingly complex environments.
References
ABREU, L. R. et al. A genetic algorithm for scheduling open shops with sequence-dependent setup times. Computers & Operations Research, v. 113, p. 104793, 2020.
ALARCON-GERBIER, E.; ZIPFEL, B.; BUSCHER, U. Customer order scheduling in a mobile 3d printing factory. IFAC-PapersOnLine, v. 55, n. 10, p. 2270–2275. 10th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2022.
CHIN-CHIA, W. et al. Robust scheduling for a two-stage assembly shop with scenario-dependent processing times. International Journal of Production Research, Taylor & Francis, v. 59, n. 17, p. 5372–5387, 2021.
DE Abreu, L. R. et al. A novel brkga for the customer order scheduling with missing operations to minimize total tardiness. Swarm and Evolutionary Computation, v. 75, p. 101149, 2022.
FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures. Journal of Global Optimization, v. 6, n. 2, p. 109–133, 1995.
FERNANDEZ-VIAGAS, V.; PEREZ-GONZALEZ, P.; FRAMINAN, J. M. Efficiency of the solution representations for the hybrid flow shop scheduling problem with makespan objective. Computers & Operations Research, v. 109, p. 77–88, 2019.
FRAMINAN, J. M.; PEREZ-GONZALEZ, P. New approximate algorithms for the customer order scheduling problem with total completion time objective. Computers & Operations Research, v. 78, p. 181–192, 2017.
FRAMINAN, J. M.; PEREZ-GONZALEZ, P. Order scheduling with tardiness objective: Improved approximate solutions. European Journal of Operational Research, v. 266, n. 3, p. 840–850, 2018.
FRAMINAN, J. M.; PEREZ-GONZALEZ, P.; FERNANDEZ-VIAGAS, V. Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures. European Journal of Operational Research, v. 273, n. 2, p. 401–417, 2019.
GUPTA, J. N. et al. Bicriteria single-machine scheduling with multiple job classes and customer orders. Applied Soft Computing, v. 147, p. 110809, 2023.
KUNG, J. et al. Metaheuristics for order scheduling problem with unequal ready times. Discrete Dynamics in Nature and Society, p. 4657368, 2018.
KUO, Y.; CHEN, S.-I.; YEH, Y.-H. Single machine scheduling with sequencedependent setup times and delayed precedence constraints. Operational Research, v. 20, n. 2, p. 927–942, 2020.
LEE, I. S. Minimizing total tardiness for the order scheduling problem. International Journal of Production Economics, v. 144, n. 1, p. 128–134, 2013.
LEUNG, J. Y.-T.; LI, H.; PINEDO, M. Scheduling orders for multiple product types with due date related objectives. European Journal of Operational Research, v. 168, n. 2, p. 370–389, 2006.
LIU, Z. et al. Intelligent scheduling of a feature-process-machine tool supernetwork based on digital twin workshop. Journal of Manufacturing Systems, v. 58, p. 157–167, 2021.
MANSOUR, M.; ABDELKRIM, H.; HAMZA, T. New model to streamline customer order scheduling. Brazilian Journal of Technology: Articles in Press.
PRATA, B. de A.; RODRIGUES, C. D.; FRAMINAN, J. M. Customer order scheduling problem to minimize makespan with sequence-dependent setup times. Computers & Industrial Engineering, v. 151, p. 106962, 2021.
PRATA, B. de A.; RODRIGUES, C. D.; FRAMINAN, J. M. A differential evolution algorithm for the customer order scheduling problem with sequence-dependent setup times. Expert Systems with Applications, v. 189, p. 116097, 2022.
WANG, G.; CHENG, T. E. Customer order scheduling to minimize total weighted completion time. Omega, v. 35, n. 5, p. 623–626, 2007.
WU, C.-C. et al. Bicriterion total flowtime and maximum tardiness minimization for an order scheduling problem. Computers & Industrial Engineering, v. 117, p. 152–163, 2018.
WU, C.-C. et al. Using heuristic and iterative greedy algorithms for the total weighted completion time order scheduling with release times. Swarm and Evolutionary Computation, v. 44, p. 913–926, 2019.
YAPING, Z. et al. Stochastic customer order scheduling with setup times to minimize expected cycle time. International Journal of Production Research, Taylor & Francis, v. 56, n. 7, p. 2684–2706, 2018.
ZHANG, X. et al. Single-machine scheduling problems with a learning effect matrix. Iranian Journal of Science and Technology, Transactions A: Science, v. 42, n. 3, p. 1327–1335, 2018.
