Positive half-products and scheduling with controllable processing times

Positive half-products and scheduling with controllable processing times

0.00 Avg rating0 Votes
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: , , ,
Keywords: computational analysis, programming: integer
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.