Name
Abstract | ||
|---|---|---|
We study the single machine scheduling problem with controllable job processing times to minimize a linear combination of the total weighted job completion time and the total weighted processing time compression. We show that this scheduling problem is a positive half-product minimization problem. Positive half-products make up an interesting subclass of half-products and are introduced in this paper to provide a conceptual framework for the problem with controllable job processing times as well as other problems. This framework allows to readily derive in one fell swoop a number of results for the problem with controllable processing times from more general results obtained earlier for the half-product. We also present fast fully polynomial time approximation schemes for the problem with controllable processing times. The schemes apply to all positive half-products. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.ejor.2004.04.012 | European Journal of Operational Research |
Keywords | Field | DocType |
Single machine scheduling,Controllable processing times,Pseudo-Boolean optimization,Fully polynomial time approximation scheme,Computational complexity | Linear combination,Mathematical optimization,Single-machine scheduling,Job shop scheduling,Controllability,Scheduling (computing),Algorithm,Time complexity,Polynomial-time approximation scheme,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
165 | 2 | 0377-2217 |
Citations | PageRank | References |
21 | 1.08 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adam Janiak | 1 | 772 | 51.89 |
| Mikhail Y. Kovalyov | 2 | 1602 | 118.18 |
| Wieslaw Kubiak | 3 | 540 | 62.61 |
| Frank Werner | 4 | 518 | 53.24 |