Single-Machine Scheduling Polyhedra with Precedence Constraints
Single-Machine Scheduling Polyhedra with Precedence Constraints
复制标题
具有优先级约束的单机调度多面体
DOI：
10.1287/moor.16.1.1
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Yaoguang Wang
中科院分区：
文献类型：
--
作者：
M. Queyranne;Yaoguang Wang
本文研究具有优先约束的非抢占式单机排序问题。我们定义的向量的工作完成时间的可行的时间表和研究的凸船体的所有可行的时间表，称为调度多面体P的结构。我们推导出类有效的不等式P，必要和充分条件下，他们是小面诱导。我们的主要结果是一个完整的描述的最小线性系统定义P时的优先约束是串并联。此外，该系统包括两类方面诱导的不等式，分别与串联和并联组成。如果优先约束不是串并联的，我们提出了另一类与诱导Z-子图有关的P的诱导刻面不等式。我们还表明，凸船体的所有抢占可行的时间表是相同的P当且仅当优先约束形成一个出森林。
We consider nonpreemptive single-machine scheduling subject to precedence constraints. We define feasible schedules by the vector of the job completion times and study the structure of the convex hull of all feasible schedules, called the scheduling polyhedron P. We derive classes of valid inequalities for P, and necessary and sufficient conditions under which they are facet-inducing. Our main result is a complete description of the minimal linear system defining P when the precedence constraints are series-parallel. Moreover, this system consists of two classes of facet-inducing inequalities, associated with series and parallel compositions, respectively. If the precedence constraints are not series-parallel, we present another class of facet-inducing inequalities for P, associated with induced Z-subgraphs. We also show that the convex hull of all preemptive feasible schedules is identical to P if and only if the precedence constraints form an out-forest.