A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes

被引：65

作者：

Artigues, C

Roubellat, F

机构：

[1] Univ Avignon & Pays Vaucluse, Lab Informat Avignon, F-84911 Avignon 9, France

[2] CNRS, Lab Anal & Architecture Syst, F-31077 Toulouse, France

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2000年 / 127卷 / 02期

关键词：

multi-resource scheduling; cumulative constraints; multiple modes; acyclic directed graphs; activity insertion; polynomial time complexity; on-line scheduling; local search;

D O I：

10.1016/S0377-2217(99)00496-8

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, a polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints, general precedence relations and multiple modes is proposed. Insertion objective is to minimize the resulting impact on maximum lateness, while keeping some essential characteristics of the initial schedule. A new disjunctive are-based representation with multiple capacities associated to resource arcs is proposed. Under specific constraints, some simple dominance rules allow to find an optimal insertion position in the digraph with low-computational requirements. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：297 / 316

页数：20