Využití moderních heuristických metod v rozvrhování

Application of Modern Heuristic Methods to Scheduling

článek v časopise - ostatní, Jost

cs

Obsahem disertační práce bylo uplatnění heuristických metod v problematice rozvrhování. Předkládaná disertační práce se pokusila zmapovat stav v této oblasti a zformalizovat podstatné rysy studovaných metod. V rámci zpracování tématu autor dosáhl některých původních výsledků: Navrhl novou implementaci známé metody CPM využívající tzv. lexikografické uspořádání hran síťového grafu a prokázal, že je efektivnější z hlediska časové složitosti než řešení založené na topologickém očíslování vrcholů, resp. na iterativním přístupu v nepřečíslovaném grafu. V problematice rozvrhování projektů s omezenými zdroji autor navrhl přístup spočívající v transformaci původního problému na posloupnost problémů batohu definovaných na časových intervalech s paralelně běžícími činnostmi. Tento přístup pak úspěšně prezentoval na významné konferenci v Helsinkách. Dále v této úloze navrhl efektivní přístup spočívající vtom, že se k trvání posouvaných činností přičte délka posunutí, a tak se automaticky po výpočtu metodou CPM posunou navazující činnosti. Přitom se u posouvané činnosti interval trvání dělí na úseky, kdy nárokuje zdroje (činnost probíhá), resp. neprobíhá a nenárokuje zdroje (čas provádění projektu spadá do intervalu posunutí). Neformálně odvodil matematické modely problémů rozvrhování proudové a zakázkové výroby. Modely rozvrhování proudové a zakázkové výroby naprogramoval a odladil v prostředí algebraického modelovacího systému GAMS a ukázal jeho omezenou použitelnost jen pro úlohy menšího rozsahu. Sestavil knihovnu procedur a funkcí pro řešení problémů rozvrhování pomocí stochastických heuristických metod (simulované žíhání, tabu-search a genetické algoritmy) v prostředí Borland Pascalu 7.0. Na základě počítačových experimentů specifikoval optimální volbu parametrů heuristických metod pro studovanou třídu problémů. V budoucím období autor předpokládá další ověřování heuristických metod, např. experimenty s délkou seznamu zakázaných transformací v tabu search či implementaci dalších reprezentací v problému rozvrhování zakázkové výroby. Z hlediska metod je možné zkoumat jejich hybridní kombinace, např. lokální hledání aplikované na chromozomy genetického algoritmu apod. Co se týká programu, autor předpokládá převod všech programových modulů, implementovaných v Borland Pascalu 7.0 do prostředí Borland Delphi. V oblasti rozvrhování vidí další možnosti v zahrnutí neurčitosti do dat rozvrhu (fuzzy scheduling) a uplatnění heuristických metod v oblasti rozvrhování servisních systémů (timetabling).

Obsahem disertační práce bylo uplatnění heuristických metod v problematice rozvrhování. Předkládaná disertační práce se pokusila zmapovat stav v této oblasti a zformalizovat podstatné rysy studovaných metod. V rámci zpracování tématu autor dosáhl některých původních výsledků: Navrhl novou implementaci známé metody CPM využívající tzv. lexikografické uspořádání hran síťového grafu a prokázal, že je efektivnější z hlediska časové složitosti než řešení založené na topologickém očíslování vrcholů, resp. na iterativním přístupu v nepřečíslovaném grafu. V problematice rozvrhování projektů s omezenými zdroji autor navrhl přístup spočívající v transformaci původního problému na posloupnost problémů batohu definovaných na časových intervalech s paralelně běžícími činnostmi. Tento přístup pak úspěšně prezentoval na významné konferenci v Helsinkách. Dále v této úloze navrhl efektivní přístup spočívající vtom, že se k trvání posouvaných činností přičte délka posunutí, a tak se automaticky po výpočtu metodou CPM posunou navazující činnosti. Přitom se u posouvané činnosti interval trvání dělí na úseky, kdy nárokuje zdroje (činnost probíhá), resp. neprobíhá a nenárokuje zdroje (čas provádění projektu spadá do intervalu posunutí). Neformálně odvodil matematické modely problémů rozvrhování proudové a zakázkové výroby. Modely rozvrhování proudové a zakázkové výroby naprogramoval a odladil v prostředí algebraického modelovacího systému GAMS a ukázal jeho omezenou použitelnost jen pro úlohy menšího rozsahu. Sestavil knihovnu procedur a funkcí pro řešení problémů rozvrhování pomocí stochastických heuristických metod (simulované žíhání, tabu-search a genetické algoritmy) v prostředí Borland Pascalu 7.0. Na základě počítačových experimentů specifikoval optimální volbu parametrů heuristických metod pro studovanou třídu problémů. V budoucím období autor předpokládá další ověřování heuristických metod, např. experimenty s délkou seznamu zakázaných transformací v tabu search či implementaci dalších reprezentací v problému rozvrhování zakázkové výroby. Z hlediska metod je možné zkoumat jejich hybridní kombinace, např. lokální hledání aplikované na chromozomy genetického algoritmu apod. Co se týká programu, autor předpokládá převod všech programových modulů, implementovaných v Borland Pascalu 7.0 do prostředí Borland Delphi. V oblasti rozvrhování vidí další možnosti v zahrnutí neurčitosti do dat rozvrhu (fuzzy scheduling) a uplatnění heuristických metod v oblasti rozvrhování servisních systémů (timetabling).

The research work in the course of the author's PhD study has been concentrated on applications of modern heuristic techniques to scheduling problems as in general, scheduling problems are NP-hard, and consequently there are no known algorithms guaranteed to give an optimal solution and run in polynomial time. The classical approach (mainly based on branch and bound method or backtracking technique) is impracticable for complex tasks. In the area of the resource constrained project scheduling the author's central idea was to transform this problem to a sequence of Multi Knapsack Problem solutions. It was shown that in projects with a single constraint, where the number of concurrent activities is up to 50, deterministic methods such as the branch and bound method and in a special case, the dynamic programming approach also may be used to yield better results than heuristic methods (genetic algorithm GA) and simulated annealing (SA)). On the contrary, the deterministic approaches are not effective or may not be used in the situations of complex projects with multiple constraints because of exponentially growing time in branch and bound method calculations and high memory requirements for the declaration of $F_k(y)$ arrays in the dynamic programming approach. In these cases, we choose heuristic techniques. The GA has been found to work effectively. It gives good results in a reasonable amount of time for hundreds of activities and tens of constraints. An original idea is also that the time shifting of activities when their total requirements are higher than the resource limit is provided by prolonging their duration but we distinguish for each activity $a$ its starting duration $t_a^s$ and current duration which $t_a^c$. Then $\delta_a=t_a^c-t_a^s$ is a subinterval corresponding to the shift activity during which it has no requirements for resources. The greatest advantage of this approach is that whenever we need to compute new earliest and latest terms for activities after shifts or updating the actual time duration of some activities we can compute the whole project by simple CPM method and precedence relationships are kept and parameters of previous activities do not change (in other words any change in the present has no effect on results in the past). As to permutation flow shop scheduling it has been shown that results are equal or close to optimal values although the number of iterations (generations) was not high (between 1000 and 50000). The GA results were better than the results gained by the SA and TS algorithm. To improve them we assume a replacement of a randomly generated initial solution by a solution generated by NEH heuristic. This research will be a basis for design of an integrated approach to flow shop lot sizing and scheduling under the assumption of constant continuous demands over an infinite planning horizon. In this case the objective is to find a sequence of production and lot sizes that minimize the sum of average setup costs and average inventory holding costs. The results achieved by heuristic techniques in solving jobshop scheduling problems are similar to previous results. Besides various approaches to problem representation (job-based, operation-based and disjunctive graph representation) we have studied one practical modification of the classical job shop scheduling problem, i.e. a parallel way of production where each job is sent to the next operation by transfer batches instead of production batches. That means when a machine assigned to $j$th operation is free, then it does not wait for completing the production batch on the previous place, but this operation is done immediately after completing and sending transfer batch from the previous operation.

flow shop, job shop, resource-constrained scheduling, heuristics

01.02.1999

VUT v Brně

1213-4198

Vědecké spisy vysokého učení technického v Brně Edice PhD Thesis

1999

4

30