A size-reduction algorithm for the order scheduling problem with total tardiness minimization

Abstract: We investigated a variant of the customer order scheduling problem taking into consideration due dates to minimize the total tardiness. Since the problem under study is NP-hard, we propose an efficient size reduction algorithm (SR). We perform an extensive computational experience and compare our proposition with JPO-20 matheuristic, the best existing algorithm for the problem under study. We use the Relative Deviation Index (RDI) and the Success Rate (SRa) as the statistical indicators for the performance measure. We must emphasize that SR presented the lowest average RDI (around 15.5 %), whereas the JPO-20 presented an average RDI approximately three times higher (around 52.5 %). Furthermore, the proposed SR presented a higher average SRa (around 66.9%), whereas the JPO-20 presented a lower average success (around 25.7%). Our proposal used a lower computational effort, resulting in a reduction for the computation times of approximately 22%. The obtained results point to the superiority of the proposed SR in comparison with the JPO-20.

How to cite this paper

 Braga-Santos, S., Barroso, G & Prata, B. (2022). A size-reduction algorithm for the order scheduling problem with total tardiness minimization.Journal of Project Management, 7(3), 167-176.

Refrences

Ahmadi, R., Bagchi, U., & Roemer, T. A. (2005). Coordinated scheduling of customer orders for quick response. Naval Research Logistics (NRL), 52(6), 493-512.
Antonioli, M., Rodrigues, C., & Prata, B. (2022). Minimizing total tardiness for the order scheduling problem with se-quence-dependent setup times using hybrid matheuristics. International Journal of Industrial Engineering Computa-tions, 13(2), 223-236.
Fanjul-Peyro, L., & Ruiz, R. (2011). Size-reduction heuristics for the unrelated parallel machines scheduling problem. Computers & Operations Research, 38(1), 301-309.
Fanjul-Peyro, L., Perea, F., & Ruiz, R. (2017). Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. European Journal of Operational Research, 260(2), 482-493.
Fernandez-Viagas, V., & Framinan, J. M. (2015). NEH-based heuristics for the permutation flowshop scheduling prob-lem to minimise total tardiness. Computers & Operations Research, 60, 27-36.
Framinan, J. M., & Perez-Gonzalez, P. (2017). New approximate algorithms for the customer order scheduling problem with total completion time objective. Computers & Operations Research, 78, 181-192.
Framinan, J. M., & Perez-Gonzalez, P. (2018). Order scheduling with tardiness objective: Improved approximate solu-tions. European Journal of Operational Research, 266(3), 840-850.
Framinan, J. M., Perez-Gonzalez, P., & Fernandez-Viagas, V. (2019). Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures. European Journal of Oper-ational Research, 273(2), 401-417.
Julien, F. M., & Magazine, M. J. (1990). Scheduling customer orders: An alternative production scheduling approach. Journal of Manufacturing and Operations Management, 3(3), 177-199.
Lee, I. S. (2013). Minimizing total tardiness for the order scheduling problem. International Journal of Production Eco-nomics, 144(1), 128-134.
Leung, J. Y. T., Li, H., & Pinedo, M. (2005). Order scheduling in an environment with dedicated resources in parallel. Journal of Scheduling, 8(5), 355-386.
Lin, B. M., & Kononov, A. V. (2007). Customer order scheduling to minimize the number of late jobs. European Jour-nal of Operational Research, 183(2), 944-948.
Lin, W. C., Yin, Y., Cheng, S. R., Cheng, T. E., Wu, C. H., & Wu, C. C. (2017). Particle swarm optimization and oppo-site-based particle swarm optimization for two-agent multi-facility customer order scheduling with ready times. Ap-plied Soft Computing, 52, 877-884.
Prata, B. D. A., de Abreu, L. R., & Lima, J. Y. F. (2021). Heuristic methods for the single-machine scheduling problem with periodical resource constraints. Top, 29(2), 524-546.
de Athayde Prata, B., Rodrigues, C. D., & Framinan, J. M. (2021). Customer order scheduling problem to minimize makespan with sequence-dependent setup times. Computers & Industrial Engineering, 151, 106962.
de Athayde Prata, B., Rodrigues, C. D., & Framinan, J. M. (2022). A differential evolution algorithm for the customer order scheduling problem with sequence-dependent setup times. Expert Systems with Applications, 189, 116097.
Riahi, V., Newton, M. H., Polash, M. M. A., & Sattar, A. (2019). Tailoring customer order scheduling search algorithms. Computers & Operations Research, 108, 155-165.
Shi, Z., Wang, L., Liu, P., & Shi, L. (2015). Minimizing completion time for order scheduling: Formulation and heuris-tic algorithm. IEEE Transactions on Automation Science and Engineering, 14(4), 1558-1569.
Sung, C. S., & Yoon, S. H. (1998). Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines. International Journal of Production Economics, 54(3), 247-255.
Wagneur, E., & Sriskandarajah, C. (1993). Openshops with jobs overlap. European Journal of Operational Research, 71(3), 366-378.
Wang, G., & Cheng, T. E. (2007). Customer order scheduling to minimize total weighted completion time. Omega, 35(5), 623-626.
Xu, J., Wu, C. C., Yin, Y., Zhao, C., Chiou, Y. T., & Lin, W. C. (2016). An order scheduling problem with position-based learning effect. Computers & Operations Research, 74, 175-186.
Xu, X., Ma, Y., Zhou, Z., & Zhao, Y. (2013). Customer order scheduling on unrelated parallel machines to minimize to-tal completion time. IEEE Transactions on Automation Science and Engineering, 12(1), 244-257.
Yang, J., & Posner, M. E. (2005). Scheduling parallel machines for the customer order problem. Journal of Scheduling, 8(1), 49-74.