Job Scheduling Algorithm Based on Multi-Criteria Optimization

• Autorzy: Piotr Czerpak , Piotr Artiemjew

Warianty tytułu

Wykorzystanie optymalizacji wielokryterialnej w algorytmie harmonogramowania zadań

• Języki publikacji: EN

Abstrakty

EN

The Job Scheduling problem is an important area of research. It is very popular among many researchers from all over the world. However, the Job Scheduling problem is NP-complete; it is impossible to find an algorithm which solves the aforementioned problem in a deterministic way and in polynomial time. In that paradigm the main task of research is to find algorithms which give as good as possible results in a reasonable time-frame. Beyond a doubt, it is a great opportunity to check the effectiveness of Job Scheduling algorithms and to compare them with solutions of other researchers. These are meaningful competitions, such as the recent Job Scheduling Competition on the TunedIT platform. In this paper we are going to present our novelty algorithm based on multi-criteria optimization, which achieved second place during the aforementioned competition. The key point of our approach is the usage of some additional heuristics which allowed us to arrive at such good results. (original abstract)

Problem szeregowania zadań to bardzo istotna dziedzina badań. Jest ona bardzo popularna wśród wielu naukowców z całego świata. Problem szeregowania zadań należy do kategorii problemów NP-zupełnych - nie istnieją algorytmy deterministyczne, które rozwiązywałyby ten problem w czasie wielomianowym. Dlatego głównym celem badaczy jest opracowanie algorytmu, który pozwoli na osiągnięcie jak najlepszych wyników w rozsądnym czasie. Niewątpliwie stwarza to możliwość sprawdzenia efektywności własnych algorytmów i porównania ich z algorytmami innych badaczy. Jedną z takich możliwości były zawody ogłoszone na portalu TunedIT. W niniejszej pracy zaprezentujemy nasz algorytm, wykorzystujący optymalizację wielokryterialną, który dał nam drugie miejsce we wspomnianych zawodach. Kluczowym punktem algorytmu są pewne heurystyki, które pozwoliły nam osiągnąć tak dobry wynik. (abstrakt oryginalny)

Słowa kluczowe

EN

Task scheduler; Algorithms; Multiple criteria optimization

PL

Harmonogram zadań; Algorytmy; Optymalizacja wielokryterialna

• Czasopismo: Studia i Materiały Polskiego Stowarzyszenia Zarządzania Wiedzą
• Rocznik: 2012
• Tom: 60
• Strony: 44--54

Twórcy

autor

Piotr Czerpak

• Uniwersytet Warmińsko-Mazurski w Olsztynie

autor

Piotr Artiemjew

• Uniwersytet Warmińsko-Mazurski w Olsztynie

Bibliografia

• Karger D., Stein C., Wein J.: Scheduling Algorithms (2010).
• Pinedo M.: Planning and Scheduling in Manufacturing and Services, Springer (2005).
• Wiers V.C.S.: A review of the applicability of OR and AI scheduling techniques in practice, "Omega", 25(2), pp. 145-153 (1997).
• Pinedo M.: Scheduling: Theory, Algorithms and Systems. Prentice Hall (1995).
• Baker K.R.: Introduction to sequencing and scheduling, New York, Wiley (1974).
• Chandrasekaran M., Asokan P., Kumanan S., Balamurugan T., Nickolas S.: Solving job shop scheduling problems using artificial immune system,"International Journal Advanced Manufacturing Technology", 31(5-6), pp. 580-593 (2005).
• Fink A., Vob S.: Solving the continuous flow shop scheduling problem by meta-heuristic, "European Journal of Operations Research", vol. 151, pp. 400-414 (2003).
• French S.: Sequencing and scheduling: An introduction to the mathematics of the job shop, Chichester, West Sussex, E. Horwood (1982).
• Giffler B., Thompson G.L.: Algorithms for solving production scheduling problems, "Operations Research", 8(4), pp. 487-503 (1960).
• Garey M.R., Johnson D.S., Sethi R.: The complexity of fowshop and jobshop scheduling, Mathematics of Operations Research, 1(1976)117-129.
• Mahanim O., Baharum A., Yahya A.H.: A job-shop scheduling problem using genetic algorithm. (2004).
• Yang G., Hongqiang R., Huang J.Z.: Adaptive grid job scheduling with genetic algorithms. (2004).
• Fatos X., Carretero J., Dorronsoro B., Alba E.: A Tabu search algorithm for scheduling independent jobs in computational grids. (2008).
• Hurink J., Jurish B., Thole M.: Tabu search for the job-shop scheduling problem with multi-purpose machines.
• Jayalakshmi S., Rajagopalan S.P.: Modular Simulated Annealing in Classical Job Shop Scheduling, "Information Technology Journal", 6: pp. 222-226 (2007).
• Takeshi Y., Ryohei N.: Job-Shop Scheduling by Simulated Annealing Combined with Deterministic Local Search. (1995).
• Zhou Y.: Study on job-shop scheduling with multi-objectives based on genetic algorithms (2010).
• Li-Ning X., Ying-Wu Ch., Ke-Wei Y.: Multi-objective flexible job shop schedule: Design and evaluation by simulation modeling (2009).
• Czerpak P.: Automatic Plan Scheduling as Multi-Objective Optimization. [w:] Methods of Optimisation and Data Analysis - Selected Issues. Kesra Nermend, Tomasz Komorowski (eds.), pp.13-29 (2010).
• Czerpak P., Drozda P., Sopyła K.: Use of Poly-Optimization for Automatic Scheduling at University. Congress of Young IT Scientist. "Polish Journal of Environmental Studies". vol. 18, no. 3B 2009, pp. 93-97 (2009).
• Tuned It: http://tunedit.org/challenge/job-scheduling (2011).
• Graham R.: Bounds for certain multiprocessing anomalies, "Bell System Technical Journal" 45: pp. 1563-1581 (1966).