|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Relocation scheduling subject to fixed processing sequences, Journal of Schedulingстатья
- Авторы: Lin B.M.T, Hwang F.J., Kononov A.V.
- Журнал: Journal of Scheduling
- Том: 19
- Номер: 2
- Год издания: 2016
- Издательство: Springer Nature
- Местоположение издательства: Switzerland
- Первая страница: 153
- Последняя страница: 163
- DOI: 10.1007/s10951-015-0455-8
- Аннотация: This study addresses a relocation schedulingproblem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processingsequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of thesix considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, ormaximum lateness can be solved in O(n1n2(n1 + n2)) time, where n1 and n2 are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in O(n1n2) time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processinglength is solvable in O(n1n2 min{n1, n2}) time. The studied problem for the minimization of number of tardy jobs issolvable in O(n^2 1n (n1 + n2)2) time.
- Добавил в систему: Кононов Александр Вениаминович