Abstract | ||
---|---|---|
We consider a high-multiplicity parallel machine scheduling problem where the objective is to minimize the weighted sum of completion times. We suggest an approximate algorithm and we prove that it is asymptotically exact. The algorithm exploits a convex quadratic relaxation of the problem to fix a partial schedule, consisting of most jobs, and then assigns the residual jobs following a simple and general rule. The quality of the obtained solution is evidenced by some numerical tests. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1016/j.orl.2010.03.009 | Oper. Res. Lett. |
Keywords | Field | DocType |
partial schedule,high multiplicity,numerical test,general rule,scheduling,weighted sum,convex quadratic relaxation,parallel machines,completion time,high-multiplicity parallel machine scheduling,approximation,approximate algorithm,residual job | Residual,Mathematical optimization,Combinatorics,Machine scheduling,Scheduling (computing),Algorithm,Multiplicity (mathematics),Quadratic equation,Regular polygon,Quadratic programming,Convex optimization,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 4 | Operations Research Letters |
Citations | PageRank | References |
1 | 0.35 | 10 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Carlo Filippi | 1 | 168 | 13.77 |