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

DOI10.15807/jorsj.22.205zbMath0427.90049OpenAlexW2186333639MaRDI 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 analysisnumerical studyready timesrandomly generated problemsworst case performanceminimization of maximum latenessdue timesone- machine schedulingsix approximation algorithms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Deterministic scheduling theory in operations research (90B35) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

A sequencing problem with family setup times, A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times, Patients scheduling problems with deferred deteriorated functions, An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown, Scheduling Algorithms for Single Machine Problem with Release and Delivery Times, Domination analysis of combinatorial optimization problems., Optimal algorithms for online single machine scheduling with deteriorating jobs, Single-machine scheduling problems with time and position dependent processing times, Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times, Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times, Optimal on-line algorithms for single-machine scheduling, A best on-line algorithm for single machine scheduling with small delivery times, Notes on ``Some single-machine scheduling problems with general position-dependent and time-dependent learning effects, Jackson's semi-preemptive scheduling on a single machine, Parallel machine scheduling with nested processing set restrictions and job delivery times, Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints, 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, Scheduling a single machine with primary and secondary objectives, Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon, An approximation algorithm for a single-machine scheduling problem with release times and delivery times