Minimizing the number of tardy job units under release time constraints

DOI10.1016/0166-218X(90)90093-RzbMath0707.90049MaRDI QIDQ919993

Ron Shamir, Dorit S. Hochbaum

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

single-machine schedulingrelease timesMonge sequencestrongly polynomial algorithmstardy units

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (24)

Minimizing the weighted number of tardy task units ⋮ Scheduling High Multiplicity Jobs on Parallel Multi-Purpose Machines with Setup Times and Machine Available Times ⋮ An alternative approach for proving the NP-hardness of optimization problems ⋮ Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date ⋮ The assignment problem with nearly Monge arrays and incompatible partner indices ⋮ A single machine scheduling problem to minimize total early work ⋮ A survey of single machine scheduling to minimize weighted number of tardy jobs ⋮ Variable neighborhood search for the single machine scheduling problem to minimize the total early work ⋮ Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work ⋮ Single-machine preemptive scheduling with release dates involving the total weighted late work criterion ⋮ Scheduling on parallel identical machines with late work criterion: offline and online cases ⋮ Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints ⋮ Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach ⋮ A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs ⋮ Monge and feasibility sequences in general flow problems ⋮ Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches ⋮ Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance ⋮ Multiplicity and complexity issues in contemporary production scheduling ⋮ Scheduling two agents with controllable processing times ⋮ Scheduling a proportionate flow shop of batching machines ⋮ Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines ⋮ Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works ⋮ A framework for the complexity of high-multiplicity scheduling problems ⋮ A polynomial algorithm for lot-size scheduling of two type tasks.

Cites Work

• Monge sequences, antimatroids, and the transportation problem with forbidden arcs
• A linear-time algorithm for a special case of disjoint set union
• A strongly polynomial minimum cost circulation algorithm
• An algorithm for the detection and construction of Monge sequences
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimizing the number of tardy job units under release time constraints