Probabilistic tabu search for makespan minimization discrete-continuous scheduling

• Autorzy: Józefowska J. , Waligóra G. , Węglarz J.
• Języki publikacji: EN

Abstrakty

EN

A problem of scheduling jobs on parallel, identical machines under an additional continuous resource to minimize the makespan is considered. Jobs are non-preemtable and independent, and all are available at the start of the process. The total amount of the continuous resource available at a time is limited, and the resource is a renewable one. Each job simultaneously requires for its processing a machine, and an amount (unknown in advance) of the continuous resource. Processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. The tabu search metaheuristic is presented to attack the problem. Probabilistic implementations of tabu search are discussed and examined. A computational experiment is described, and the results obtained for the probabilistic version of tabu search are compared to optimal solutions. A few conclusions and final remarks are presented.

Słowa kluczowe

EN

discrete-continuous scheduling; tabu search

PL

szeregowanie

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2003
• Tom: Vol. 28, No. 4
• Strony: 211--222
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Józefowska J.

• Poznań University of Technology, Institute of Computing Science, Piotrowo 3A, 60-965 Poznań, Poland

autor

Waligóra G.

• Poznań University of Technology, Institute of Computing Science, Piotrowo 3A, 60-965 Poznań, Poland

autor

Węglarz J.

• Poznań University of Technology, Institute of Computing Science, Piotrowo 3A, 60-965 Poznań, Poland

Bibliografia

• [1] Glover F., Future path for integer programming and links to artificial intelligence, Computers & Operations Research, 13, 1986, 533-549.
• [2] Glover F., Tabu search - part 1, ORSA Journal of Computing, 1, 1989, 190-206.
• [3] Glover F., Tabu search - part 2, ORSA Journal of Computing, 2, 1990, 4-32.
• [4] Glover F., Laguna M., Tabu search, Kluwer Academic Publishers, Norwell, 1997.
• [5] Glover F., McMillan C., The general employee scheduling problem: an integration of management science and artificial intelligence, Computers and Operations Research, 15(5), 1986, 563-593.
• [6] Józefowska J., Mika M., Różycki R., Waligóra G., Węglarz J., Local search metaheuristics for some discrete-continuous scheduling problems, European Journal of Operational Research, 107(2), 1998, 354-370.
• [7] Józefowska J., Waligóra G., Węglarz J., Tabu list management methods for a discrete-continuous scheduling problem, European Journal of Operational Research, 137(2), 2002, 288-302.
• [8] Józefowska J., Węglarz J., On a methodology for discrete-continuous scheduling, European Journal of Operational Research, 107(2), 1998, 338-353.
• [9] Lawrence C., Zhou J.L., Tits A.L., Users guide for CFSQP version 2.3 (released August 1995), 1995, available by e-mail: [e-mail].
• [10] Skorin-Kapov J., Tabu search applied to the quadratic assignment problem, ORSA Journal of Computing, 2, 1990, 33-45.