Algorytmy z szacowaniem kosztów w kryterium lokalnym dla problemu szeregowania zadań

Abstract

W artykule przedstawiono problem właściwego utworzenia kryterium lokalnego w metodzie gromadzenia informacji na potrzeby sterowania. Zawarte zostały rozważania dotyczące dwóch wzajemnie przeciwstawnych wymagań: potrzeby wykorzystania jak największej ilości dostępnych informacji do optymalizacji lokalnej oraz możliwie małej złożoności obliczeniowej algorytmu optymalizacji lokalnej. Zaprezentowano postaci kryterium lokalnego wykorzystujące różną ilość informacji opracowane dla problemu drążenia wyrobisk korytarzowych. Problem ten należy do klasy szeregowania zadań na wielu maszynach z czasami przezbrojeń zależnymi od stanu systemu. Przestawiono wyniki przeprowadzonych eksperymentów.

The article presents a problem connected with a proper creation of local criterion in a solution search method with information gathering for a control purpose. Two opposite requirements are discussed: using possibly the biggest amount of information and getting possibly the smallest computational complexity. There are presented local criteria using different amount of information designed for a drift driving problem. This problem belongs to class of task scheduling problems on multiple machines with retooling depending on process state. Some results of experiments are also described.