Single machine scheduling problems with financial resource constraints: some complexity results and properties (Q554491): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q57633864, #quickstatements; #temporary_batch_1707161894653 |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:37, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Single machine scheduling problems with financial resource constraints: some complexity results and properties |
scientific article |
Statements
Single machine scheduling problems with financial resource constraints: some complexity results and properties (English)
0 references
4 August 2011
0 references
In this paper single-machine scheduling problems with a non-renewable resource are studied. Given is a set of jobs \(j=1,\ldots,n\) with processing times \(p_j\) which have to be processed on a single machine. Furthermore, a non-renewable resource is given, which becomes available at specified points in time and is consumed by the jobs. The goal is to find a feasible schedule respecting the resource constraints and minimizing a given objective function. It is shown that the problem is strongly NP-hard for the makespan objective, minimizing the total tardiness (even if all due dates are the same) and that it is NP-hard for the total completion time. Afterwards, structural properties for special cases of the tardiness problem are studied. Finally, the so-called budget problem minimizing the makespan is considered.
0 references
scheduling
0 references
non-renewable resource
0 references
complexity
0 references