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

DOI10.1016/j.ejor.2022.03.043OpenAlexW4220715269MaRDI QIDQ2102995

Kyparisis, George J., Christos P. Koulamas

Publication date: 12 December 2022

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2022.03.043

zbMATH Keywords

schedulingdynamic programmingsingle-machine

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites Work

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

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