Tabu search for a class of single-machine scheduling problems. (English) Zbl 1008.90020
Summary: We develop a tabu search-based solution procedure designed specifically for a certain class of single-machine scheduling problems with a non-regular performance measure. The performance of the developed algorithm is tested for solving the variance minimization problem. Problems from the literature are used to test the performance of the algorithm. This algorithm can be used for solving other problems such as minimizing completion time deviation from a common due date.
Software:
Tabu searchReferences:
| [1] | Al-Turki, U. M.; Mittenthal, J.; Ragavachari, M., A dominant subset of V-shaped sequences for a class of single machine sequencing problems, European Journal of Operational Research, 88, 345-347 (1996) · Zbl 0913.90156 |
| [2] | Schrage, L., Minimizing the time-in-system variance for a finite job set, Management Science, 31, 540-543 (1975) · Zbl 0302.90021 |
| [3] | Elion, S.; Chowdhury, I. C., Minimizing the waiting time variance in the single machine problem, Management Science, 23, 567-575 (1977) · Zbl 0362.90051 |
| [4] | Baker, K. R.; Scudder, G. D., Sequencing with earliness and tardiness penalties: a review, Operations Research, 38, 22-36 (1990) · Zbl 0699.90052 |
| [5] | Raghavachari, M., Scheduling problems with non-regular penalty functions: a review, Operations Research, 25, 144-164 (1988) · Zbl 0649.90065 |
| [6] | Mittenthal, J.; Ragavachari, M., Stochastic single machine scheduling with quadratic Early-Tardy penalties, Operations Research, 41, 786-796 (1993) · Zbl 0782.90055 |
| [7] | Vani, V.; Raghavachari, M., Deterministic and random single machine sequencing with variance minimization, Operations Research, 35, 111-120 (1987) · Zbl 0616.90027 |
| [8] | Mittenthal, I.; Ragavachari, M.; Rana, A. I., A hybrid simulated annealing approach for single machine scheduling problems with nonregular penalty functions, Computers and Operations Research, 20, 103-111 (1993) · Zbl 0759.90047 |
| [9] | Glover, F., Future paths for integer programming and linkage to artificial intelligence, Computers and Operations Research, 13, 533-549 (1986) · Zbl 0615.90083 |
| [10] | Glover, F., Tabu Search - Part I, ORSA Journal on Computing, 1, 3, 190-206 (1989) · Zbl 0753.90054 |
| [11] | Glover, F., Tabu Search - Part II, ORSA Journal on Computing, 2, 1, 4-32 (1990) · Zbl 0771.90084 |
| [12] | Hansen P. The steepest ascent mildest descent heuristic for combinatorial programming. Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy, 1986.; Hansen P. The steepest ascent mildest descent heuristic for combinatorial programming. Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy, 1986. |
| [13] | Hansen P, Jumard B. Algorithm for the maximum satisfiability problem. RUTCOR Research Report RR No. 43-87, Rutgers, New Brunswick, NJ, 1987.; Hansen P, Jumard B. Algorithm for the maximum satisfiability problem. RUTCOR Research Report RR No. 43-87, Rutgers, New Brunswick, NJ, 1987. |
| [14] | Nowicki E, Smutnicki C. A fast taboo search algorithm for the flow shop. Report ICT PRE 8/94, Technical University of Wroclaw, 1996.; Nowicki E, Smutnicki C. A fast taboo search algorithm for the flow shop. Report ICT PRE 8/94, Technical University of Wroclaw, 1996. · Zbl 0880.90079 |
| [15] | Taillard, E., Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Operations Research, 47, 65-74 (1990) · Zbl 0702.90043 |
| [16] | Laguna, M.; Kelly, J. P.; Gonzalez-Velarde, J. L.; Glover, F., Tabu search for the multilevel generalized assignment problem, European Journal of Operations Research, 82, 176-189 (1995) · Zbl 0905.90122 |
| [17] | Bland, J. A.; Dawson, J. P., Tabu search and design optimization, Computer-aided Design, 23, 3, 195-201 (1991) · Zbl 0735.65036 |
| [18] | Hertz, A., Tabu search for large scale time tabling problems, European Journal of Operations Research, 51, 39-47 (1991) · Zbl 0729.90660 |
| [19] | Skorin-Kapov, D.; Skorin-Kapov, J., On tabu search for the location of interacting hub facilities, European Journal of Operations Research, 73, 502-509 (1994) · Zbl 0806.90075 |
| [20] | Gupta, M. C.; Gupta, Y. P.; Bector, C. R., Minimizing the flow time variance in single machine systems, Journal of the operational Research Society, 41, 8, 767-779 (1990) · Zbl 0725.90039 |
| [21] | Al-Turki UM. Minimizing flow time variance in scheduling operations. The Fifth Saudi Engineering Conference, Umm Al-Qurah University Mekkah Al-Mukarama, Saudi Arabia, vol. 4, 1999. p. 207-11.; Al-Turki UM. Minimizing flow time variance in scheduling operations. The Fifth Saudi Engineering Conference, Umm Al-Qurah University Mekkah Al-Mukarama, Saudi Arabia, vol. 4, 1999. p. 207-11. |
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.
