The complexity of scheduling starting time dependent tasks with release times
From MaRDI portal
Publication:293188
DOI10.1016/S0020-0190(97)00195-6zbMath1338.68096OpenAlexW1966457785MaRDI QIDQ293188
Publication date: 9 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097001956?np=y
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Parallel-machine serial-batching scheduling with release times under the effects of position-dependent learning and time-dependent deterioration ⋮ Algorithms for single-machine scheduling problem with deterioration depending on a novel model ⋮ Minimizing total completion time in a two-machine flow shop with deteriorating jobs ⋮ Flow shop scheduling problems with decreasing linear deterioration under dominant machines ⋮ Single-machine scheduling with deteriorating functions for job processing times ⋮ Patients scheduling problems with deferred deteriorated functions ⋮ Online scheduling with deterioration and unexpected processor breakdown ⋮ Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration ⋮ A concise survey of scheduling with time-dependent processing times ⋮ Some single-machine and flowshop scheduling problems with a non-linear deterioration function ⋮ Single-machine group scheduling problems with deterioration consideration ⋮ A single-machine scheduling with a truncated linear deterioration and ready times ⋮ A SINGLE-MACHINE DETERIORATING JOB SCHEDULING PROBLEM WITH A NON-REGULAR CRITERION ⋮ Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint ⋮ Single machine due-date scheduling of jobs with decreasing start-time dependent processing times ⋮ Scheduling linear deteriorating jobs to minimize the number of tardy jobs ⋮ Two scheduling problems in group technology with deteriorating jobs ⋮ Single machine scheduling problems with deteriorating jobs ⋮ Two-agent scheduling with position-based deteriorating jobs and learning effects ⋮ Single-machine group scheduling problems with deteriorated and learning effect ⋮ A note on scheduling problems with learning effect and deteriorating jobs ⋮ Single machine scheduling with decreasing linear deterioration under precedence constraints ⋮ Single machine scheduling with step-deteriorating processing times ⋮ A time-dependent multiple criteria single-machine scheduling problem ⋮ Optimal composition ordering problems for piecewise linear functions ⋮ Improved estimation of distribution algorithm for the problem of single-machine scheduling with deteriorating jobs and different due dates ⋮ Isomorphic scheduling problems ⋮ A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems ⋮ Single-machine group scheduling problems with deteriorating and learning effect ⋮ Mirror scheduling problems with early work and late work criteria ⋮ Conjugate problems in time-dependent scheduling ⋮ Scheduling jobs under decreasing linear deterioration ⋮ Equivalent time-dependent scheduling problems ⋮ A dynamic programming algorithm for the single-machine scheduling problem with deteriorating processing times ⋮ SCHEDULING PROBLEMS WITH THE EFFECTS OF DETERIORATION AND LEARNING ⋮ A note on the complexity of scheduling problems with linear job deterioration
Cites Work
- Complexity of scheduling tasks with time-dependent execution times
- Single machine scheduling with deadlines and increasing rates of processing times
- The complexity of single machine scheduling with two distinct deadlines and identical decreasing rates of processing times
- Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine
- Minimizing Total Tardiness on One Machine is NP-Hard
- Scheduling Deteriorating Jobs on a Single Processor
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
