Article ID: | iaor20062049 |
Country: | Netherlands |
Volume: | 165 |
Issue: | 2 |
Start Page Number: | 416 |
End Page Number: | 422 |
Publication Date: | Sep 2005 |
Journal: | European Journal of Operational Research |
Authors: | Kubiak Wieslaw, Werner Frank, Janiak Adam, Kovalyov Mikhail Y. |
Keywords: | computational analysis, programming: integer |
We study the single machine scheduling problem with controllable job processing times to minimize a linear combination of the total weighted jobs 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.