34080

Автор(ы): 

Автор(ов): 

2

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

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

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

Название: 

Single machine scheduling: an upper bound on maximum lateness

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

  • 28th Conference of the European Chapter on Combinatorial Optimization (Catania, 2015)

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

  • Abstracts of the 28th Conference of the European Chapter on Combinatorial Optimization (Catania, 2015)

Город: 

  • Catania

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

  • Dept. of Economics and Business University of Catania

Год издания: 

2015

Страницы: 

63
Аннотация
The following classical NP-complete scheduling problem is considered. There is a single machine and a set of jobs to be processed. The goal is to construct an optimal schedule with respect to criterion minimization of maximum lateness. We construct the measure of insolubility E for a set of polynomial solvable instances. Then, we project the considered instance on 3n-dimensional unit sphere and we estimate an upper bound on a metric distance between the considered instance and polynomial solvable area equals E < 1 when parameters of jobs are real and E < 1/sqrt2 when parameters of jobs are positive. We also present some bad instances to prove that the bound is tight for a considered set of polynomial solvable areas. In addition we present some properties of instances with the largest metric distances. Analysis of the efficiency of suggested method and numerical experiments are also presented.

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

Лазарев А.А., Архипов Д.И. Single machine scheduling: an upper bound on maximum lateness / Abstracts of the 28th Conference of the European Chapter on Combinatorial Optimization (Catania, 2015). Catania: Dept. of Economics and Business University of Catania, 2015. С. 63.