×

Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time. (English) Zbl 1252.90024

Summary: C.-L. Zhao, H.-Y. Tang and C.-D. Cheng [Eur. J. Oper. Res. 198, No. 1, 354–357 (2009; Zbl 1163.90518)] studied the \(m\) identical parallel-machine scheduling problem with rate-modifying activities to minimize the total completion time. They show that the problem can be solved in \(O(n^{2m+3})\) time. In this study, we extend the scheduling environment to the unrelated parallel-machine setting and present a more efficient algorithm to solve the extended problem. For the cases in which the rate-modifying rate is (i) larger than 0 and not larger than 1 and (ii) larger than 0, we show that the problem can be solved in \(O(n^{m+3})\) and \(O(n^{2m+2})\) time, respectively.

MSC:

90B35 Deterministic scheduling theory in operations research

Citations:

Zbl 1163.90518
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Biskup, D., A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188, 315-329 (2008) · Zbl 1129.90022
[2] Cheng, T. C.E.; Wu, C.-C.; Lee, W.-C., Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects, Information Sciences, 178, 2476-2487 (2008) · Zbl 1172.90397
[3] Cheng, T. C.E.; Lai, P.-J.; Wu, C.-C.; Lee, W.-C., Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations, Information Sciences, 179, 3127-3135 (2009) · Zbl 1170.90387
[4] Gordon, V. S.; Tarasevich, A. A., A note: common due date assignment for a single machine scheduling with the rate-modifying activity, Computers & Operations Research, 36, 325-328 (2009) · Zbl 1163.90488
[5] Gupta, J. N.D.; Gupta, S. K., Single facility scheduling with nonlinear processing times, Computers & Industrial Engineering, 14, 387-393 (1988)
[6] Kunnathur, A. S.; Gupta, S. K., Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European Journal of Operational Research, 47, 56-64 (1990) · Zbl 0717.90034
[7] Kuo, W. H.; Yang, D. L., Note on “single-machine and flowshop scheduling with a general learning effect model” and “some single-machine and m-machine flowshop scheduling problems with learning considerations”, Information Sciences, 180, 3814-3816 (2010) · Zbl 1194.90041
[8] Lee, C. Y.; Leon, V. J., Machine scheduling with a rate-modifying activity, European Journal of Operational Research, 129, 119-128 (2001) · Zbl 0983.90020
[9] Lee, C. Y.; Lin, C. S., Single-machine scheduling with maintenance and repair rate-modifying activities, European Journal of Operational Research, 135, 493-513 (2001) · Zbl 0989.90036
[10] Lee, W. C.; Lai, P. J., Scheduling problems with general effects of deterioration and learning, Information Sciences, 181, 1164-1170 (2011) · Zbl 1208.90072
[11] Lee, W. C.; Wu, C. C., Some single-machine and m-machine flowshop scheduling problems with learning considerations, Information Sciences, 179, 3885-3892 (2009) · Zbl 1179.90141
[12] Li, C. L., Viewpoints: a note on unrelated parallel machine scheduling with time-dependent processing times, Journal of Operational Research Society, 59, 1696-1697 (2008) · Zbl 1155.90388
[13] Lodree, E. J.; Geiger, C. D., A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration, European Journal of Operational Research, 201, 644-648 (2010) · Zbl 1192.90076
[14] Ma, Y.; Chu, C. B.; Zuo, C. R., A survey of scheduling with deterministic machine availability constraints, Computers & Industrial Engineering, 58, 199-211 (2010)
[15] Mosheiov, G., Λ-shaped policies for schedule deteriorating jobs, Journal of the Operational Research Society, 47, 1184-1191 (1996) · Zbl 0869.90039
[16] Mosheiov, G.; Sidney, J. B., New results on sequencing with rate modification, INFOR, 41, 155-163 (2004) · Zbl 07682299
[17] Mosheiov, G.; Oron, D., Due-date assignment and maintenance activity scheduling problem, Mathematical and Computer Modelling, 44, 1053-1057 (2006) · Zbl 1161.90397
[18] Mosheiov, G.; Sarig, A., Scheduling a maintenance activity and due-window assignment on a single machine, Computers & Operations Research, 36, 2541-2545 (2009) · Zbl 1179.90146
[19] Mott, J. L.; Kandel, A.; Baker, T. P., Discrete Mathematics for Computer Scientists & Mathematicians (1986), Prentice-Hall: Prentice-Hall New Jersey
[20] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2002), Prentice-Hall: Prentice-Hall New Jersey · Zbl 1145.90394
[21] Schmidt, G., Scheduling with limited machine availability, European Journal of Operational Research, 121, 1-15 (2000) · Zbl 0959.90023
[22] Yin, Y. Q.; Xu, D. H.; Sun, K. B.; Li, H. X., Some scheduling problems with general position-dependent and time-dependent learning effects, Information Sciences, 179, 2416-2425 (2009) · Zbl 1166.90342
[23] Yin, Y. Q.; Xu, D. H.; Huang, X. K., Notes on “some single-machine scheduling problems with general position-dependent and time-dependent learning effects”, Information Sciences, 181, 2209-2217 (2011) · Zbl 1231.90223
[24] Zhao, C. L.; Tang, H. Y.; Cheng, C. D., Two-parallel machines scheduling with rate-modifying activities to minimize total completion time, European Journal of Operational Research, 198, 354-357 (2009) · Zbl 1163.90518
[25] Zhao, C. L.; Tang, H. Y., A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity, Computers & Operations Research (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.