Minimizing total tardiness on a single machine with controllable processing times. (English) Zbl 1179.90159
Summary: The concept of time-cost trade-off is commonly considered in PERT/CPM, but it is seldom considered in the scheduling area. Such concept implies that the processing times of jobs are controllable by increasing or decreasing the available resources, such as manpower and equipment. In this paper, we focus on the single machine total tardiness problem with controllable processing times. First, a mixed-integer programming (MIP) model is formulated to find the optimal solution. Then, we propose both a linear programming model and a net benefit of compression (NBC) algorithm to obtain a set of optimal amounts of compression for a given sequence. To solve medium- to large-size problem instances, we develop a heuristic based on the NBC algorithm. To verify the proposed heuristic, the MIP model is used as a comparison for small-size problem instances, whereas for medium- to large-size instances the variable neighborhood search, a useful local search method, is employed. Computational results show that the proposed heuristic has a good performance.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Sen, T.; Gupta, S. K., A state-of-art survey of static scheduling research involving due dates, OMEGA, The International Journal of Management Science, 12, 63-76 (1984) |
| [2] | Abdul-Razaq, T. S.; Potts, C. N.; Van Wassenhove, L. N., A survey of algorithms for the single machine total weighted tardiness scheduling problem, Discrete Applied Mathematics, 26, 235-253 (1990) · Zbl 0685.90059 |
| [3] | Koulamas, K., The total tardiness problem: review and extensions, Operations Research, 42, 1025-1041 (1994) · Zbl 0824.90083 |
| [4] | Nowicki, E.; Zdrzałka, S., A survey of results for sequencing problems with controllable processing times, Discrete Applied Mathematics, 26, 271-287 (1990) · Zbl 0693.90056 |
| [5] | Wang, X.; Cheng, T. C.E., Single machine scheduling with resource dependent release times and processing times, European Journal of Operational Research, 162, 727-739 (2005) · Zbl 1065.90045 |
| [6] | Vickson, R. G., Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine, Operations Research, 28, 1155-1167 (1980) · Zbl 0449.90054 |
| [7] | Vickson, R. G., Two single machine sequencing problems involving controllable job processing times, AIIE Transaction, 12, 258-262 (1980) |
| [8] | Van Wassenhove, L. N.; Baker, K. R., A bicriterion approach to time/cost trade-offs in sequence, European Journal of Operational Research, 11, 48-54 (1982) · Zbl 0482.90043 |
| [9] | Daniels, R. L.; Sarin, R. K., Single machine scheduling with controllable processing times and number of jobs tardy, Operations Research, 37, 981-984 (1989) · Zbl 0686.90023 |
| [10] | Janiak, A., General flow-shop scheduling with resource constraints, International Journal of Production Research, 26, 1089-1103 (1988) · Zbl 0639.90050 |
| [11] | Janiak, A.; Kovalyov, M. Y., Single machine scheduling subject to deadlines and resource dependent processing times, European Journal of Operational Research, 94, 284-291 (1996) · Zbl 0947.90584 |
| [12] | Cheng, T. C.E.; Chen, Z. L.; Li, C. L., Single-machine scheduling with trade-off between number of tardy jobs and resource allocation, Operations Research Letters, 19, 237-242 (1996) · Zbl 0874.90105 |
| [13] | Chen, Z. L.; Lu, Q.; Tang, G., Single machine scheduling with discretely controllable processing times, Operation Research Letters, 21, 69-76 (1997) · Zbl 0888.90088 |
| [14] | Shabtay, D.; Kaspi, M., Minimizing the total weighted flow time in a single machine with controllable processing times, Computers and Operations Research, 31, 2279-2289 (2004) · Zbl 1073.90017 |
| [15] | Shabtay, D., Single and two-resource allocation algorithms for minimizing the maximal lateness in a single machine, Computers and Operations Research, 31, 1303-1315 (2004) · Zbl 1073.90016 |
| [16] | Kaspi, M.; Shabtay, D., A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates, Computers and Operations Research, 33, 3015-3033 (2006) · Zbl 1086.90024 |
| [17] | Shabtay, D.; Steiner, G., A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 155, 1643-1666 (2007) · Zbl 1119.90022 |
| [18] | Panwalkar, S. S.; Rajagopalan, R., Single-machine sequencing with controllable processing times, European Journal of Operational Research, 59, 298-302 (1992) · Zbl 0760.90058 |
| [19] | Liman, S. D.; Panwalkar, S. S.; Thongmee, S., A single machine scheduling problem with common due window and controllable processing times, Annals of Operations Research, 70, 145-154 (1997) · Zbl 0890.90104 |
| [20] | Ng, C. T.D.; Cheng, T. C.E.; Kovalyov, M. Y.; Lam, S. S., Single machine scheduling with a variable common due date and resource-dependent processing times, Computers and Operations Research, 30, 1173-1185 (2003) · Zbl 1047.90022 |
| [21] | Hansen, P.; Mladenović, N., Variable neighborhood search: principles and applications, European Journal of Operational Research, 130, 449-467 (2001) · Zbl 0981.90063 |
| [22] | Du, J.; Leung, J. Y.T., Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15, 483-495 (1990) · Zbl 0714.90052 |
| [23] | Pinedo, M., Scheduling: theory, algorithm, and system (2002), Prentice-Hall: Prentice-Hall New Jersey · Zbl 1145.90394 |
| [24] | Nemhauser, G.; Wolsey, L., Integer and combinatorial optimization (1988), Wiley: Wiley New York · Zbl 0652.90067 |
| [25] | Hillier, F. S.; Lieberman, G. J., Introduction to operations research (2001), McGraw-Hill: McGraw-Hill New York · Zbl 0155.28202 |
| [26] | Russell, R. M.; Holsenback, J. E., Evaluation of leading heuristics for the single machine tardiness problem, European Journal of Operational Research, 96, 538-545 (1997) · Zbl 0929.90039 |
| [27] | Schrage, L. E., Optimization modeling with LINDO (1997), Brooks, Cole: Brooks, Cole California |
| [28] | Mladenović, N.; Hansen, P., Variable neighborhood search, Computers and Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119 |
| [29] | Hansen, P.; Mladenović, N., Variable neighborhood search for the \(p\)-Median, Location Science, 5, 207-226 (1997) · Zbl 0928.90043 |
| [30] | Avanthay, C.; Hertz, A.; Zufferey, N., A variable neighborhood search for graph coloring, European Journal of Operational Research, 151, 379-388 (2003) · Zbl 1053.90050 |
| [31] | Ben-Daya, M.; Al-Fawzan, M., A simulated annealing approach for the one-machine mean tardiness scheduling problem, European Journal of Operational Research, 93, 61-67 (1996) · Zbl 0912.90171 |
| [32] | Etiler, O.; Toklu, B.; Atak, M.; Wilson, J., A genetic algorithm for flow shop scheduling problems, Journal of the Operational Research Society, 55, 830-835 (2004) · Zbl 1060.90035 |
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.
