.png){kind=icon}
.png){kind=icon}
Return
A new approximation algorithm for UET-scheduling with chain-type precedence constraints
.png){kind=icon}
PRE
AI
DOI：10.1016/S0305-0548(98)00022-7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper a new approximation algorithm with worst case performance ratio 3/2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makespan where each job can be processed on only one machine and there are chain-type precedence constraints in the jobs. This result answers an open problem in Jansen et al. [Jansen, K., Woeginger, G. J. and Yu, Z., UET-Scheduling with chain-type precedence constraints. Report 277, Technische Universitat Graz, Institut fur Mathematik, Graz, Austria, 1993.]: Does there exist a polynomial time heuristic with worst-case guarantee better than 5/3 for the problem U2Chain?. The new approximation algorithm is also applied to the problem J2\pmtn\C-max. (C) 1998 Elsevier Science Ltd. All rights reserved.
Keywords:
precedence constraints
parallel machines
makespan
approximation algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
No organization information available