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
- KUTZNER ARNE HOLGER
- 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/NODE01836530https://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