Equitable scheduling on a single machine
From MaRDI portal
Abstract: We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem at once. In particular, we have clients over a period of days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the days, so that each client is guaranteed to have their job meet its deadline in at least days. This corresponds to an equitable schedule where each client is guaranteed a minimal level of service throughout the period of days. We provide a thorough analysis of the computational complexity of three main variants of this problem, identifying both efficient algorithms and worst-case intractability results.
Recommendations
- A fast algorithm for multi-machine scheduling problems with jobs of equal processing times
- Scheduling equal length jobs with eligibility restrictions
- Single machine scheduling subject to deadlines and resource dependent processing times
- A study of single-machine scheduling problem to maximize throughput
- Scheduling jobs on a single machine with periodic release date/deadline intervals
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A Simple Optimality Proof of Moore's Sequencing Algorithm
- A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
- A survey of single machine scheduling to minimize weighted number of tardy jobs
- A time-oriented branch-and-bound algorithm for resource-constrained project scheduling with generalised precedence constraints
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
- Bin packing with fixed number of bins revisited
- Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem
- Complexity of Scheduling under Precedence Constraints
- Complexity results for scheduling chains on a single machine
- Economics and computation. An introduction to algorithmic game theory, computational social choice, and fair division
- Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
- Fairness Measures for Resource Allocation
- Fast algorithms for bin packing
- Fundamentals of parameterized complexity
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Integer Programming with a Fixed Number of Variables
- Job Shop Scheduling with Unit Processing Times
- Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
- Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs
- On Representatives of Subsets
- On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs
- On the complexity of deciding whether the regular number is at most two
- On the minmax common-due-date problem: extensions to position-dependent processing times, job rejection, learning effect, uniform machines and flowshops
- On the parameterized tractability of single machine scheduling with rejection
- On the parameterized tractability of the just-in-time flow-shop scheduling problem
- On the parametric complexity of schedules to minimize tardy tasks.
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Parameterized algorithms
- Parameterized complexity of machine scheduling: 15 open problems
- Parameterized multi-scenario single-machine scheduling problems
- Parametrized complexity theory.
- Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
- Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
- Proportionate progress: A notion of fairness in resource allocation
- Reducibility among combinatorial problems
- Scheduling and fixed-parameter tractability
- Scheduling equal-length jobs on identical parallel machines
- Scheduling unit processing time jobs on a single machine with multiple criteria
- Scheduling with AND/OR Precedence Constraints
- Scheduling with common due date, earliness and tardiness penalties for multimachine problems: a survey
- Single-Machine Scheduling with Precedence Constraints
- Single-machine common due date total earliness/tardiness scheduling with machine unavailability
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- Some simplified NP-complete graph problems
- Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time
- The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints
- The price of fairness
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
Cited in
(5)- A multivariate complexity analysis of the material consumption scheduling problem
- Trade-off between utility and fairness in two-agent single-machine scheduling
- Fairness in repetitive scheduling
- Single-machine scheduling to minimize the number of tardy jobs with release dates
- Fair repetitive interval scheduling
This page was built for publication: Equitable scheduling on a single machine
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103750)
