Scheduling a single machine with primary and secondary objectives (Q2331605)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Scheduling a single machine with primary and secondary objectives |
scientific article |
Statements
Scheduling a single machine with primary and secondary objectives (English)
0 references
30 October 2019
0 references
Summary: We study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme to minimize the maximum job lateness, with the secondary objective to minimize the maximum job completion time. The problem of finding the Pareto-optimal set of feasible solutions with these two objective criteria is strongly NP-hard. We give the dominance properties and conditions when the Pareto-optimal set can be formed in polynomial time. These properties, together with our general framework, provide the theoretical background, so that the basic framework can be expanded to (exponential-time) implicit enumeration algorithms and polynomial-time approximation algorithms (generating the Pareto sub-optimal frontier with a fair balance between the two objectives). Some available in the literature experimental results confirm the practical efficiency of the proposed framework.
0 references
scheduling single machine
0 references
release time
0 references
lateness
0 references
makespan
0 references
bi-criteria scheduling
0 references
Pareto-optimal solution
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references