Minimizing maximum lateness on one machine: computational experience and some applications

DOI10.1111/J.1467-9574.1976.TB00264.XzbMath0336.90029OpenAlexW2120142199MaRDI QIDQ4103320

B. J. Lageweg, Alexander H. G. Rinnooy Kan, Jan Karel Lenstra

Publication date: 1976

Published in: Statistica Neerlandica (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/21640

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Formal languages and automata (68Q45) Deterministic scheduling theory in operations research (90B35) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (42)

A block approach for single-machine scheduling with release dates and due dates ⋮ Adjustment of heads and tails for the job-shop problem ⋮ Scheduling jobs with release dates and tails on identical machines to minimize the makespan ⋮ Dominance-based heuristics for one-machine total cost scheduling problems ⋮ A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates ⋮ A sequencing problem with family setup times ⋮ An algorithm for single machine sequencing with release dates to minimize maximum cost ⋮ Parallel batch scheduling of equal-length jobs with release and due dates ⋮ An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints ⋮ New single machine and job-shop scheduling problems with availability constraints ⋮ A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times ⋮ Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach ⋮ A procedure for the one-machine sequencing problem with dependent jobs ⋮ Polynomially solvable subcases for the approximate solution of multi-machine scheduling problems ⋮ Solving the resource constrained deadline scheduling problem via reduction to the network flow problem ⋮ A historical note on the complexity of scheduling problems ⋮ A survey of results for sequencing problems with controllable processing times ⋮ Probabilistic single processor scheduling ⋮ Applying new dominance concepts to job schedule optimization ⋮ The one-machine sequencing problem ⋮ Single facility multi-class job scheduling ⋮ An algorithm for single machine sequencing with release dates to minimize total weighted completion time ⋮ Surrogate duality relaxation for job shop scheduling ⋮ Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan ⋮ A metric approach for scheduling problems with minimizing the maximum penalty ⋮ Match-up scheduling of mixed-criticality jobs: maximizing the probability of jobs execution ⋮ Coupling genetic local search and recovering beam search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates ⋮ Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times ⋮ Jackson's pseudo-preemptive schedule and cumulative scheduling problems ⋮ Unnamed Item ⋮ A heuristic approach for single-machine scheduling with due dates and class setups. ⋮ Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints ⋮ Jackson's semi-preemptive scheduling on a single machine ⋮ Simple algorithms for multiprocessor scheduling to meet deadlines ⋮ Deadline scheduling of tasks with ready times and resource constraints ⋮ About one algorithm for solving scheduling problem ⋮ Reduction of job-shop problems to flow-shop problems with precedence constraints ⋮ New directions in scheduling theory ⋮ Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem ⋮ An approximation algorithm for a single-machine scheduling problem with release times and delivery times ⋮ A note on generalizing the maximum lateness criterion for scheduling ⋮ Minimizing makespan on parallel machines subject to release dates and delivery times

Cites Work

This page was built for publication: Minimizing maximum lateness on one machine: computational experience and some applications