PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES

DOI10.15807/jorsj.22.205zbMath0427.90049MaRDI QIDQ3863414

Toshihide Ibaraki, Hisashi Mine, Hiroshi Kise

Publication date: 1979

Published in: Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.15807/jorsj.22.205

zbMATH Keywords

performance analysis; numerical study; ready times; randomly generated problems; worst case performance; minimization of maximum lateness; due times; one- machine scheduling; six approximation algorithms

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

65K10: Numerical optimization and variational techniques

90B35: Deterministic scheduling theory in operations research

68Q60: Specification and verification (program logics, model checking, etc.)

Related Items

Optimal algorithms for online single machine scheduling with deteriorating jobs, Notes on ``Some single-machine scheduling problems with general position-dependent and time-dependent learning effects, Single-machine scheduling problems with time and position dependent processing times, Jackson's semi-preemptive scheduling on a single machine, On-line scheduling with delivery time on a single batch machine, An optimal online algorithm for single machine scheduling with bounded delivery times, Approximability of flow shop scheduling, An approximation algorithm for a single-machine scheduling problem with release times and delivery times, Domination analysis of combinatorial optimization problems., A sequencing problem with family setup times, Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times, A best on-line algorithm for single machine scheduling with small delivery times