A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems

Cites Work

Single machine scheduling with batch deliveries
A Dynamic Programming Approach to Sequencing Problems
Exact algorithms for inventory constrained scheduling on a single machine
Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
Techniques for scheduling with rejection
A Functional Equation and its Application to Resource Allocation and Sequencing Problems
Single machine scheduling with release dates and rejection
Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs
A survey of the state-of-the-art of common due date assignment and scheduling research
Scheduling a single machine with parallel batching to minimize makespan and total rejection cost
Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem
A survey on offline scheduling with rejection
Algorithms for Scheduling Independent Tasks
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
Single-machine scheduling under the job rejection constraint
Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
A multiple-criterion model for machine scheduling
A survey on scheduling problems with due windows
Scheduling Problems with Two Competing Agents
A note on the scheduling with two families of jobs
Preemptive scheduling with rejection
Single machine scheduling with scenarios
Scheduling with limited machine availability
An exact algorithm for single-machine scheduling without machine idle time
A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
Revised delivery-time quotation in scheduling with tardiness penalties
Minimizing Total Tardiness on One Machine is NP-Hard
Supply Chain Scheduling: Batching and Delivery
An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
Single machine scheduling with deadlines and increasing rates of processing times
A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization
Scheduling the production of two-component jobs on a single machine
Single-machine scheduling with production and rejection costs to minimize the maximum earliness
A state-of-the-art review on scheduling with learning effects
On the Complexity of Scheduling with Batch Setup Times
A bicriteria approach to scheduling a single machine with job rejection and positional penalties
The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan
Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling
Scheduling linear deteriorating jobs with rejection on a single machine
A dynamic programming method for single machine scheduling
An exact algorithm for the precedence-constrained single-machine scheduling problem
Single machine scheduling with delivery dates and cumulative payoffs
Single-machine scheduling problems with past-sequence-dependent setup times
Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
On J -maximal and J -minimal Flow-Shop Schedules
Bicriterion Single Machine Scheduling with Resource Dependent Processing Times
The single-machine total tardiness scheduling problem: review and extensions
A concise survey of scheduling with time-dependent processing times
Parallel machine scheduling with additional resources: notation, classification, models and solution methods
Single-machine multi-agent scheduling problems with a global objective function
Machine scheduling with an availability constraint
An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem
Near-optimal solutions of large-scale single-machine scheduling problems
Rescheduling for Job Unavailability
Sequencing with Earliness and Tardiness Penalties: A Review
Rescheduling for New Orders
Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
Makespan minimization in single-machine scheduling with step-deterioration of processing times
Two due date assignment problems in scheduling a single machine
Dynamic programming and decomposition approaches for the single machine total tardiness problem
Machine scheduling with a rate-modifying activity
A decomposition algorithm for the single machine total tardiness problem
A fully polynomial approximation scheme for the total tardiness problem
Improving the complexities of approximation algorithms for optimization problems
Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times
New Precedence Theorems for One-Machine Weighted Tardiness
Batch delivery scheduling with batch delivery cost on a single machine
Scheduling shops to minimize the weighted number of late jobs
Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
An exponential neighborhood for a one-machine batching problem
A single machine scheduling problem to minimize total early work
Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs
Single Machine Scheduling to Minimize Total Late Work
Batch scheduling and common due-date assignment on a single machine
Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs
An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
Single-machine scheduling with trade-off between number of tardy jobs and resource allocation
Preemptive scheduling of equal-length jobs to maximize weighted throughput.
Single Machine Scheduling with Deadlines to Minimize the Weighted Number of Tardy Jobs
Single machine scheduling problems with subcontracting options
Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
Non deterministic polynomial optimization problems and their approximations
Algorithms and Data Structures
Single-machine scheduling with a common due window
A faster algorithm for a due date assignment problem with tardy jobs
Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems
Minimizing the total weighted flow time in a single machine with controllable processing times
Scheduling linear deteriorating jobs with an availability constraint on a single machine
Batch Delivery Scheduling on a Single Machine
Single Machine Scheduling to Minimize Batch Delivery and Job Earliness Penalties
Single machine scheduling and due date assignment with positionally dependent processing times
Approximation algorithms for scheduling a single machine to minimize total late work
Machine scheduling with job class setup and delivery considerations
Mimimization of agreeably weighted variance in single machine systems
On the Minimization of Completion Time Variance with a Bicriteria Extension
A Dynamic Programming Solution to the Dynamic, Multi-Item, Single-Machine Scheduling Problem
Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks
Single machine scheduling with discretely controllable processing times
A time-dependent multiple criteria single-machine scheduling problem
Scheduling two job classes on a single machine
A review of TSP based approaches for flowshop scheduling
Evolutionary algorithms and dynamic programming
Single machine batch scheduling with deadlines and resource dependent processing times
Minimizing the total completion time in a unit-time open shop with release times
Optimal schedules for single facility with two job classes
An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine
Scheduling deteriorating jobs to minimize makespan
Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine
A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work
Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work
CON/SLK due date assignment and scheduling on a single machine with two agents
A dynamic programming algorithm for single machine scheduling with ready times
Single Machine Scheduling with Precedence Constraints of Dimension 2
Single Machine Scheduling with Series-Parallel Precedence Constraints
The proportionate flow shop total tardiness problem
Earliness-Tardiness Scheduling Around Almost Equal Due Dates
Single Machine Scheduling to Minimize Total Weighted Late Work
Minmax scheduling with acceptable lead-times: extensions to position-dependent processing times, due-window and job rejection
Two-agent scheduling with rejection on a single machine
Single machine lot scheduling with optional job-rejection
Minimizing total late work on a single machine with generalized due-dates
Single-machine scheduling with release times, deadlines, setup times, and rejection
New results for scheduling to minimize tardiness on one machine with rejection and related problems
Mirror scheduling problems with early work and late work criteria
New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives
Single-machine common due date total earliness/tardiness scheduling with machine unavailability
Scheduling with partial rejection
The construction of ε-approximate algorithms for the optimization of functions in successively constructed sets
HEURISTIC FOR MINIMIZING THE NUMBER OF LATE JOBS ON TWO PROCESSORS
Proportionate flow shop: New complexity results and models with due date assignment
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)

This page was built for publication: A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems

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