Parallel machine earliness and tardiness scheduling with proportional weights. (English) Zbl 1026.90042
Summary: In this paper we study the problem of scheduling \(n\) jobs with a common due date and proportional early and tardy penalties on \(m\) identical parallel machines. We show that the problem is NP-hard and propose a dynamic programming algorithm to solve it. We also propose two heuristics to tackle the problem and analyze their worst-case error bounds.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Arkin, E. M.; Roundy, R. O., Weighted-tardiness scheduling on parallel machines with proportional weights, Operations Research, 39, 64-81 (1991) · Zbl 0746.90030 |
| [2] | Szwarc, W.; Liu, J. J., Weighted tardiness single machine scheduling with proportional weights, Management Science, 57, 167-178 (1993) · Zbl 0783.90057 |
| [3] | Baker, K. R.; Scudder, G. D., Sequencing with earliness and tardiness penalties: a review, Operations Research, 38, 22-36 (1990) · Zbl 0699.90052 |
| [4] | Hall, N. G.; Posner, M. E., Earliness-tardiness scheduling problems. I: weighted deviation of completion times about a common due date, Operations Research, 39, 836-846 (1991) · Zbl 0749.90041 |
| [5] | Ahmed, M. U.; Sundararaghavan, P. S., Minimizing the weighted sum of late and early completion times in a single machine, IIE Transactions, 22, 288-290 (1990) |
| [6] | Hoogeveen, J. A.; van de Velde, S. L., Scheduling around a small common due date, European Journal of Operational Research, 55, 237-242 (1991) · Zbl 0755.90044 |
| [7] | Rachamadugu, R., Scheduling jobs with proportionate early/tardy penalties, IIE Transactions, 27, 679-682 (1995) |
| [8] | Alidaee, B.; Dragan, I., A note on minimizing the weighted sum of tardy and early completion penalties in a single machine: a case of small common due date, European Journal of Operational Research, 96, 559-563 (1997) · Zbl 0917.90182 |
| [9] | Alidaee, B., Minimizing absolute and squared deviation of completion times from due dates, Production and Operations Management, 3, 133-147 (1994) |
| [10] | Sundararaghavan, P. S.; Ahmed, M. U., Minimizing the sum of absolute lateness in single-machine and multimachine scheduling, Naval Research Logistics Quarterly, 31, 325-333 (1984) · Zbl 0544.90052 |
| [11] | Hall, N. G., Single- and multiple-processor models for minimizing completion time variance, Naval Research Logistics, 33, 49-54 (1986) · Zbl 0599.90057 |
| [12] | Emmons, H., Scheduling to a common due date on parallel common processors, Naval Research Logistics Quarterly, 34, 851-970 (1987) · Zbl 0648.90043 |
| [13] | Kubiak, W.; Low, S.; Sethi, S., Equivalence of mean flow time problems and mean absolute deviation problems, Operations Research Letters, 9, 371-374 (1990) · Zbl 0825.90553 |
| [14] | Federgruen, A.; Mosheiov, G., Heuristics for multi-machine scheduling problems with earliness and tardiness costs, Management Science, 42, 1544-1556 (1996) · Zbl 0879.90115 |
| [15] | Chen, Z.-. L.; Powell, W. B., A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem, European Journal of Operational Research, 116, 220-232 (1999) · Zbl 1009.90040 |
| [16] | Heady, R. B.; Zhu, Z., Minimizing the sum of job earliness and tardiness in a multimachine system, International Journal of Production Research, 36, 1619-1632 (1998) · Zbl 0940.90504 |
| [17] | Garey, M. R.; Johnson, D. S., Computers and intractability: a guide to the theory of NP-completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [18] | Chandra, A. K.; Wong, C. K., Worst-case analysis of a placement algorithm related to storage allocation, SIAM Journal on Computing, 4, 249-263 (1975) · Zbl 0315.68040 |
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.
