Scheduling problem: complexity analysis and polynomially solvable subclasses

DOI10.1515/DMA.1996.6.5.435MaRDI QIDQ3125964zbMATH OpenOpenAlexFDO

Authors Yu. S. Fedosenko, Dmitry Kogan

Publication date 23 March 1997

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma.1996.6.5.435

zbMATH Keywords

finite deterministic flow of claimsNP- complexitypolynomial algorithmsrecursive dynamic programmingsingle server

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Recommendations

• scientific article; zbMATH DE number 4031379
• scientific article; zbMATH DE number 3882159
• On schedules of works on a computer with running times depending nonlinearly on time
• scientific article; zbMATH DE number 3891075
• scientific article; zbMATH DE number 4099022

Cited in

(10)

• A note on `Efficient scheduling of periodic information monitoring requests'
• On the extension complexity of scheduling polytopes
• Polynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting
• Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedra
• On schedules of works on a computer with running times depending nonlinearly on time
• Complete Complexity Classification of Short Shop Scheduling
• scientific article; zbMATH DE number 1560545 (Why is no real title available?)
• scientific article; zbMATH DE number 850294 (Why is no real title available?)
• Models and optimization problems for single-processor servicing of packets of objects
• Optimal servicing strategy design problems for stationary objects in a one-dimensional working zone of a processor

This page was built for publication: Scheduling problem: complexity analysis and polynomially solvable subclasses

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