Scheduling a single machine with primary and secondary objectives

DOI10.3390/A11060080MaRDI QIDQ2331605zbMATH OpenOpenAlexWikidataFDO

Authors Nodari Vakhania

Publication date 30 October 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a11060080

zbMATH Keywords

bi-criteria schedulinglatenessmakespanPareto-optimal solutionrelease timescheduling single machine

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Review text

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.

Recommendations

• The Pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine
• Pareto optima for total weighted completion time and maximum lateness on a single machine
• Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work
• Minimizing Maximum Promptness and Maximum Lateness on a Single Machine
• Scheduling unit processing time jobs on a single machine with multiple criteria

Cites work

• A better algorithm for sequencing with release and delivery times on identical machines
• A block approach for single-machine scheduling with release dates and due dates
• An approximation algorithm for a single-machine scheduling problem with release times and delivery times
• Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times
• Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
• Jackson's semi-preemptive scheduling on a single machine
• Multicriteria Optimization
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
• On single-machine scheduling without intermediate delays
• PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
• Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan
• Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• The one-machine sequencing problem
• The Pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine
• Theoretical expectation versus practical performance of Jackson's heuristic

Cited in

(7)

• The Pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine
• Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines
• Editorial. Special issue on algorithms for scheduling problems
• Pareto optima for total weighted completion time and maximum lateness on a single machine
• Primary-secondary bicriteria scheduling on identical machines to minimize the total completion time of all jobs and the maximum T-time of all machines
• Bicriterion Pareto‐scheduling of equal‐length jobs on a single machine related to the total weighted late work
• Approximation schemes for scheduling jobs on identical parallel machines to minimize the maximum lateness and makespan

This page was built for publication: Scheduling a single machine with primary and secondary objectives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2331605)