Near-optimal solutions and tight lower bounds for the parallel machines scheduling problem with learning effect

Hidri, Lotfi; Jemmali, Mahdi

RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 2, pp. 507-527.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

In this paper, the parallel machines scheduling problem with Dejong’s learning effect is addressed. The considered problem has a practical interest since it models real-world situations. In addition, this problem is a challenging one because of its NP-Hardness. In this work, a set of heuristics are proposed. The developed heuristics are categorized into two types. The first category is based on the dispatching methods, with new enhancement variants. The second type is more sophisticated and requires solving NP-Hard problems. Furthermore, several lower bounds are developed in order to assess the performance of the proposed heuristics. These lower bounds are based on solving the problem of the determination of the minimum average load under taking into account some observations. Among these observations, the existence of a limit position that the jobs are not allowed to exceed in any optimal schedule. Finally, an extensive experimental study is conducted over benchmark test problems, with up to 1500 jobs and 5280 instances. The obtained results are outperforming those proposed in the literature.

Classification : 90B35, 90C27, 90C59, 90C90
Mots-clés : Parallel machines, learning effect, lower bounds, heuristics

[1] M.J. Anzanello and F.S. Fogliatto, Learning curve models and applications: literature review and research directions. Int. J. Ind. Ergon. 41 (2011) 573–583. | DOI

[2] L. Argote, Organizational Learning: Creating, Retaining and Transferring Knowledge. Springer Science & Business Media (2012).

[3] R.G. Askin and J.B. Goldberg, Design and Analysis of Lean Production Systems. John Wiley & Sons (2007).

[4] A.B. Badiru, Computational survey of univariate and multivariate learning curve models. IEEE Trans. Eng. Manage. 39 (1992) 176–188. | DOI

[5] D. Biskup, A state-of-the-art review on scheduling with learning effects. Eur. J. Oper. Res. 188 (2008) 315–329. | DOI | MR | Zbl

[6] J. Carlier, F. Clautiaux and A. Moukrim, New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation. Comput. Oper. Res. 34 (2007) 2223–2250. | DOI | Zbl

[7] M. Drozdowski, Back to scheduling models. In: Scheduling for Parallel Processing. Springer (2009) 367–377. | DOI

[8] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Vol. 5 of Annals of Discrete Mathematics. Elsevier (1979) 287–326. | DOI | MR | Zbl

[9] M. Haouari and M. Jemmali, Tight bounds for the identical parallel machine-scheduling problem: part ii. Int. Trans. Oper. Res. 15 (2008) 19–34. | DOI | MR | Zbl

[10] X. Huang, M.Z. Wang and P. Ji, Parallel machines scheduling with deteriorating and learning effects. Optim. Lett. 8 (2014) 493–500. | DOI | MR | Zbl

[11] M. Ji, D. Yao, Q. Yang and T. Cheng, Machine scheduling with DeJong’s learning effect. Comput. Ind. Eng. 80 (2015) 195–200. | DOI

[12] M. Ji, X. Tang, X. Zhang and T.E. Cheng, Machine scheduling with deteriorating jobs and DeJong’s learning effect. Comput. Ind. Eng. 91 (2016) 42–47. | DOI

[13] Y.K. Lin, Scheduling identical jobs on uniform parallel machines under position-based learning effects. Arab. J. Sci. Eng. 39 (2014) 6567–6574. | DOI

[14] Y.Y. Lu, J. Jin, P. Ji and J.B. Wang, Resource-dependent scheduling with deteriorating jobs and learning effects on unrelated parallel machine. Neural Comput. Appl. 27 (2016) 1993–2000. | DOI

[15] K. Luo, A scheduling model with a more general function of learning effects. Comput. Ind. Eng. 82 (2015) 159–166. | DOI

[16] L.P. Michael, Scheduling: Theory, Algorithms, and Systems. Springer (2018).

[17] D. Okołowski and S. Gawiejnowicz, Exact and heuristic algorithms for parallel-machine scheduling with DeJong’s learning effect. Comput. Ind. Eng. 59 (2010) 272–279. | DOI

[18] S. Pakzad-Moghaddam, A Lévy flight embedded particle swarm optimization for multi-objective parallel-machine scheduling with learning and adapting considerations. Comput. Ind. Eng. 91 (2016) 109–128. | DOI

[19] M. Rostami, A.E. Pilerood and M.M. Mazdeh, Multi-objective parallel machine scheduling problem with job deterioration and learning effect under fuzzy environment. Comput. Ind. Eng. 85 (2015) 206–215. | DOI

[20] R. Rudek, Scheduling on parallel processors with varying processing times. Comput. Oper. Res. 81 (2017) 90–101. | DOI | MR | Zbl

[21] D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times. Disc. Appl. Math. 155 (2007) 1643–1666. | DOI | MR | Zbl

[22] C. Teplitz, The Learning Curve Deskbook: A Reference Guide to Theory, Calculations and Applications. Quorum Books, Westport, CT (1991).

[23] X.Y. Wang and J.J. Wang, Scheduling deteriorating jobs with a learning effect on unrelated parallel machines. Appl. Math. Model. 38 (2014) 5231–5238. | DOI | MR

[24] C. Wang, C. Liu, Z.H. Zhang and L. Zheng, Minimizing the total completion time for parallel machine scheduling with job splitting and learning. Comput. Ind. Eng. 97 (2016) 170–182. | DOI

[25] W.C. Yeh, P.J. Lai, W.C. Lee and M.C. Chuang, Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effects. Inf. Sci. 269 (2014) 142–158. | DOI | MR