Single machine scheduling problems with financial resource constraints: some complexity results and properties (Q554491): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Sigrid Knust / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90B35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 91B32 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q25 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5935943 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
scheduling | |||
Property / zbMATH Keywords: scheduling / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
non-renewable resource | |||
Property / zbMATH Keywords: non-renewable resource / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
complexity | |||
Property / zbMATH Keywords: complexity / rank | |||
Normal rank |
Revision as of 14:23, 1 July 2023
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