Composite heuristics and water wave optimality algorithms for tri-criteria multiple job classes and customer order scheduling on a single machine

Li, L.; Lin, W.; Bai, D.; Zhang, X.; Azzouz, A.; Cheng, S.; Wu, Y.; Wu, C.

Abstract: Among the well-known scheduling problems, the customer order scheduling problem (COSP) has always been of great importance in manufacturing. To reflect the reality of COSPs as much as possible, this study considers that jobs from different orders are classified in various classes. This paper addresses a tri-criteria single-machine scheduling model with multiple job classes and customer orders on which the measurement minimizes a linear combination of the sum of the ranges of all orders, the tardiness of all orders, and the total completion times of all jobs. Due to the NP-hard complexity of the problem, a lower bound and a property are developed and utilized in a branch-and-bound for solving an exact solution. Afterward, four heuristics with three local improved searching methods each and a water wave optimality algorithm with four variants of wavelengths are proposed. The tested outputs report the performances of the proposed methods.

How to cite this paper

 Li, L., Lin, W., Bai, D., Zhang, X., Azzouz, A., Cheng, S., Wu, Y & Wu, C. (2023). Composite heuristics and water wave optimality algorithms for tri-criteria multiple job classes and customer order scheduling on a single machine.International Journal of Industrial Engineering Computations , 14(2), 265-274.

References

Allahverdi, A., & Soroush, H. M. (2008). The significance of reducing setup times/setup costs. European Journal of Operational Research, 187(3), 978-984.
Allahverdi, A., Ng, C. T., Cheng, T. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European journal of operational research, 187(3), 985-1032.
Allahverdi, A. (2015). The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, 246(2), 345-378.
Allahverdi, A., Gupta, J. N., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, 27(2), 219-239.
Cheng, T.C.E., Gupta, J.N.D., & Wang, G. (2000). A review of flowshop scheduling research with setup times. Production and Operations Management, 9(3), 262–282.
de Athayde Prata, B., Rodrigues, C. D., & Framinan, J. M. (2021a). 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. (2021b). A differential evolution algorithm for the customer order scheduling problem with sequence-dependent setup times. Expert Systems with Applications, 116097.
Della Croce, F., Narayan, V., & Tadei, R. (1996). The two-machine total completion time flow shop problem. European Journal of Operational Research, 90, 227–237.
Erel, E., & Ghosh, J. B. (2007). Customer order scheduling on a single machine with family setup times: Complexity and algorithms. Applied Mathematics and Computation, 185, 11–18.
Fisher, M. L. (1976). A dual algorithm for the one-machine scheduling problem. Mathematical Programming, 11(1), 229–251.
Framinan, J. M., & Perez-Gonzalez, P. (2018). Order scheduling with tardiness objective: Improved approximate solutions. European Journal of Operational Research, 266(3), 840–850.
Gupta, J. N., Ho, J. C., & van der Veen, J. A. (1997). Single machine hierarchical scheduling with customer orders and multiple job classes. Annals of Operations Research, 70, 127–143.
Hazır, Ö., Günalay, Y., & Erel, E. (2008). Customer order scheduling problem: a comparative metaheuristics study. The International Journal of Advanced Manufacturing Technology, 37(5-6), 589–598.
Holland, M. D., Wolfe, A., & Chicken, E. (2014). Nonparametric Statistical Methods, 3rd edition. Wiley, Hoboken.
Julien, F. M., & Magazine, M. J. (1990). Scheduling customer orders: An alternative production scheduling approach. Journal of Manufacturing and Operations Management, 3, 177–199.
Liaee, M. M., & Emmons, H. (1997). Scheduling families of jobs with setup times. International Journal of Production Economics, 51(3), 165–176.
Su, L. H., Chen, P. S., & Chen, S. Y. (2013). Scheduling on parallel machines to minimize maximum lateness for the customer order problem. International journal of systems science, 44(5), 926–936.
Wu, C. C., Lin, W. C., Zhang, X., Chung, I. H., Yang, T. H., & Lai, K. (2019). Tardiness minimisation for a customer order scheduling problem with sum-of-processing-time-based learning effect. Journal of the Operational Research Society, 70(3), 487–501.
Yang, W. H., & Liao, C.J. (1999). Survey of scheduling research involving setup times. International Journal of Systems Science, 30(2), 143–155.
Zhao, F., Liu, H., Zhang, Y., Mac, W., & Zhang, C. (2018) A discrete Water Wave Optimization algorithm for no-wait flow shop scheduling problem. Expert Systems with Applications, 91, 347–363.
Zheng, Y. J. (2015). Water wave optimization: A new nature-inspired metaheuristic. Computers and Operations Research, 55(1), 1–11.
Zheng, Y. J., Lu, X. Q., Du, Y. C., Xue, Y., & Sheng, W. G. (2019). Water wave optimization for combinatorial optimization: Design strategies and applications. Applied Soft Computing, 83, 105611.