18199

Автор(ы): 

Автор(ов): 

2

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

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

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

Название: 

Two Dedicated Machines Scheduling Problem in Two-Sided Assembly Lines

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

  • Operations Research (Hannover, 2012)

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

  • Book of Abstracts of the International annual conference "Operations Research" (Hannover, 2012)

Город: 

  • Hannover

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

  • Institute of Production Management Leibniz Universitat Hannover

Год издания: 

2012

Страницы: 

174
Аннотация
Two dedicated parallel machines scheduling problem with precedence constraints to minimize makespan is considered. Given a set N of n jobs that must be processed on two parallel machines. Jobs from the subset N1 have to be processed on the first machine, jobs from N2 on the second one. All the jobs are assumed to be available for processing at time 0. For each job j a processing time is known. Furthermore, arbitrary finish-start precedence relations are introduced between the jobs according to an acyclic directed graph G. The objective is to determine the starting time in such a way that the given precedence relations are fulfilled and the makespan (the maximal completion time) is minimized. This problem originally appeared as a sub-problem of the well-known two-sided assembly line balancing problem (TSALBP-1). Denote this problem P2|N1,N2,prec|Cmax. The following Lemmas are proven: Lemma 1. A special case of the problem P2|N1,N2,chain|Cmax is NP hard in the strong sense, where G consists only chains of jobs. Lemma 2. A simple assembly line balancing problem(SALBP-1) can be reduced P2|N1,N2,chain|Cmax in polynomial time. Lemma 3. A special case with equal-processing-times of jobs P2|N1,N2,p_j=1|Cmax is NP hard in the strong sense. Lemma 4. The problem P2|N1,N2,prec|Cmax --> max with opposite optimization criterion is NP-hard in the strong sense. We showed as well that List Scheduling Algorithm with some domination rules (Critical Path, Largest Processing Time, etc.) has an approximation ratio almost equal 2.

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

Гафаров Е.Р., Долгий А.Б. Two Dedicated Machines Scheduling Problem in Two-Sided Assembly Lines / Book of Abstracts of the International annual conference "Operations Research" (Hannover, 2012). Hannover: Institute of Production Management Leibniz Universitat Hannover, 2012. С. 174.