| Tartalmi leírás: |
The paper presents new approximability results for single machine scheduling problems with jobs requiring
some non-renewable resources (like raw materials, energy, or money) beside the machine. Each resource has
an initial stock and additional supplies over time. A feasible schedule specifies a starting time for each job
such that no two jobs overlap in time, and when a job is started, enough resources are available to cover
its requirements. The goal is to find a feasible schedule of minimum makespan. This problem is strongly
NP-hard.
Recently, the authors of this paper have proposed a PTAS for the special case with a single non-renewable
resource and with a constant number of supply dates, as well as an FPTAS for the special case with two
supply dates and one resource only. In this paper we prove APX-hardness of the problem when the number
of resources is part of the input, and new polynomial time approximation schemes are devised for some
variants, including (1) job release dates, and more than one, but constant number of resources and resource
supply dates, and (2) only one resource, arbitrary number of supply dates and job release dates, but with
resource requirements proportional to job processing times.
|
