78 0

A Term-based Language for Resource-Constrained Project Scheduling and its Complexity Analysis

Title
A Term-based Language for Resource-Constrained Project Scheduling and its Complexity Analysis
Author
Keywords
Scheduling problem; description logics; complexity theory
Issue Date
2012-03
Publisher
Korean Institute of Intelligent Systems
Citation
Journal of fuzzy Logic and Intelligent Systems, 2012, 12(1), P.20-28
Abstract
We define a language $\mathcal{RS}$, a subclass of the scheduling language $\mathcal{RS}V$ (resource constrained project scheduling with variant processes). $\mathcal{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 $\mathcal{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 $\mathcal{RS}$-scheduling problem, the optimizing variant, the number variant and the decision variant. Using the decision variant we show that the problem $\mathcal{RS}$ is $\mathcal{NP}$-complete. Further we show that the optimizing variant (or number variant) of the $\mathcal{RS}$-problem is computable in polynomial time iff the decision variant is computable in polynomial time.
URI
http://www.dbpia.co.kr/Journal/ArticleDetail/NODE01836530http://repository.hanyang.ac.kr/handle/20.500.11754/69576
ISSN
1598-2645
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