Single-machine scheduling with mixed precedence constraints

被引：0

作者：

Levner, E

Vlach, M

机构：

[1] Ctr Technol Educ Holon, Holon, Israel

[2] Japan Adv Inst Sci & Technol, Sch Informat Sci, Tatsunokuchi, Ishikawa 9231292, Japan

来源：

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN | 1999年 / 42卷 / 03期

基金：

日本学术振兴会;

关键词：

D O I：

10.15807/jorsj.42.330

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The paper deals with a single machine scheduling problem involving a general precedence structure that permits both ordinary and fuzzy precedence constraints. Feasible schedules are evaluated not only by their cost but also by the degree of satisfaction with their precedence structure. An O(m log n + max(n(2), kn(2)))-time algorithm is proposed for finding nondominated solutions of the resulting bi-criteria. scheduling problem where n is the number of jobs, k is the number of fuzzy constraints, and m is the total number of precedence constraints.

引用

页码：330 / 341

页数：12

共 15 条

[1]

Cormen T. H., 1990, INTRO ALGORITHMS

[2]

Gaspin C., 1989, Telematics and Informatics, V6, P159, DOI 10.1016/S0736-5853(89)80013-9

[3] MAXIMIZING THE VALUE OF A SPACE MISSION [J].