Complexity of scheduling tasks with time-dependent execution times

DOI10.1016/0020-0190(93)90175-9zbMath0942.68508OpenAlexW1967855112MaRDI QIDQ1334634

Publication date: 25 September 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90175-9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

The complexity of scheduling starting time dependent tasks with release times ⋮ Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines ⋮ Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation ⋮ An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan ⋮ A note on scheduling on a single processor with speed dependent on a number of executed jobs ⋮ A fully polynomial-time approximation scheme for total completion time minimization on a single machine with DeJong's learning effect and an availability constraint ⋮ Minimizing total completion time in a two-machine flow shop with deteriorating jobs ⋮ A note on single-processor scheduling with time-dependent execution times ⋮ A dynamic programming algorithm for scheduling problems on earliness award and tardiness penalty with time-dependent processing time ⋮ Flow shop scheduling problems with decreasing linear deterioration under dominant machines ⋮ Single-machine time-dependent scheduling problems with fixed rate-modifying activities and resumable jobs ⋮ Scheduling Two-Agents with a Time-Dependent Deterioration to Minimize the Minsum Earliness Measures ⋮ Parallel machine scheduling with time dependent processing times ⋮ Two-agent scheduling of time-dependent jobs ⋮ Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration ⋮ Online Parallel-Batch Scheduling of Learning Effect Jobs with Incompatible Job Families for Prefabricated Components ⋮ Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times ⋮ A concise survey of scheduling with time-dependent processing times ⋮ Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties ⋮ Single-machine scheduling problems with time and position dependent processing times ⋮ Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties ⋮ Scheduling jobs with a V-shaped time-dependent processing time ⋮ Single machine group scheduling with decreasing time-dependent processing times subject to release dates ⋮ Single machine group scheduling under decreasing linear deterioration ⋮ Scheduling on a single processor with variable speed ⋮ Scheduling with time-dependent execution times ⋮ Scheduling jobs with varying processing times ⋮ Flow shop scheduling with effects of learning and deterioration ⋮ Scheduling time-dependent jobs under mixed deterioration ⋮ Parallel-machine scheduling with time dependent processing times ⋮ Learning effect and deteriorating jobs in the single machine scheduling problems ⋮ A note on single-machine scheduling with decreasing time-dependent job processing times ⋮ Single machine scheduling problems with deteriorating jobs ⋮ Scheduling linearly shortening jobs under precedence constraints ⋮ Scheduling in a contaminated area: a model and polynomial algorithms ⋮ Single machine scheduling with decreasing linear deterioration under precedence constraints ⋮ Greedy solutions of selection and ordering problems ⋮ Optimal composition ordering problems for piecewise linear functions ⋮ Parallel-batching machines scheduling problem with a truncated time-dependent learning effect via a hybrid CS-JADE algorithm ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems ⋮ Permutation Flow Shop Problem with Shortening Job Processing Times ⋮ Preemptive repayment policy for multiple loans ⋮ Conjugate problems in time-dependent scheduling ⋮ Scheduling jobs under decreasing linear deterioration ⋮ Equivalent time-dependent scheduling problems ⋮ Single-machine scheduling problems with precedence constraints and simple linear deterioration ⋮ SCHEDULING PROBLEMS WITH THE EFFECTS OF DETERIORATION AND LEARNING ⋮ 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

Cites Work