Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times

Wang, Li-Yan; Huang, Xue; Liu, Wei-Wei; Wu, Yu-Bin; Wang, Ji-Bo

doi:10.1051/ro/2020117

Wang, Li-Yan ; Huang, Xue ; Liu, Wei-Wei ; Wu, Yu-Bin ; Wang, Ji-Bo

RAIRO. Operations Research, Tome 55 (2021), pp. S2747-S2758

Résumé

In this study, we consider single-machine scheduling problems with past-sequence-dependent (denoted by psd) setup times in which the setup times of jobs are proportional to the length of already processed jobs. Under common (CON) and slack (SLK) due-date assignment methods, we prove that the weighted sum of earliness, tardiness and due-date minimization remains polynomially solvable. We also give some extensions for the scheduling problems with psd setup times.

MR

DOI : 10.1051/ro/2020117

Classification : 90B35
Keywords: Scheduling, single-machine, past-sequence-dependent setup times, position-dependent weights

@article{RO_2021__55_S1_S2747_0,
     author = {Wang, Li-Yan and Huang, Xue and Liu, Wei-Wei and Wu, Yu-Bin and Wang, Ji-Bo},
     title = {Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times},
     journal = {RAIRO. Operations Research},
     pages = {S2747--S2758},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020117},
     mrnumber = {4223180},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020117/}
}

TY  - JOUR
AU  - Wang, Li-Yan
AU  - Huang, Xue
AU  - Liu, Wei-Wei
AU  - Wu, Yu-Bin
AU  - Wang, Ji-Bo
TI  - Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S2747
EP  - S2758
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020117/
DO  - 10.1051/ro/2020117
LA  - en
ID  - RO_2021__55_S1_S2747_0
ER  -

%0 Journal Article
%A Wang, Li-Yan
%A Huang, Xue
%A Liu, Wei-Wei
%A Wu, Yu-Bin
%A Wang, Ji-Bo
%T Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times
%J RAIRO. Operations Research
%D 2021
%P S2747-S2758
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020117/
%R 10.1051/ro/2020117
%G en
%F RO_2021__55_S1_S2747_0

Wang, Li-Yan; Huang, Xue; Liu, Wei-Wei; Wu, Yu-Bin; Wang, Ji-Bo. Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times. RAIRO. Operations Research, Tome 55 (2021), pp. S2747-S2758. doi: 10.1051/ro/2020117

Bibliographie
Cité par

[1] A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs. Eur. J. Oper. Res. 246 (2015) 345–378. | MR | DOI

[2] A. Allahverdi, C. T. Ng, T. C. E. Cheng and M. Y. Kovalyov, A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187 (2008) 985–1032. | MR | Zbl | DOI

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

[4] D. Biskup and J. Herrmann, Single-machine scheduling against due dates with past-sequence-dependent setup times. Eur. J. Oper. Res. 191 (2008) 587–592. | MR | Zbl | DOI

[5] P. Brucker, Scheduling Algorithms, 3rd edition. Springer, Berlin-Heidelberg (2001). | MR | Zbl

[6] T. C. E. Cheng, W.-C. Lee and C.-C. Wu, Scheduling problems with deteriorating jobs and learning effects including proportional setup times. Comput. Ind. Eng. 58 (2010) 326–331. | DOI

[7] T. C. E. Cheng, W.-C. Lee and C.-C. Wu, Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times. Appl. Math. Model. 35 (2011) 1861–1867. | MR | Zbl | DOI

[8] P. Chrétienne, Minimizing the earliness and tardiness cost of a sequence of tasks on a single machine. RAIRO:OR 35 (2001) 165–187. | MR | Zbl | Numdam | DOI

[9] S. Gawiejnowicz, Time-Dependent Scheduling. Springer, Berlin-Heidelberg (2008). | MR | Zbl

[10] V. S. Gordon, J. M. Proth and C. B. Chu, A survey of the state of-the-art of common due date assignment and scheduling research. Eur. J. Oper. Res. 139 (2002) 1–25. | MR | Zbl | DOI

[11] V. S. Gordon, J. M. Proth and C. B. Chu, Due date assignment and scheduling: SLK, TWK and other due date assignment models. Prod. Plan. Control 13 (2002) 117–132. | DOI

[12] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Disc. Math. 5 (1979) 287–326. | MR | Zbl | DOI

[13] G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, 2nd edition. Cambridge University Press, Cambridge, UK (1967). | MR | Zbl

[14] C.-J. Hsu, W.-H. Kuo and D.-L. Yang, Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects. Appl. Math. Model. 35 (2011) 1492–1496. | MR | Zbl | DOI

[15] X. Huang, G. Li, Y. Huo and P. Ji, Single machine scheduling with general time-dependent deterioration, position-dependent learning and past sequence-dependent setup times. Optim. Lett. 7 (2013) 1793–1804. | MR | Zbl | DOI

[16] C. Koulamas and G. J. Kyparisis, Single-machine scheduling problems with past-sequence-dependent setup times. Eur. J. Oper. Res. 187 (2008) 1045–1049. | MR | Zbl | DOI

[17] C. Koulamas and G. J. Kyparisis, New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives. Eur. J. Oper. Res. 278 (2019) 149–159. | MR | DOI

[18] W.-H. Kuo and D.-L. Yang, Single-machine scheduling with past-sequence-dependent setup times and learning effects. Inf. Process. Lett. 102 (2007) 22–26. | MR | Zbl | DOI

[19] W.-H. Kuo, C.-J. Hsu and D.-L. Yang, Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects. Comput. Ind. Eng. 61 (2011) 179–183. | DOI

[20] S. D. Liman, S. S. Panwalkar and S. Thongmee, Common due window size and location determination in a single machine scheduling problem. J. Oper. Res. Soc. 49 (1998) 1007–1010. | Zbl | DOI

[21] H. Lin, C. He and Y. Lin, Bicriteria scheduling for due date assignment with total weighted tardiness. RAIRO:OR 52 (2018) 359–370. | MR | DOI

[22] W. Liu, X. Hu and X.-Y. Wang, Single machine scheduling with slack due dates assignment. Eng. Optim. 49 (2017) 709–717. | MR | DOI

[23] Y.-Y. Lu, G. Li, Y.-B. Wu and P. Ji, Optimal due-date assignment problem with learning effect and resource-dependent processing times. Optim. Lett. 8 (2014) 113–127. | MR | Zbl | DOI

[24] Y.-Y. Lu, F. Teng and Z.-X. Feng, Scheduling jobs with truncated exponential sum-of-logarithm-processing-times based and position-based learning effects. Asia Pac. J. Oper. Res. 32 (2015) 1550026. | MR | DOI

[25] V. Mani, P.-C. Chang and S.-H. Chen, Single-machine scheduling with past-sequence-dependent setup times and learning effects: a parametric analysis. Int. J. Syst. Sci. 42 (2011) 2097–2102. | MR | Zbl | DOI

[26] H. M. Soroush, Scheduling in bicriteria single machine systems with past-sequence-dependent setup times and learning effects. J. Oper. Res. Soc. 65 (2014) 1017–1036. | DOI

[27] L. Tai, Optimizing batch-processing operations with batch-position-based learning effects. To appear in: RAIRO:OR. DOI: (2021). | DOI | MR | Numdam

[28] J.-B. Wang, Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect. Comput. Ind. Eng. 55 (2008) 584–591. | DOI

[29] J.-B. Wang and J.-X. Li, Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects. Appl. Math. Model. 35 (2011) 1388–1395. | MR | Zbl | DOI

[30] J.-J. Wang and Y.-J. Liu, Single-machine bicriterion group scheduling with deteriorating setup times and job processing times. Appl. Math. Comput. 242 (2014) 309–314. | MR

[31] X.-R. Wang and J.-B. Wang, Scheduling with past-sequence-dependent setup times and learning effects on a single machine. Int. J. Adv. Manuf. Technol. 48 (2010) 739–746. | DOI

[32] X.-Y. Wang and J.-J. Wang, Scheduling problems with past-sequence-dependent setup times and general effects of deterioration and learning. Appl. Math. Model. 37 (2013) 4905–4914. | MR | DOI

[33] J.-B. Wang, D. Wang, L.-Y. Wang, L. Lin, N. Yin and W.-W. Wang, Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times. Comput. Math. App. 57 (2009) 9–16. | MR | Zbl

[34] X.-R. Wang, J. Jin, J.-B. Wang and P. Ji, Single machine scheduling with truncated job-dependent learning effect. Optim. Lett. 8 (2014) 669–677. | MR | Zbl | DOI

[35] J.-B. Wang, X.-N. Geng, L. Liu, J.-J. Wang and Y.-Y. Lu, Single machine CON/SLK due date assignment scheduling with controllable processing time and job-dependent learning effects. Comput. J. 61 (2018) 1329–1337. | MR | DOI

[36] J.-B. Wang, F. Liu and J.-J. Wang, Research on $m$ -machine flow shop scheduling with truncated learning effects. Int. Trans. Oper. Res. 26 (2019) 1135–1151. | MR | DOI

[37] J.-B. Wang, M. Gao, J.-J. Wang, L. Liu and H. He, Scheduling with a position-weighted learning effect and job release dates. Eng. Optim. 52 (2020) 1475–1493. | MR | DOI

[38] X. Xiong, D. Wang, T. C. E. Cheng, C. Wu and Y. Yin, Single-machine scheduling and common due date assignment with potential machine disruption. Int. J. Prod. Res. 56 (2018) 1345–1360. | DOI

[39] X. Zhang and Y. Wang, Single-machine scheduling CON/SLK due window assignment problems with sum-of-processed time based learning effect. Appl. Math. Comput. 250 (2015) 628–635. | MR

[40] X. Zhang, W. Lin, W. Wu and C. Wu, Single-machine common/slack due window assignment problems with linear decreasing processing times. Eng. Optim. 49 (2017) 1388–1400. | MR | DOI

Cité par Sources :