no. 3
Single machine group scheduling problem with makespan objective and a proportional linear shortening
RAIRO. Operations Research, Tome 56 (2022) no. 3, pp. 1523-1532

This paper considers a group scheduling problem with shorten (i.e., a proportional linear shortening) job processing times and ready times on a single machine. If the jobs are in the same group, they have independent and constant ready times. The setup time of a group is independent constant setup time between each group. The goal is to determine the optimal group sequence and the job sequence within the groups such that the makespan (i.e., the maximum completion time) is minimized. For the general case of the problem, an initial heuristic algorithm (an upper bound) and some lower bounds are proposed, and then a branch-and-bound algorithm can be developed to solve the problem.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2022078
Classification : 90B35
Keywords: scheduling, group technology, shortening job processing times, branch-and-bound algorithm 
@article{RO_2022__56_3_1523_0,
     author = {Wang, Ji-Bo and Jia, Xue and Yan, Jia-Xuan and Wang, Si-Han and Qian, Jin},
     title = {Single machine group scheduling problem with makespan objective and a proportional linear shortening},
     journal = {RAIRO. Operations Research},
     pages = {1523--1532},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {3},
     doi = {10.1051/ro/2022078},
     mrnumber = {4440013},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022078/}
}
TY  - JOUR
AU  - Wang, Ji-Bo
AU  - Jia, Xue
AU  - Yan, Jia-Xuan
AU  - Wang, Si-Han
AU  - Qian, Jin
TI  - Single machine group scheduling problem with makespan objective and a proportional linear shortening
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 1523
EP  - 1532
VL  - 56
IS  - 3
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022078/
DO  - 10.1051/ro/2022078
LA  - en
ID  - RO_2022__56_3_1523_0
ER  - 
%0 Journal Article
%A Wang, Ji-Bo
%A Jia, Xue
%A Yan, Jia-Xuan
%A Wang, Si-Han
%A Qian, Jin
%T Single machine group scheduling problem with makespan objective and a proportional linear shortening
%J RAIRO. Operations Research
%D 2022
%P 1523-1532
%V 56
%N 3
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022078/
%R 10.1051/ro/2022078
%G en
%F RO_2022__56_3_1523_0
Wang, Ji-Bo; Jia, Xue; Yan, Jia-Xuan; Wang, Si-Han; Qian, Jin. Single machine group scheduling problem with makespan objective and a proportional linear shortening. RAIRO. Operations Research, Tome 56 (2022) no. 3, pp. 1523-1532. doi: 10.1051/ro/2022078

[1] B. Alidaee and N. K. Womer, Scheduling with time dependent processing times: Review and extensions. J. Oper. Res. Soc. 50 (1999) 711–720. | Zbl | DOI

[2] A. Azzouz, M. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography. Int. J. Prod. Res. 56 (2018) 1642–1661. | DOI

[3] J. Bai, Z. R. Li and X. Huang, Single-machine group scheduling with general deterioration and learning effects. Appl. Math. Model. 36 (2012) 1267–1274. | MR | Zbl | DOI

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

[5] T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. 152 (2004) 1–13. | MR | Zbl | DOI

[6] J. M. Framinan and R. Leisten, An efficient constructive heuristic for flowtime minimization in permutation flow shops. Omega 31 (2003) 311–317. | DOI

[7] S. Gawiejnowicz, Models and Algorithms of Time-Dependent Scheduling. Springer, Berlin (2020). | MR | Zbl | DOI

[8] K. I.-J. Ho, J. Y.-T. Leung and W.-D. Wei, Complexity of scheduling tasks with time-dependent execution times. Inf. Process. Lett. 48 (1993) 315–320. | MR | Zbl | DOI

[9] X. Huang, N. Yin, W.-W. Liu and J.-B. Wang, Common due window assignment scheduling with proportional linear deterioration effects. Asia-Pac. J. Oper. Res. 37 (2020) 1950031. | MR | Zbl | DOI

[10] P. Ji and L. Li, Single-machine group scheduling problems with variable job processing times. Math. Prob. Eng. 2015 (2015) 758919 (9 pages). | MR | Zbl

[11] T. Keshavarz, M. Savelsbergh and N. Salmasi, A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties. Appl. Math. Model. 39 (2015) 6410–6424. | MR | Zbl | DOI

[12] L. Li and J.-J. Wang, Scheduling jobs with deterioration effect and controllable processing time. Neural Comput. App. 29 (2018) 1163–1170. | DOI

[13] S.-S. Lin, A note on parallel-machine scheduling with controllable processing times and job-dependent learning effects. RAIRO-Oper. Res. 55 (2021) 561–569. | MR | Zbl | Numdam | DOI

[14] F. Liu, J. Yang and Y.-Y. Lu, Solution algorithms for single-machine group scheduling with ready times and deteriorating jobs. Eng. Optim. 51 (2019) 862–874. | MR | DOI

[15] Y.-Y. Lu, J.-J. Wang and J.-B. Wang, Single machine group scheduling with decreasing time-dependent processing times subject to release dates. Appl. Math. Comput. 234 (2014) 286–292. | MR | Zbl

[16] 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. App. 27 (2016) 1993–2000. | DOI

[17] Y.-Y. Lu, J.-B. Wang, P. Ji and H. He, A note on resource allocation scheduling with group technology and learning effects on a single machine. Eng. Optim. 49 (2017) 1621–1632. | MR | DOI

[18] J. S. Neufeld, J. N. D. Gupta and U. Buscher, A comprehensive review of flowshop group scheduling literature. Comput. Oper. Res. 70 (2016) 56–74. | MR | Zbl | DOI

[19] C. N. Potts and L. N. Van Wassenhove, Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. J. Oper. Res. Soc. 43 (1992) 395–406. | Zbl | DOI

[20] J.-B. Wang and L.-Y. Sun, Single-machine group scheduling with decreasing linear deterioration setup times and job processing times. Int. J. Adv. Manuf. Technol. 49 (2010) 765–772. | DOI

[21] J.-B. Wang and J.-J. Wang, Single machine group scheduling with time dependent processing times and ready times. Inf. Sci. 275 (2014) 226–231. | MR | Zbl | DOI

[22] J.-B. Wang and Z.-Q. Xia, Scheduling jobs under decreasing linear deterioration. Inf. Process. Lett. 94 (2005) 63–69. | MR | Zbl | DOI

[23] J.-B. Wang, A.-X. Guo, F. Shan, B. Jiang and L.-Y. Wang, Single machine group scheduling under decreasing linear deterioration. J. Appl. Math. Comput. 24 (2007) 283–293. | MR | Zbl | DOI

[24] J.-B. Wang, L. Lin and F. Shan, Single-machine group scheduling problems with deteriorating jobs. Int. J. Adv. Manuf. Technol. 39 (2008) 808–812. | DOI

[25] J.-B. Wang, X. Huang, Y.-B. Wu and P. Ji, Group scheduling with independent setup times, ready times, and deteriorating job processing times. Int. J. Adv. Manuf. Technol. 60 (2012) 643–649. | DOI

[26] D. Wang, Y. Huo and P. Ji, Single-machine group scheduling with deteriorating jobs and allotted resource. Optim. Lett. 8 (2014) 591–605. | MR | Zbl | DOI

[27] Z. Wang, C.-M. Wei and Y.-Y. Lu, Permutation flow shop problem with shortening job processing times. Asia-Pac. J. Oper. Res. 33 (2016) 1650032 (14 pages). | MR | Zbl | DOI

[28] J.-B. Wang, L. Liu, J.-J. Wang and L. Li, Makenspan minimization scheduling with ready times, group technology and shortening job processing times. Comput. J. 61 (2018) 1422–1428. | MR | DOI

[29] L.-Y. Wang, X. Huang, W.-W. Liu, Y.-B. Wu and J.-B. Wang, Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times. RAIRO-Oper. Res. 55 (2021) S2747–S2758. | MR | Zbl | Numdam | DOI

[30] Y.-T. Xu, Y. Zhang and X. Huang, Single-machine ready times scheduling with group technology and proportional linear deterioration. Appl. Math. Model. 38 (2014) 384–391. | Zbl | MR | DOI

Cité par Sources :