Computer-aided way to prove theorems in scheduling

DOI10.1007/3-540-68530-8_42MaRDI QIDQ4252045zbMATH OpenFDO

Authors Ilya Tchernykh, Sergey Sevastyanov

Publication date 17 June 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-68530-8_42

zbMATH Keywords

linear-time approximation algorithmstight boundsworst-case performance ratios

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• An existence theorem for packing problems with implications for the computation of optimal machine schedules
• On the optima localization for the three-machine routing open shop
• Computer-Aided complexity classification of combinational problems
• A problem in scheduling theory

Cited in

(17)

• A manifesto for the computational method
• A 6 5-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• Two-machine routing open shop: How long is the optimal makespan?
• Exponential tightness for integral-type functionals of centered independent differently distributed random variables
• Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
• Four decades of research on the open-shop scheduling problem to minimize the makespan
• Irreducible bin packing and normality in routing open shop
• Some positive news on the proportionate open shop problem
• Cellular automata approach to scheduling problem in case of modifications of a program graph
• The three-machine proportionate open shop and mixed shop minimum makespan problems
• The open shop scheduling problem
• An existence theorem for packing problems with implications for the computation of optimal machine schedules
• scientific article; zbMATH DE number 7362744 (Why is no real title available?)
• Polynomial time approximation algorithms for proportionate open-shop scheduling
• Linear time approximation scheme for the multiprocessor open shop problem
• Branch‐and‐bound approach for optima localization in scheduling multiprocessor jobs
• Minimizing the sojourn time of open shop scheduling problems with unit-time operations

This page was built for publication: Computer-aided way to prove theorems in scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4252045)