×

A lower bound for weighted completion time variance. (English) Zbl 1206.90046

Summary: We consider a single machine scheduling problem to minimize the weighted completion time variance. This problem is known to be NP-hard. We propose a heuristic and a lower bound based on job splitting and the Viswanathkumar and Srinivasan procedure. The test on more than 2000 instances shows that this lower bound is very tight and the heuristic yields solutions very close to optimal ones since the gap between the solution given by the heuristic and the lower bound is very small.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Turki, U.; Fediki, C.; Andijani, A., Tabu search for a class of single-machine scheduling problems, Computers & Operations Research, 28, 1223-1230 (2001) · Zbl 1008.90020
[2] Badics, T.; Boros, E., Minimization of half-products, Mathematics of Operations Research, 23, 649-660 (1998) · Zbl 0977.90026
[3] Bagchi, U.; Sullivan, R. S.; Chang, Y. L., Minimizing mean squared deviation of completion times about a common due date, Management Science, 33, 894-906 (1987) · Zbl 0636.90049
[4] Cai, X., V-shape property for job sequences that minimize the expected completion time variance, European Journal of Operational Research, 91, 118-123 (1996) · Zbl 0947.90593
[5] Cai, X., Minimization of agreeably weighted variance in single machine systems, European Journal of Operational Research, 85, 576-592 (1995) · Zbl 0912.90172
[6] Cheng, J.; Kubiak, W., A half-product based approximation scheme for agreeably weighted completion time variance, European Journal of Operational Research, 162, 45-54 (2005) · Zbl 1132.90322
[7] Cheng, T.; Kovalyov, M. Y., Batch scheduling and common due-date assignment on a single machine, Discrete Applied Mathematics, 70, 231-245 (1996) · Zbl 0871.90044
[8] De, P.; Ghosh, J. B.; Wells, C. E., Scheduling to minimize the coefficient of variation, International Journal of Production Economics, 44, 249-253 (1996)
[9] De, P.; Ghosh, J. B.; Wells, C. E., On the minimization of completion time variance with a bicriteria extension, Operations Research, 40, 1148-1155 (1992) · Zbl 0770.90032
[10] Eilon, S.; Chowdhury, I. G., Minimizing waiting time variance in the single machine problem, Management Science, 23, 567-575 (1977) · Zbl 0362.90051
[11] Federgruen, A.; Mosheiov, G., Heuristics for multimachine scheduling problems with earliness and tardiness costs, Management Science, 42, 1544-1555 (1996) · Zbl 0879.90115
[12] Gupta, M. C.; Gupta, Y. P.; Bector, C. R., Minimizing the flow-time variance in single-machine systems, The Journal of the Operational Research Society, 41, 767-779 (1990) · Zbl 0725.90039
[13] Hall, N. G.; Kubiak, W., Proof of a conjecture of schrage about the completion time variance problem, Operations Research Letters, 10, 467-472 (1991) · Zbl 0751.90037
[14] Kanet, J. J., Minimizing variation of flow time in single machine systems, Management Science, 27, 1453-1459 (1971) · Zbl 0473.90048
[15] Kubiak, W.; Cheng, J.; Kovalyov, M. Y., Fast fully polynomial approximation schemes for minimizing completion time variance, European Journal of Operational Research, 137, 303-309 (2002) · Zbl 0998.90038
[16] Kubiak, W., New result on the completion time variance minimization, Discrete Applied Mathematics, 58, 157-168 (1995) · Zbl 0833.90070
[17] Kubiak, W., Completion time variance minimization on a single machine is difficult, Operations Research Letters, 14, 49-59 (1993) · Zbl 0794.90024
[18] Li, X.; Ye, N.; Liu, T.; Sun, Y., Job scheduling to minimize the weighted waiting time variance of jobs, Computers & Industrial Engineering, 52, 41-56 (2007)
[19] Manna, D. K.; Prasad, V. R., Bounds for the position of the smallest job in completion time variance minimization, European Journal of Operational Research, 114, 411-419 (1999) · Zbl 0935.90014
[20] Manna, D. K.; Prasad, V. R., Pseudopolynomial algorithms for CTV minimization in single machine scheduling, Computers & Operations Research, 24, 1119-1128 (1997) · Zbl 0893.90092
[21] Merten, A. G.; Muller, M. E., Variance minimization in single machine sequencing problems, Management Science, 18, 518-528 (1972) · Zbl 0254.90040
[22] Mittenthal, J.; Raghavachari, M.; Rana, A., V- and a-shaped properties for optimal single machine schedules for a class of nonseparable penalty functions, European Journal of Operational Research, 86, 262-269 (1995) · Zbl 0906.90091
[23] Schrage, L., Minimizing the time-in-system variance for a finite jobset, Management Science, 21, 540-543 (1975) · Zbl 0302.90021
[24] Viswanathkumar, C.; Srinivasan, C., A branch and bound algorithm to minimize completion time variance on a single processor, Computers & Operations Research, 30, 1135-1150 (2003) · Zbl 1049.90028
[25] Ye, N.; Li, X.; Farley, T.; Xu, X., Job scheduling methods for reducing waiting time variance, Computers & Operations Research, 34, 3069-3083 (2007) · Zbl 1185.90104
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.