|
This article is cited in 2 scientific papers (total in 2 papers)
Effective algorithms for one scheduling problem on two machines with makespan minimization
A. A. Romanovaab a Omsk Law Academy, 12 Korolenko St., 644010 Omsk, Russia
b Omsk State University, 55-a Mir Ave., 644077 Omsk, Russia
Abstract:
We consider an NP-hard problem of scheduling a set of jobs of equal processing time on two machines, given a partial precedence order between the jobs, with an objective to minimize the makespan. An approximation algorithm with performance guarantee is proposed for this problem. Polynomial solvability of the problem is proved in the case when each job on the first machine is in precedence relation with two jobs on the second machine. Ill. 9, bibliogr. 8.
Keywords:
cross-docking problem, schedule, partial order, approximation algorithm.
Received: 17.03.2015 Revised: 06.05.2015
Citation:
A. A. Romanova, “Effective algorithms for one scheduling problem on two machines with makespan minimization”, Diskretn. Anal. Issled. Oper., 22:4 (2015), 63–79; J. Appl. Industr. Math., 9:4 (2015), 570–579
Linking options:
https://www.mathnet.ru/eng/da825 https://www.mathnet.ru/eng/da/v22/i4/p63
|
Statistics & downloads: |
Abstract page: | 228 | Full-text PDF : | 171 | References: | 34 | First page: | 9 |
|