18345

Автор(ы): 

Автор(ов): 

2

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

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

Доклад

Название: 

Metric for the total tardiness minimization problem

Электронная публикация: 

Да

ISBN/ISSN: 

978-5-91601-069-5

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

  • III International Conference on Optimization Methods and Application (OPTIMA-2012), Costa da Caparica, Portugal, september 2012

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

  • Proceedings of the III International Conference on Optimization Methods and Application (OPTIMA-2012,Costa da Caparica, Portugal)

Город: 

  • Москва

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

  • Федеральное государственное бюджетное учреждение науки Вычислительный центр им. А.А.Дородницына РАН

Год издания: 

2012

Страницы: 

134-139
Аннотация
We consider single machine scheduling problems. N jobs that must be processed on the machine are given. Machine is ready to star processing since time 0 and can handle only one job at a time. Preemptions are not allowed. Each job $j$ is characterized by processing time $p_j$, due date $d_j$, and release date $r_j$. Our goal is to construct a schedule of processing that minimizes total tardiness of the jobs. We propose a new approach to construct approximate solutions with guaranteed absolute error for the problem. The approach consists in finding an instance of the problem, closest to a given instance in certain metric and using its optimal schedule as an approximate solution for the given instance. The approach can be generalized to scheduling problems with other objective functions.

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

Коренев П.С., Лазарев А.А. Metric for the total tardiness minimization problem / Proceedings of the III International Conference on Optimization Methods and Application (OPTIMA-2012,Costa da Caparica, Portugal). М.: Федеральное государственное бюджетное учреждение науки Вычислительный центр им. А.А.Дородницына РАН, 2012. С. 134-139.