×

Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties. (English) Zbl 1211.90085

Summary: In this paper we consider parallel identical machines scheduling problems with deteriorating jobs. In this model, job processing times are defined by functions of their starting times. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remains polynomially solvable under the proposed model.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alidaee, B.; Womer, N. K., Scheduling with time dependent processing times: review and extensions, J. Oper. Res. Soc., 50, 711-720 (1999) · Zbl 1054.90542
[2] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, Eur. J. Oper. Res., 152, 1-13 (2004) · Zbl 1030.90023
[3] Cheng, T. C.E.; Kang, L.; Ng, C. T., Due-date assignment and single machine scheduling with deteriorating jobs, J. Oper. Res. Soc., 55, 198-203 (2004) · Zbl 1095.90036
[4] Cheng, T. C.E.; Kang, L.; Ng, C. T., Single machine due-date scheduling of jobs with decreasing start-time dependent processing times, Int. Trans. Oper. Res., 12, 355-366 (2005) · Zbl 1131.90355
[5] Cheng, T. C.E.; Kang, L. Y.; Ng, C. T., Due-date assignment and parallel-machine scheduling with deteriorating jobs, J. Oper. Res. Soc., 58, 1103-1108 (2007) · Zbl 1278.90145
[6] Wang, J.-B.; Xia, Z.-Q., Scheduling jobs under decreasing linear deterioration, Inf. Process. Lett., 94, 63-69 (2005) · Zbl 1182.68359
[7] Wang, J.-B.; Xia, Z.-Q., Flow shop scheduling with deteriorating jobs under dominating machines, Omega, 34, 327-336 (2006) · Zbl 1090.90095
[8] Wang, J.-B.; Xia, Z.-Q., Flow shop scheduling problems with deteriorating jobs under dominating machines, J. Oper. Res. Soc., 57, 220-226 (2006) · Zbl 1090.90095
[9] Janiak, A.; Kovalyov, M. Y., Scheduling in a contaminated area: a model and polynomial algorithms, Eur. J. Oper. Res., 173, 125-132 (2006) · Zbl 1125.90354
[10] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Pareto and scalar bicriterion optimization in scheduling deteriorating jobs, Comput. Oper. Res., 33, 746-767 (2006) · Zbl 1116.90045
[11] Gawiejnowicz, S., Scheduling deteriorating jobs subject to job or machine availability constraints, Eur. J. Oper. Res., 180, 472-478 (2007) · Zbl 1114.90034
[12] Kang, L.; Ng, C. T., A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs, Int. J. Prod. Econ., 109, 180-184 (2007)
[13] Wang, J.-B., Flow shop scheduling problems with decreasing linear deterioration under dominating machines, Comput. Oper. Res., 34, 2043-2058 (2007) · Zbl 1193.90116
[14] Wu, C.-C.; Lee, W.-C.; Shiau, Y.-R., Minimizing the total weighted completion time on a single machine under linear deterioration, Int. J. Adv. Manuf. Technol., 33, 1237-1243 (2007)
[15] Wu, C.-C.; Shiau, Y.-R.; Lee, W.-C., Single-machine group scheduling problems with deterioration consideration, Computers and Operations Research, 35, 1652-1659 (2008) · Zbl 1211.90094
[16] Kuo, W.-H.; Yang, D.-L., A note on due-date assignment and single-machine scheduling with deteriorating jobs, J. Oper. Res. Soc., 59, 857-859 (2008) · Zbl 1153.90427
[17] Oron, D., Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times, Comput. Oper. Res., 35, 2071-2078 (2008) · Zbl 1139.90012
[18] Wang, J.-B.; Lin, L.; Shan, F., Single machine group scheduling problems with deteriorating jobs, Int. J. Adv. Manuf. Technol., 39, 808-812 (2008)
[19] Wang, J.-B., Single machine scheduling with a time-dependent learning effect and deteriorating jobs, J. Oper. Res. Soc., 60, 583-586 (2009) · Zbl 1163.90515
[20] Wang, J.-B.; Jiang, Y.; Wang, G., Single machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning, Int. J. Adv. Manuf. Technol., 41, 1221-1226 (2009)
[21] Kuo, W.-H.; Hsu, C.-J.; Yang, D.-L., A note on unrelated parallel machine scheduling with time-dependent processing times, J. Oper. Res. Soc., 60, 431-434 (2009) · Zbl 1156.90366
[22] Lee, W.-C.; Wu, C.-C.; Chung, Y.-H.; Liu, H.-C., Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates, Comput. Oper. Res., 36, 2111-2121 (2009) · Zbl 1179.90142
[23] Cheng, T. C.E.; Lee, W.-C.; Wu, C.-C., Single-machine scheduling with deteriorating functions for job processing times, Appl. Math. Modell., 34, 4171-4178 (2010) · Zbl 1201.90073
[24] Wang, J.-B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Appl. Math. Modell., 34, 309-313 (2010) · Zbl 1185.90099
[25] Wei, C.-M.; Wang, J.-B., Single machine quadratic penalty function scheduling with deteriorating jobs and group technology, Appl. Math. Modell., 34, 3642-3647 (2010) · Zbl 1201.90090
[26] Lee, W. C.; Wang, W. J.; Shiau, Y. R.; Wu, C. C., A single-machine scheduling problem with two-agent and deteriorating jobs, Appl. Math. Modell. (2010)
[27] Sun, L.-H.; Sun, L.-Y.; Wang, J.-B., Single-machine scheduling to minimize total absolute differences in waiting times under simple linear deterioration, J. Oper. Res. Soc. (2010)
[28] Wang, J.-B.; Wang, J.-J.; Ji, P., Scheduling jobs with chain precedence constraints and deteriorating jobs, J. Oper. Res. Soc. (2010)
[29] Merten, A. G.; Muller, M. E., Variance minimization in single machine sequencing problems, Manage. Sci., 18, 518-528 (1972) · Zbl 0254.90040
[30] Schrage, L., Minimizing the time-in-system variance for a finite jobset, Manage. Sci., 21, 540-543 (1975) · Zbl 0302.90021
[31] Eilon, S.; Chowdhury, I. E., Minimizing waiting time variance in the single machine problem, Manage. Sci., 23, 567-575 (1977) · Zbl 0362.90051
[32] Vani, V.; Raghavachari, M., Deterministic and random single machine sequencing with variance minimization, Oper. Res., 35, 111-120 (1987) · Zbl 0616.90027
[33] Kanet, J. J., Minimizing variation of flow time in single machine systems, Manage. Sci., 27, 12, 1453-1459 (1981) · Zbl 0473.90048
[34] Bagchi, U. B., Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems, Oper. Res., 37, 118-125 (1989) · Zbl 0661.90046
[35] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[36] Hardy, G. H.; Littlewood, J. E.; Polya, G., Inequalities (1967), Cambridge University Press · Zbl 0634.26008
[37] Stirzaker, D., Elementary Probability (1995), Cambridge University Press: Cambridge University Press Cambridge
[38] Mosheiov, G., Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines, J. Oper. Res. Soc., 59, 1422-1424 (2008) · Zbl 1155.90392
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.