Heuristic procedures for allocating the continuous resource in discrete-continuous scheduling problems

• Autorzy: Józefowska J. , Waligóra G.
• 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. A heuristic approach to allocating the continuous resource is proposed. Four heuristic procedures are presented and discussed. A computational experiment is described, and the results produced by the heuristics are compared with optimal solutions. Some conclusions and directions for further research are given.

Słowa kluczowe

EN

scheduling; heuristic procedures

PL

szeregowanie; heurystyka

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2004
• Tom: Vol. 29, No. 4
• Strony: 315--328
• Opis fizyczny: Bibliogr. 8 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

Bibliografia

• [1] 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.
• [2] Józefowska J., Mika M., Różycki R., Waligóra G., Węglarz J., A heuristic approach to allocating the continuous resource in discrete-continuous scheduling problems to minimize the makespan, Journal of Scheduling, 5,2002, 487-499.
• [3] Józefowska J., Waligóra G., Węglarz J., A tabu search algorithm for some discrete-continuous scheduling problems, in: V.J. Rayward-Smith, I.H. Osman, C.R. Reeves, G.D. Smith (eds.), Modern Heuristic Search Methods, Wiley, Chichester, 1996, 167-180.
• [4] 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.
• [5] Józefowska J., Waligóra G., Węglarz J., A performance analysis of tabu search for discrete-continuous scheduling problems, in: M.G.C. Resende, J.P. de Sousa (eds.), Metaheuristics: Computer Decision-Making, Kluwer, Boston, 2003, 385-404.
• [6] Józefowska J., Waligóra G., Węglarz J., Probabilistic tabu search for makespan minimization discrete-continuous scheduling. Foundations of Computing and Decision Sciences, 28(4), 2003, 211-222.
• [7] Józefowska J., Węglarz J., On a methodology for discrete-continuous scheduling, European Journal of Operational Research, 107(2), 1998, 338-353.
• [8] 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].