|
|
| |
| SEMI-DEFINITE RELAXATION ALGORITHMFOR SINGLE MACHINE SCHEDULING WITHCONTROLLABLE PROCESSING TIMES |
| |
Citation： |
CHEN Feng,ZHANG Liansheng.SEMI-DEFINITE RELAXATION ALGORITHMFOR SINGLE MACHINE SCHEDULING WITHCONTROLLABLE PROCESSING TIMES[J].Chinese Annals of Mathematics B,2005,26(1):153~158 |
| Page view： 1163
Net amount： 754 |
Authors： |
CHEN Feng; ZHANG Liansheng |
|
|
| Abstract： |
The authors present a semi-definite relaxation algorithm for the scheduling problem
with controllable times on a single machine. Their approach shows how to relate this
problem with the maximum vertex-cover problem with kernel constraints (MKVC).
The established relationship enables to transfer the approximate solutions of MKVC
into the approximate solutions for the scheduling problem. Then, they show how to
obtain an integer approximate solution for MKVC based on the semi-definite relaxation
and randomized rounding technique. |
Keywords： |
Scheduling with controllable times, Semi-definite programming, Approximation
algorithm |
Classification： |
90B35, 90C27, 68Q25 |
|
|
Download PDF Full-Text
|
|
|
|
