An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem

References

• Ahuja R. K., Ergun O., Orlin J. B., Punnen A. A survey of very large-scale neighborhood search techniques. (1999) . Working Paper, Operations Research Center, Massechusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Anderson E. J., Glass C. A., Potts C. N., Aarts E. H. L., Lenstra J. K. Machine scheduling. Local Search in Combinatorial Optimization (1997) (Wiley, Chichester, UK) 361–414Google Scholar
• Applegate D., Bixby R., Chvatal V., Cook W. Finding tours in the TSP. (1999) . Report No. 99885, Forschungsinstitut für Diskrete Mathematik, Universität Bonn, Bonn, GermanyGoogle Scholar
• Balas E. New classes of efficiently solvable generalized traveling salesman problems. Annals of Operations Research (1999) 86:529–558Crossref, Google Scholar
• Balas E., Simonetti N. Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study. INFORMS Journal on Computing (2001) 13:56–75Link, Google Scholar
• Baum E. B. Iterated descent: a better algorithm for local search in combinatorial optimization problems. (1986a) . Technical Report, Caltech, Pasadena, CAGoogle Scholar
• Baum E. B., Denker J. S. Towards practical ‘neural’ computation for combinatorial optimization problems. Neural Networks for Computing (1986b) Proceedings AIP Conference 151, American Institute of PhysicsNew York:53–58Crossref, Google Scholar
• Baxter J. Local optima avoidance in depot location. Journal of the Operational Research Society (1981) 32:815–819Crossref, Google Scholar
• Beasley J. E. OR library: distributing test problems by electronic mail. Journal of the Operational Research Society (1990) 41:1069–1072Crossref, Google Scholar
• Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems-I. Discrete Applied Mathematics (1996) 65:97–122Crossref, Google Scholar
• Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems. Part 2. Discrete Applied Mathematics (1997) 72:47–69Crossref, Google Scholar
• Carlier J., Villon P. A new heuristic for the traveling salesman problem. RAIRO Recherche Opérationelle (1990) 24:245–253Crossref, Google Scholar
• Congram R. K. Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimisation. (2000) . Ph.D. thesis, University of Southampton, UKGoogle Scholar
• Crauwels H. A. J., Potts C. N., Van Wassenhove L. N. Local search heuristics for the single machine total weighted tardiness scheduling problem. INFORMS Journal on Computing (1998) 10:341–350Link, Google Scholar
• Deĭneko V., J.Woeginger G. A study of exponential neighborhoods for the traveling salesman problem and for the quadratic assignment problem. Mathematical Programming (2000) 87:519–542Crossref, Google Scholar
• Hurink J. An exponential neighborhood for a one-machine batching problem. OR Spektrum (1999) 21:461–476Crossref, Google Scholar
• Johnson D. S., Paterson M. S. Local optimization and the traveling salesman problem. Automata, Languages and Programming (1990) (Springer, Berlin, Germany) 446–461Lecture Notes in Computer Science 443Crossref, Google Scholar
• Johnson D. S., McGeoch L. A., Aarts E. H. L., Lenstra J. K. The traveling salesman problem: a case study. Local Search in Combinatorial Optimization (1997) (Wiley, Chichester, UK) 215–310Google Scholar
• Johnson D. S., Bentley J. L., McGeoch L. A., Rothbergh E. E. Near-optimal solutions to very large traveling salesman problems. (2001) . Monograph in preparation, AT & T Labs, Florham Park, NJGoogle Scholar
• Lawler E. L. A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics (1977) 1:331–342Crossref, Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G., Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics (1977) 1:343–362Crossref, Google Scholar
• Lourenço H. R. Job-shop scheduling: computational study of local search and large-step optimization methods. European Journal of Operational Research (1995) 83:347–364Crossref, Google Scholar
• Lourenço H. R., Zwijnenburg M., Osman I. H., Kelly J. P. Combining the largestep optimization with tabu-search: application to the job-shop scheduling problem. Meta-Heuristics: Theory and Applications (1996) (Kluwer, Norwell, MA) 219–236Crossref, Google Scholar
• Martin O., Otto S. W. Combining simulated annealing with local search heuristics. Annals of Operations Research (1996) 63:57–75Crossref, Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the traveling salesman problem. Complex Systems (1991) 5:299–326Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the TSP incorporating local search heuristics. Operations Research Letters (1992) 11:219–224Crossref, Google Scholar
• Matsuo H., Suh C. J., Sullivan R. S. A controlled search simulated annealing method for the single machine weighted tardiness problem. (1987) . Working Paper 87-12-2, Department of Management, University of Texas, Austin, TXGoogle Scholar
• Morton T. E., Pentico D. W.Heuristic Scheduling Systems with Applications to Production Systems and Project Management (1993) (Wiley, Chichester, UK) Google Scholar
• Morton T. E., Rachamadugu R. M., Vepsalainen A. Accurate myopic heuristics for tardiness scheduling. (1984) . GSIA Working Paper No. 36-83-84, Carnegie-Mellon University, Pittsburgh, PAGoogle Scholar
• Potts C. N., Van Wassenhove L. N. A branch and bound algorithm for the total weighted tardiness problem. Operations Research (1985) 33:363–377Link, Google Scholar
• Potts C. N., Van Wassenhove L. N. Single machine tardiness sequencing heuristics. IIE Transactions (1991) 23:346–354Crossref, Google Scholar
• Sarvanov V. I., Doroshko N. N. The approximate solution of the travelling salesman problem by a local algorithm that searches neighborhoods of exponential cardinality in quadratic time (in Russian). Software: Algorithms and Programs (1981a) 31:8–11Mathematical Institute of the Belorussian Academy of Sciences, Minsk, BelarusGoogle Scholar
• Sarvanov V. I., Doroshko N. N. The approximate solution of the travelling salesman problem by a local algorithm with scanning neighborhoods of factorial cardinality in cubic time (in Russian). Software: Algorithms and Programs (1981b) 31:11–13Mathematical Institute of the Belorussian Academy of Sciences, Minsk, BelarusGoogle Scholar
• Standard Performance Evaluation Corporation Performance results. (1992) . 10754 Ambassador Drive, Suite 201, Manassas, VA 20109. http://performance.netlib.org/performance/html/new.spec.cint92.col0.htmlGoogle Scholar
• Stützle T., den Besten M., Dorigo M. Ant colony optimization for the weighted tardiness problem. (1999) . Technical Report IRIDIA/99-16, Université Libre de Bruxelles, Brussels, BelgiumGoogle Scholar