Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates

DOI10.1287/opre.36.4.553zbMath0652.90063OpenAlexW2078331920MaRDI QIDQ3798473

C. Y. Liu, Robert L. Bulfin

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1287/opre.36.4.553

zbMATH Keywords

open shoppolynomial algorithmstotal tardinessm machinesscheduling n jobsidentical processing time jobs

Mathematics Subject Classification ID

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

Related Items

Minimizing the weighted number of tardy jobs on multiple machines: a review ⋮ On complexity of minimizing weighted number of late jobs in unit time open shops ⋮ Minimizing the total completion time in a unit-time open shop with release times ⋮ A branch \(\&\) bound algorithm for the open-shop problem ⋮ Open shop problems with unit time operations ⋮ On minimizing the weighted number of late jobs in unit execution time open-shops. ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Scheduling ordered open shops ⋮ Minimizing the weighted number of late jobs in UET open shops ⋮ A polynomial algorithm for an open shop problem with unit processing times and tree constraints ⋮ The generalized shifting bottleneck procedure ⋮ Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop ⋮ Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints ⋮ Scheduling unit time open shops to minimize the weighted number of late jobs ⋮ A polynomial algorithm for the \([n/m/0,\;t_{ij}=1,\text{ tree}/C_{\max}\) open shop problem]