An Improved Tabu Search Algorithm for a Type of Single Machine Sequencing Problem

Abstract:

Machine scheduling is a central task in production planning. In general it means the problem of scheduling job operations on a given number of available machines. In this paper we consider a machine scheduling problem with one machine, or the Single Machine Total Tardiness Problem. To solve this NP-hard problem, we develop an improved Tabu Search Algorithm, which is tested to have the ability to find good results by an example.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 3997-4001
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.3997
• Online since: September 2013
• Authors: Meng Lan Wang, Wen Bin Liu
• Keywords: Machine Scheduling, SMTTP, Tabu Search Algorithm

References

[1] Glover F. Heuristics for integer programming using surrogate constraints [J]. Decision Science, 1977, 8(1): 156-166.

DOI: 10.1111/j.1540-5915.1977.tb01074.x

[2] Glover F. Tabu search－PartⅠ [J]. ORSA Journal on Computing, 1989, 1(3): 190-206.

[3] Glover F. Tabu search－Part Ⅱ [J]. ORSA Journal on Computing, 1990, 2(1): 4-32.

[4] Glover F, Taillard E, Werra D de. A user's guide to tabu search [J]. Annals of Operation Research, 1993, 41(1-4): 3-28.

[5] Glover F, Kelly J P, Laguna M. Genetic algorithms and tabu search: hybrids for optimization [J]. Computers Ops. Res., 1995, 22(1): 111-134.

DOI: 10.1016/0305-0548(93)e0023-m

[6] Glover F, Hanafi Saı̈d. Tabu search and finite convergence [J]. Discrete Applied Mathematics, 2002, 119: 3-36.

DOI: 10.1016/s0166-218x(01)00263-3

[7] Michel Gendreau, Alain Hertz and Gilbert Laporte. A Tabu Search Heuristic for the Vehicle Routing Problem [J]. Management Science, 1994 40(10): 1276-1290.

DOI: 10.1287/mnsc.40.10.1276

[8] Mauro Dell'Amico and Marco Trubian. Applying tabu search to the job-shop scheduling problem [J]. Annals of Operations Research, 1993 41: 231-252.

DOI: 10.1007/bf02023076

[9] Michel Gendreau, Alain Hertz and Gilbert Laporte. A Tabu Search Heuristic for the Vehicle Routing Problem [J]. Management Science, 1994 40(10): 1276-1290.

DOI: 10.1287/mnsc.40.10.1276

[10] A. Hertz and D. de Werra, Lausanne. Using Tabu Search Techniques for Graph Coloring [J]. Computing, 1987 39: 345-351.

DOI: 10.1007/bf02239976

[11] C. N. Fiechter. A parallel tabu search algorithm for large traveling salesman problems [J]. Discrete Applied Mathematics, 1994 51(3): 243–267.

DOI: 10.1016/0166-218x(92)00033-i

[12] ALFONSAS MISEVICIUS. A Tabu Search Algorithm for the Quadratic Assignment Problem [J]. Computational Optimization and Applications, 2005 30: 95-111.

DOI: 10.1007/s10589-005-4562-x

[13] Emmons, H. One-machine sequencing to minimize certain functions of job tardiness. Operations Research, 1969, 17: 701-715.

DOI: 10.1287/opre.17.4.701

[14] Lawler, E. L. A pseudopolynomial, algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1997, 1, 331-342.

DOI: 10.1016/s0167-5060(08)70742-8

[15] Du, J. and Leung, J.Y.T. Minimizing total tardiness on one machine is ZP-hard. Mathematics of Operations Research, 1990, 15, 483-495.

DOI: 10.1287/moor.15.3.483

[16] Koulamas, C. P. The total tardiness problem: review and extensions. Operations Research, 1994, 42, 1025-1041.

DOI: 10.1287/opre.42.6.1025

[17] Potts, C.N. and Van Wassenhove, L. N., A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 1982, 1, 177-181.

DOI: 10.1016/0167-6377(82)90035-9

[18] Chu, C., A branch-bound algorithm to minimize total tardiness with different release dates. Naval Research Logistics, 1992, 39, 265-283.

DOI: 10.1002/1520-6750(199203)39:2<265::aid-nav3220390209>3.0.co;2-l

[19] Fisher, M.L. (1976): A Dual Algorithm for the One-Machine Scheduling Problem, Mathematical Programming 11 pp.229-251.

DOI: 10.1007/bf01580393

[20] Schrage, L.E. and K. R. Baker (1978): Dynamic Programming Solution of Sequencing Problems with Precedence Constrains, Operations Research 26 pp.444-449.

DOI: 10.1287/opre.26.3.444

[21] Szwarc, W. and S. Mukhopadhyay (1996): Decomposition of the Single Machine Total Tardiness Problem, Operations Research Letters 19 pp.243-245.

DOI: 10.1016/s0167-6377(96)00031-4

[22] Della Croce, F., R. Tadei, P. Baracco and A. Grosso(1998): A New Decomposition Approach for the Single Machine Total Tardiness Scheduling Problem, Journal of the Operational Research Society 49 pp.1101-1106.

DOI: 10.1057/palgrave.jors.2600624

[23] Wilkerson, L. J, and Irwin, J.D. (1971): An Improved Algorithm for Scheduling Independent Tasks, AIIE Transactions 3 pp.239-245.

[24] Fry, T. D., L. Vicens, K. Macleod and S. Fernandez (1989): A heuristic Solution Procedure to Minimize T on a Single Machine, Journal of the Operational Research Society 40 pp.293-297.

DOI: 10.1057/jors.1989.39

[25] Hosenback, J. E. and R.M. Russell(1992): A heuristic Algorithm for Sequencing on One Machine to Minimize Total Tardiness, Journal of the Operational Research Society 43 pp.53-62.

DOI: 10.1057/jors.1992.6

[26] Panwalkar, S. S., M. L. Smith and C. P. Koulamas (1993): A heuristic for the Single Machine Tardiness Problem, European Journal of Operational Research 70 pp.304-310.

DOI: 10.1016/0377-2217(93)90241-e

[27] Wang Dingwei, the intelligent optimization methods [M], higher education press, (2007).

[28] R. Panneerselvam, Simple heuristic to minimize total tardiness in a single machine scheduling problem.