Name
Title | ||
|---|---|---|
Minimizing job completion time variance for service stability on identical parallel machines |
Abstract | ||
|---|---|---|
This paper addresses a job scheduling problem on multiple identical parallel machines so as to minimize job completion time variance (CTV). CTV minimization is closely related to the Just-In-Time philosophy and the service stability concept since it penalizes both earliness and tardiness. Its applications can be found in many real-life areas such as Internet data packet dispatching and production planning. This paper focuses on the unrestricted case of the problem where idle times are allowed to exist before machines start to process jobs. We prove several dominant properties about the optimal solution to the problem. For instance, we prove that the mean completion time (MCT) on each machine should be the same under an optimal schedule. Based on these properties, an efficient heuristic algorithm is proposed. Computational experiments are conducted to test the performance of the proposed algorithm. The outputs demonstrate that the proposed algorithm is near optimal for small problem instances and greatly outperforms some existing algorithms for large problem instances. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.cie.2010.02.002 | Computers & Industrial Engineering |
Keywords | Field | DocType |
near optimal,service stability,minimizing job completion time,proposed algorithm,ctv minimization,small problem instance,completion time variance (ctv),existing algorithm,optimal solution,optimal schedule,job scheduling,efficient heuristic algorithm,job scheduling problem,identical parallel machine,just-in-time,large problem instance,optimization,computer experiment,heuristic algorithm | Mathematical optimization,Tardiness,Heuristic (computer science),Computer science,Network packet,Minification,Production planning,Job scheduler,Time variance,Operations management,The Internet | Journal |
Volume | Issue | ISSN |
58 | 4 | Computers & Industrial Engineering |
Citations | PageRank | References |
1 | 0.36 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xueping Li | 1 | 171 | 13.01 |
| Yuerong Chen | 2 | 18 | 2.33 |
| Yang Sun | 3 | 46 | 15.21 |