Scheduling with semaphore constraints

DOI10.1016/0167-6377(87)90023-XMaRDI QIDQ1096534zbMATH OpenOpenAlexFDO

Authors Errol L. Lloyd

Publication date 1987

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

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

zbMATH Keywords

linear time algorithmminimum length schedulingNP-completenesssemaphore constraintstask systems

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Review text

We consider task systems with semaphore constraints, a generalization of the standard deterministic scheduling model that allows a broad class of task dependencies. We show that minimum length scheduling of task systems with semaphore constraints is NP-complete on two processors even when the tasks have identical execution times. In addition, we provide a linear time algorithm for determining the consistency of a task system with semaphore constraints.

Recommendations

• Scheduling with Concurrency-Based Constraints
• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• Scheduling multiprocessor tasks with chain constraints
• Complexity of Scheduling Parallel Task Systems
• Scheduling Periodic Tasks

Cites work

• Bounds on list scheduling of UET tasks with restricted resource constraints
• Concurrent Task Systems
• scientific article; zbMATH DE number 3757695 (Why is no real title available?)
• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• scientific article; zbMATH DE number 3557249 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• On the computational power of pushdown automata

Cited in

(1)

• Scheduling with Concurrency-Based Constraints

This page was built for publication: Scheduling with semaphore constraints

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