×

Total absolute deviation of job completion times on uniform and unrelated machines. (English) Zbl 1201.90083

Summary: Unlike other measures of variation of job completion times considered in scheduling literature, the measure of minimizing total absolute deviation of job completion times (TADC) was shown to have a polynomial time solution on a single machine. It was recently shown to remain polynomially solvable when position-dependent job processing times are assumed. In this paper we further extend these results, and show that minimizing TADC remains polynomial when position-dependent processing times are assumed (i) on uniform and unrelated machines and (ii) for a bicriteria objective consisting of a linear combination of total job completion times and TADC. These extensions are shown to be valid also for the measure of total absolute differences of job waiting times (TADW).

MSC:

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

References:

[1] Kanet, J., Minimizing variation of flow time in single machine systems, Management Science, 27, 1453-1459 (1981) · Zbl 0473.90048
[2] Kubiak, W., Completion time variance minimization is difficult, Operations Research Letters, 14, 49-59 (1993) · Zbl 0794.90024
[3] Hall, N.; Kubiak, W.; Sethi, S. P., Earliness-tardiness scheduling problems II: deviation of completion times about a restrictive common due-date, Operations Research, 39, 847-856 (1991) · Zbl 0762.90037
[4] Oron, D., Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times, Computers and Operations Research, 35, 2071-2078 (2008) · Zbl 1139.90012
[5] Li, Y.; Li, G.; Sun, L.; Xu, Z., Single machine scheduling of deteriorating jobs to minimize total absolute differences in completion times, International Journal of Production Economics, 118, 424-429 (2009)
[6] Mosheiov, G., Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines, Journal of the Operational Research Society, 59, 1422-1424 (2008) · Zbl 1155.90392
[7] Kuo, W. H.; Yang, D. L., Single machine scheduling with past-sequence-dependent setup times and learning effects, Information Processing Letters, 102, 22-26 (2007) · Zbl 1184.68132
[8] Koulamas, C.; Kyparisis, G. J., Single machine scheduling problems with past-sequence-dependent setup times, European Journal of Operational Research, 187, 1045-1049 (2008) · Zbl 1137.90498
[9] Kuo, W. H.; Yang, D. L., Some scheduling problems with deteriorating jobs and learning effects, Computers & Industrial Engineering (2009)
[10] Yang DL, Kuo WH. Single machine scheduling with both deterioration and learning effects. Annals of Operations Research 2009;172:315-327, doi:10.1007/S10479-009-0615-3; Yang DL, Kuo WH. Single machine scheduling with both deterioration and learning effects. Annals of Operations Research 2009;172:315-327, doi:10.1007/S10479-009-0615-3 · Zbl 1181.90131
[11] Ganesan, V. K.; Sivakumar, A. L., Scheduling in static jobshops for minimizing mean flowtime subject to minimum totaö deviation of job completion times, International Journal of Production Economics, 103, 633-647 (2006)
[12] Wang, J. B.; Xia, Z. Q., Single machine scheduling problems with controllable processing times and total absolute differences penalties, European Journal of Operational Research, 177, 638-645 (2007) · Zbl 1109.90045
[13] Wang JB, Gao WJ, Huang X. Scheduling with past-sequence-dependent setup times and learning effects on a single machine. International Journal of Advanced Manufacturing Technology 2009;48:739-746, doi:10.1007/S00170-009-2308-0; Wang JB, Gao WJ, Huang X. Scheduling with past-sequence-dependent setup times and learning effects on a single machine. International Journal of Advanced Manufacturing Technology 2009;48:739-746, doi:10.1007/S00170-009-2308-0
[14] Bagchi, U., Simultaneous minimization of mean and variation of flow time and waiting time in single machine systems, Operations Research, 37, 118-125 (1989) · Zbl 0661.90046
[15] Stirzaker, D., Elementary probability (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0784.60002
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.