Single machine scheduling problems with financial resource constraints: some complexity results and properties (Q554491): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 5 users not shown) | |||
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 | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q57633864 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.mathsocsci.2011.04.004 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2108940302 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Scheduling subject to nonrenewable-resource constraints / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimizing Total Tardiness on One Machine is NP-Hard / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3741388 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4124332 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A special case of the single-machine total tardiness problem is NP-hard / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4055377 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A decomposition algorithm for the single machine total tardiness problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Preemptive scheduling of independent jobs on parallel machines subject to financial constraints / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Solution of the single machine total tardiness problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Scheduling under a Non-renewable Resource Constraint / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:35, 4 July 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
0 references