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

scientific article

Language	Label	Description	Also known as
English	A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems	scientific article

Statements

instance of

scholarly article

0 references

title

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

0 references

DOI

10.1016/j.ejor.2022.03.043

0 references

published in

European Journal of Operational Research

0 references

publication date

12 December 2022

0 references

Mathematics Subject Classification ID

0 references

0 references

scheduling

0 references

single-machine

0 references

dynamic programming

0 references

0 references

0 references

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.ejor.2022.03.043

0 references

OpenAlex ID

W4220715269

0 references

cites work

Dynamic Programming State-Space Relaxation for Single-Machine Scheduling

0 references

Scheduling Problems with Two Competing Agents

0 references

Near-Optimal Solutions of Large-Scale Single-Machine Scheduling Problems

0 references

A review of TSP based approaches for flowshop scheduling

0 references

Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems

0 references

Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks

0 references

Sequencing with Earliness and Tardiness Penalties: A Review

0 references

A multiple-criterion model for machine scheduling

0 references

An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

0 references

Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times

0 references

Preemptive scheduling of equal-length jobs to maximize weighted throughput.

0 references

Q3241581

0 references

A single machine scheduling problem to minimize total early work

0 references

A state-of-the-art review on scheduling with learning effects

0 references

Exact algorithms for inventory constrained scheduling on a single machine

0 references

Q4873242

0 references

Single-machine common due date total earliness/tardiness scheduling with machine unavailability

0 references

Single Machine Scheduling with Series-Parallel Precedence Constraints

0 references

Mimimization of agreeably weighted variance in single machine systems

0 references

Mirror scheduling problems with early work and late work criteria

0 references

Single machine scheduling with discretely controllable processing times

0 references

Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs

0 references

Single-machine scheduling with trade-off between number of tardy jobs and resource allocation

0 references

Single machine scheduling with deadlines and increasing rates of processing times

0 references

A concise survey of scheduling with time-dependent processing times

0 references

Batch Delivery Scheduling on a Single Machine

0 references

Single machine scheduling with batch deliveries

0 references

Bicriterion Single Machine Scheduling with Resource Dependent Processing Times

0 references

Single machine batch scheduling with deadlines and resource dependent processing times

0 references

Batch scheduling and common due-date assignment on a single machine

0 references

Single Machine Scheduling to Minimize Batch Delivery and Job Earliness Penalties

0 references

Machine scheduling with job class setup and delivery considerations

0 references

Scheduling linear deteriorating jobs with rejection on a single machine

0 references

On J -maximal and J -minimal Flow-Shop Schedules

0 references

An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem

0 references

A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization

0 references

On the Minimization of Completion Time Variance with a Bicriteria Extension

0 references

Single-machine scheduling with release times, deadlines, setup times, and rejection

0 references

Evolutionary algorithms and dynamic programming

0 references

Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs

0 references

Minimizing Total Tardiness on One Machine is NP-Hard

0 references

Parallel machine scheduling with additional resources: notation, classification, models and solution methods

0 references

Techniques for scheduling with rejection

0 references

Q4287985

0 references

Two-agent scheduling with rejection on a single machine

0 references

A Dynamic Programming Solution to the Dynamic, Multi-Item, Single-Machine Scheduling Problem

0 references

A dynamic programming algorithm for single machine scheduling with ready times

0 references

Scheduling the production of two-component jobs on a single machine

0 references

Minmax scheduling with acceptable lead-times: extensions to position-dependent processing times, due-window and job rejection

0 references

A survey of the state-of-the-art of common due date assignment and scheduling research

0 references

Single machine scheduling and due date assignment with positionally dependent processing times

0 references

Q4934199

0 references

Optimal schedules for single facility with two job classes

0 references

Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better

0 references

Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date

0 references

Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date

0 references

Supply Chain Scheduling: Batching and Delivery

0 references

Rescheduling for New Orders

0 references

Rescheduling for Job Unavailability

0 references

Single Machine Scheduling with Deadlines to Minimize the Weighted Number of Tardy Jobs

0 references

Single Machine Scheduling to Minimize Total Weighted Late Work

0 references

Scheduling a single machine with parallel batching to minimize makespan and total rejection cost

0 references

A Dynamic Programming Approach to Sequencing Problems

0 references

Preemptive scheduling with rejection

0 references

Earliness-Tardiness Scheduling Around Almost Equal Due Dates

0 references

An exponential neighborhood for a one-machine batching problem

0 references

A dynamic programming method for single machine scheduling

0 references

Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

0 references

A survey on scheduling problems with due windows

0 references

Makespan minimization in single-machine scheduling with step-deterioration of processing times

0 references

Scheduling linear deteriorating jobs with an availability constraint on a single machine

0 references

Batch delivery scheduling with batch delivery cost on a single machine

0 references

Scheduling shops to minimize the weighted number of late jobs

0 references

Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval

0 references

Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times

0 references

New Precedence Theorems for One-Machine Weighted Tardiness

0 references

A time-dependent multiple criteria single-machine scheduling problem

0 references

Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine

0 references

Q3320130

0 references

The single-machine total tardiness scheduling problem: review and extensions

0 references

A faster algorithm for a due date assignment problem with tardy jobs

0 references

The proportionate flow shop total tardiness problem

0 references

New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives

0 references

New results for scheduling to minimize tardiness on one machine with rejection and related problems

0 references

Single-machine scheduling problems with past-sequence-dependent setup times

0 references

Improving the complexities of approximation algorithms for optimization problems

0 references

A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work

0 references

The construction of ε-approximate algorithms for the optimization of functions in successively constructed sets

0 references

Scheduling deteriorating jobs to minimize makespan

0 references

Q4124332

0 references

A fully polynomial approximation scheme for the total tardiness problem

0 references

A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

0 references

A Functional Equation and its Application to Resource Allocation and Sequencing Problems

0 references

Machine scheduling with an availability constraint

0 references

Machine scheduling with a rate-modifying activity

0 references

HEURISTIC FOR MINIMIZING THE NUMBER OF LATE JOBS ON TWO PROCESSORS

0 references

Scheduling with partial rejection

0 references

Single-machine scheduling with production and rejection costs to minimize the maximum earliness

0 references

Single machine scheduling with scenarios

0 references

On the Complexity of Scheduling with Batch Setup Times

0 references

An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs

0 references

Single machine lot scheduling with optional job-rejection

0 references

Minimizing total late work on a single machine with generalized due-dates

0 references

Proportionate flow shop: New complexity results and models with due date assignment

0 references

Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem

0 references

Non deterministic polynomial optimization problems and their approximations

0 references

Scheduling two job classes on a single machine

0 references

A decomposition algorithm for the single machine total tardiness problem

0 references

Dynamic programming and decomposition approaches for the single machine total tardiness problem

0 references

Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs

0 references

Single Machine Scheduling to Minimize Total Late Work

0 references

Approximation algorithms for scheduling a single machine to minimize total late work

0 references

Algorithms for Scheduling Independent Tasks

0 references

Scheduling with limited machine availability

0 references

Dynamic Programming Solution of Sequencing Problems with Precedence Constraints

0 references

Single machine scheduling with delivery dates and cumulative payoffs

0 references

Algorithms and Data Structures

0 references

A survey on offline scheduling with rejection

0 references

A bicriteria approach to scheduling a single machine with job rejection and positional penalties

0 references

Minimizing the total weighted flow time in a single machine with controllable processing times

0 references

Two due date assignment problems in scheduling a single machine

0 references

Single Machine Scheduling with Precedence Constraints of Dimension 2

0 references

Revised Delivery-Time Quotation in Scheduling with Tardiness Penalties

0 references

A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time

0 references

An exact algorithm for single-machine scheduling without machine idle time

0 references

An exact algorithm for the precedence-constrained single-machine scheduling problem

0 references

Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling

0 references

Minimizing the total completion time in a unit-time open shop with release times

0 references

Single-machine multi-agent scheduling problems with a global objective function

0 references

Q3989986

0 references

An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine

0 references

When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

0 references

Single-machine scheduling with a common due window

0 references

CON/SLK due date assignment and scheduling on a single machine with two agents

0 references

Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

0 references

The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan

0 references

A note on the scheduling with two families of jobs

0 references

Single machine scheduling with release dates and rejection

0 references

Single-machine scheduling under the job rejection constraint

0 references

Single machine scheduling problems with subcontracting options

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2102995