登入
選單
返回
Google圖書搜尋
Scheduling Tasks with AND/OR Precedence Constraints
Donald W. Gillies
Jane W. S. Liu
University of Illinois at Urbana-Champaign. Department of Computer Science
出版
Department of Computer Science, University of Illinois
, 1991
URL
http://books.google.com.hk/books?id=8h7eHaCdj3wC&hl=&source=gbs_api
註釋
Abstract: "In traditional precedence-constrained scheduling a task is ready to execute when all its predecessors are complete. We call such a task an AND task. In this paper we allow certain tasks to be ready when just one of their predecessors is complete. These tasks are known as OR tasks. We analyze the complexity of two types of real-time AND/OR task scheduling problems. In the first type of problem, all predecessors of every OR task must eventually be completed, but in the second type of problem, some OR predecessors may be left unscheduled. We show that most problems involving tasks with individual deadlines are NP-complete, and then present two priority-driven heuristic algorithms to minimize completion time.