13939

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Тезисы доклада

Название: 

Polynomial algorithm for Baptiste's problem for single machine with preemptions of jobs

Наименование конференции: 

  • 24th Conference of the European Chapter on Combinatorial Optimization (ECCO, Amsterdam, 2011)

Наименование источника: 

  • Abstracts of the 24th European Chapter on Combinatorial Optimization (ECCO, Amsterdam, 2011)

Город: 

  • Amsterdam

Издательство: 

  • Universiteit Van Amsterdam

Год издания: 

2011

Страницы: 

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.

Библиографическая ссылка: 

Лазарев А.А., Архипов Д.И. Polynomial algorithm for Baptiste's problem for single machine with preemptions of jobs / Abstracts of the 24th European Chapter on Combinatorial Optimization (ECCO, Amsterdam, 2011). Amsterdam: Universiteit Van Amsterdam, 2011. С. 31.