Note—On Baluts Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem

DOI10.1287/mnsc.29.3.384zbMath0513.90039OpenAlexW2124713686MaRDI QIDQ3659513

Toshihide Ibaraki, Hiroshi Kise

Publication date: 1983

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.29.3.384

zbMATH Keywords

NP-completenessrandom processing timesBalut's algorithmchance-constrained schedulingminimization of the number of tardy jobsn-job one- machine scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

The stochastic single machine scheduling problem with earliness and tardiness costs, Minimizing the number of tardy jobs with stochastically-ordered processing times, Minimizing the expected weighted number of tardy jobs in stochastic flow shops, Setting optimal due dates in a basic safe-scheduling model, Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem, Optimal sequences in stochastic single machine shops, General stochastic single-machine scheduling with regular cost functions, A survey of single machine scheduling to minimize weighted number of tardy jobs, Single Machine Stochastic Scheduling: Minimizing the Number of Tardy Jobs, On the minimization of the weighted number of tardy jobs with random processing times and deadline, Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs, A polynomial time algorithm for a chance-constrained single machine scheduling problem, Dynamic scheduling of stochastic jobs on a single machine, Minimizing earliness and tardiness costs in stochastic scheduling, Minimizing the expected number of tardy jobs when processing times are normally distributed