Browsing by Subject "sequencing"

Now showing 1 - 2 of 2

Access status: Open Access ,
Block approach-local search algorithm for single machine total weighted tardiness problem
(Wydawnictwa AGH, 2005) Bożejko, Wojciech; Grabowski, Józef; Wodecki, Mieczysław
W pracy rozpatrujemy problem szeregowania zadań na jednej maszynie z minimalizacją sumy kosztów opóźnień. Przedstawiamy szereg nowych własności pozwalających na rozbicie permutacji (rozwiązania dopuszczalnego) na podciągi, zwane blokami. Dzięki temu, z otoczeń generowanych przez ruchy typu zamień lub wstaw, eliminujemy wiele rozwiązań nie gwarantujących poprawę wartości funkcji celu. Algorytm oparty na metodzie poszukiwania z zabronieniami (tabu search), w którym stosuje się te otoczenia, działa bardzo szybko, a otrzymane wyniki są lepsze niż inne wyniki opisane w literaturze algorytmów.
Access status: Open Access ,
Scheduling jobs with linear model of simultaneous ageing and learning effects
(2011) Janiak, Adam; Lichtenstein, Maciej; Rusoń, Agata
In the paper, we introduce some new scheduling model in which learning and aging effects are both considered simultaneously. In this model the actual processing time of the jobs depends only on its position in a schedule and can be described by the piecewise linear function. For single-processor problem with introduced model, we show that the problem of minimizing the makespan criterion for independent jobs with release dates is strongly NP-hard, but some special cases of this problem are polynomially solvable. Based on those special cases, we propose 4 heuristic algorithms and we experimentally examine their usefulness for solving the general problem.