DocumentCode :
3332576
Title :
Scheduling on Networks of Workstations with Task Runtime Restrictions
Author :
Bazyluk, Marcin ; Koszalka, Leszek ; Burnham, Keith J.
Author_Institution :
Wroclaw Univ. of Technol., Wroclaw
fYear :
2008
fDate :
13-18 April 2008
Firstpage :
608
Lastpage :
613
Abstract :
In recent time we spot a tendency to use the computing capacity of workstation clusters instead of investing in single machines with tremendous calculation power. Applying this idea we are able to execute multiple jobs paralelly. However, it still remains unclear how to schedule given jobs among available machines most effectively. Therefore this paper is an approach to optimization of mentioned scheduling. The problem faced here is known in the literature as parallel machine earliness-tardiness scheduling (PMSP_E/T). The optimum criterion is finding the minimal sum of the weighted earliness and tardiness penalties. Due to NP-hardness of specified problem and thus difficulty in locating the optimum we propose two heuristic algorithms to find a satisfying solution: genetic with MCUOX crossover operator and tabu search. We have conducted a research to compare the effectiveness of both approaches and display their dependence on the size of examined instances. Results proove genetic approach superiority over tabu search for larger instances.
Keywords :
computational complexity; optimisation; parallel machines; scheduling; search problems; workstation clusters; NP-hardness; earliness-tardiness scheduling; optimization; parallel machine; tabu search; task runtime restrictions; workstation clusters; Computer networks; Control theory; Equations; Genetics; Job shop scheduling; Parallel machines; Processor scheduling; Runtime; Single machine scheduling; Workstations;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Networking, 2008. ICN 2008. Seventh International Conference on
Conference_Location :
Cancun
Print_ISBN :
978-0-7695-3106-9
Electronic_ISBN :
978-0-7695-3106-9
Type :
conf
DOI :
10.1109/ICN.2008.82
Filename :
4498229
Link To Document :
بازگشت