77 0

The Terminological Scheduling Language RS and its Complexity

Title
The Terminological Scheduling Language RS and its Complexity
Author
KUTZNER ARNE HOLGER
Keywords
Scheduling problem; description logics; complexity theory
Issue Date
2011-09
Publisher
한국지능시스템학회 / Korean Institute of Intelligent Systems
Citation
INTERNATIONAL JOURNAL of FUZZY LOGIC and INTELLIGENT SYSTEMS, Vol.12, No.1, p20-28
Abstract
We define a language RS, a subclass of the scheduling language RSV (resource constrained project scheduling with variant processes). RS involves the determination of the starting times for ground activities of a project satisfying precedence and resource constraints, in order to minimize the total project duration. In RS ground activities and two structural symbols (operators) ‘seq’ and ‘pll’ are used to construct activity-terms representing scheduling problems. We consider three different variants for formalizing the RS-scheduling problem, the optimizing variant, the number variant and the decision variant. Using the decision variant we show that the problem RS is NP-complete. Further we show that the optimizing variant (or number variant) of theRS-problem is computable in polynomial time iff the decision variant is computable in polynomial time.
URI
http://www.dbpia.co.kr/Journal/ArticleDetail/NODE01836530http://hdl.handle.net/20.500.11754/41285
ISSN
1598-2645
DOI
10.5391/IJFIS.2012.12.1.20 p
Appears in Collections:
COLLEGE OF ENGINEERING[S](공과대학) > INFORMATION SYSTEMS(정보시스템학과) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE