|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Polynomial algorithm for Baptiste's problem for single machine with preemptions of jobsтезисы доклада
- Авторы: Лазарев А.А., Архипов Д.И.
- Сборник: 24th European Chapter on Combinatorial Optimization
- Тезисы
- Год издания: 2011
- Место издания: Universiteit Van Amsterdam Amsterdam
- Первая страница: 31
- Аннотация: We study the scheduling problem for single machine with preemptions of jobs. On a machine it is necessary to process a set of n jobs. Simultaneous processing is prohibited, but interrupts in processing jobs is possible. Each job j of the set is characterize by it's weight w_j, release date r_j = j - 1 and processing time p_j = 2. The only restriction is that weights w_j are non-decreasing. The objective function can be expressed as the sum of weighted completion times. We suggest the polynomial algorithm with complexity O(n^4) operations which gives us the Pareto-optimal schedules for each set of jobs. In the algorithm we use generalized Smith's rule, to obtain particular schedules after moment r_n and to prove some important lemmas for reduction of search of suitable schedules.
- Добавил в систему: Лазарев Александр Алексеевич