Algorytm branch-and-bound dla pewnego problemu szeregowania zadań uwarunkowanych czasowo

Abstract

The article presents a branch-and-bound algorithm for a follo­wing time-dependent scheduling problem: $1|p_{i}=1+a_{i}s_{i}| \Sigma C_{i}$. The computational experiments were conducted to examine the efficiency of the algorithm. Application of the presented algorithm allows us to increase the size of input instances that can be solved to optimality in reasonable time by 6-10 jobs, compared to the exhaustive-search algorithm. W pracy przedstawiono algorytm branch-and-bound dla problemu szeregowania zadań uwarunkowanych czasowo $1|p_{i}=1+a_{i}s_{i}| \Sigma C_{i}$, a także wyniki eksperymentów komputerowych prezentujących wydajność algorytmu. Zastosowanie przedstawionego algorytmu umożliwia powiększenie 'obliczalnych' rozmiarów instancji o 6-10 zadań w stosunku do algorytmu pełnego przeszukiwania.