Scheduling with release dates on a single machine to minimize total weighted completion time

DOI10.1016/0166-218X(92)90255-9zbMath0757.90032OpenAlexW1994429799MaRDI QIDQ1193720

Chris N. Potts, Hocine Belouadah, Marc E. Posner

Publication date: 27 September 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90255-9

zbMATH Keywords

branch-and-boundNP-hardone machinenon-equal ready timesnonpreemptable, independent tasks

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Single machine scheduling with two competing agents, arbitrary release dates and unit processing times ⋮ A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties ⋮ Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval ⋮ Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ Dominance-based heuristics for one-machine total cost scheduling problems ⋮ Minimizing the sum of weighted completion times with unrestricted weights ⋮ Two-agent singe-machine scheduling with release times to minimize the total weighted completion time ⋮ A hybrid differential evolution approach based on surrogate modelling for scheduling bottleneck stages ⋮ Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time ⋮ Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time ⋮ Minimizing total completion time on a single machine with a flexible maintenance activity ⋮ Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems ⋮ EA/G-GA for single machine scheduling problems with earliness/tardiness costs ⋮ Dominance rules in combinatorial optimization problems ⋮ A global constraint for total weighted completion time for unary resources ⋮ Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods ⋮ A two-agent single-machine scheduling problem to minimize the total cost with release dates ⋮ Single-machine scheduling with no idle time and release dates to~minimize a regular criterion ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates ⋮ Reducibility among single machine weighted completion time scheduling problems ⋮ Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times ⋮ A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times ⋮ A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates ⋮ Efficient heuristics to minimize total flow time with release dates ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates ⋮ On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation ⋮ Scheduling a single machine to minimize a regular objective function under setup constraints ⋮ Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates ⋮ An exact approach to early/tardy scheduling with release dates ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time ⋮ Metaheuristics to solve a tasks scheduling problem in parallel identical machines with unavailability periods ⋮ Modeling single machine preemptive scheduling problems for computational efficiency ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems

Cites Work

• Unnamed Item
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• The one-machine sequencing problem
• An algorithm for single machine sequencing with release dates to minimize total weighted completion time
• Scheduling identical parallel machines to minimize total weighted completion time
• Scheduling of a single machine to minimize total weighted completion time subject to release dates
• Minimizing Weighted Completion Times with Deadlines
• Sequencing Jobs with Unequal Ready Times to Minimize Mean Flow Time
• On n/1/?? dynamic deterministic problems
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints