A polynomial time algorithm for a chance-constrained single machine scheduling problem

DOI10.1016/0167-6377(83)90038-XzbMath0506.90039OpenAlexW2032618916MaRDI QIDQ1837104

Toshihide Ibaraki, Naoki Katoh

Publication date: 1983

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(83)90038-x

zbMATH Keywords

single machinepolynomial time algorithmNP-hardnesschance-constrained sequencing problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items

Minimizing the expected weighted number of tardy jobs in stochastic flow shops, General stochastic single-machine scheduling with regular cost functions, Single Machine Stochastic Scheduling: Minimizing the Number of Tardy Jobs, A polynomial-time algorithm for a nonconvex chance-constrained program under the normal approximation, An \(\varepsilon\)-approximation scheme for combinatorial optimization problems with minimum variance criterion, A fully polynomial time approximation scheme for minimum cost-reliability ratio problems, A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program, An efficient algorithm for the parametric resource allocation problem, Analysis of a class of proxy problems, A class of nonseparable dynamic programming problems

Cites Work

• Stochastic spanning tree problem
• Note—On Baluts Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem
• An Algorithm for the Equipollent Resource Allocation Problem
• AN EFFICIENT ALGORITHM FOR A CHANCE-CONSTRAINED SCHEDULING PROBLEM
• Scheduling to Minimize the Number of Late Jobs When Set-Up and Processing Times are Uncertain