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

Kutzner, Arne,Kim, Pok-Son Korean Institute of Intelligent Systems 2012 INTERNATIONAL JOURNAL of FUZZY LOGIC and INTELLIGE Vol.12 No.1

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.

A Small Scale Registry Concept for Microcontroller Configuration

Arne Kutzner(아네 쿠츠너),Pok-Son Kim(김복선) 한국지능시스템학회 2012 한국지능시스템학회 학술발표 논문집 Vol.22 No.2

We propose a registry concept that is optimized with respect to the special architectural and computational aspects of microcontroller centered systems. Our registry concept is self-contained, allows the realization of hierarchically organized configuration environments and is minimal regarding the consumption of volatile memory. The proposed model allows the distribution of different parts of the registry over different kinds of memory as e.g. EEPROM and Flash. Using an imperative programming language the central registry access algorithm can be transparently implemented as a singular function construct. For import and export purposes our model supports the XML representation of registries. We report about a practical implementation in the context of a microcontroller based system for model railway control.

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

Arne Kutzner,Pok-Son Kim 한국지능시스템학회 2012 INTERNATIONAL JOURNAL of FUZZY LOGIC and INTELLIGE Vol.12 No.1

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.

Stable한 Minimum Storage 병합을 위한 단순알고리즘의 복잡도 분석

쿠츠너 아네(Arne Kutzner),김복선(Pok-Son Kim),김정숙 한국지능시스템학회 2012 한국지능시스템학회 학술발표 논문집 Vol.22 No.1

We contribute to the research on complexity analysis of a stable minimum storage merging algorithm that is particularly simply structured and transparently implemented by few lines of Pseudocode compared to its competitors. The algorithm presented in [4] is based on a structurally simple principle of symmetric splitting, where the start and end point of a rotation are computed by a repeated halving of two search spaces. The algorithm performs ?logn?+1 comparisons in the best case and O(mlog(n/m))comparisons in the worst case, where m and n are the sizes of the input sequences with m≤n. Hence, according to the lower bounds of merging the algorithm is asymptotically optimal regarding the number of comparisons. For proving the worst case complexity we consider several special cases. Based on the complexity of these special cases we prove the worst case complexity of the algorithm.

디지털 모델기차 콘트롤을 위한 실시간 OS에 기반한 Firmware의 디자인 및 구조

아네 쿠츠너(Arne Kutzner),김복선(Pok-Son Kim) 한국지능시스템학회 2011 한국지능시스템학회 학술발표 논문집 Vol.21 No.2

We propose the structure and components of a real-time operating system based solution for digital model-railway control. Digital model railways, where pulse-width modulation (PWM) based data generation is used for locomotive and accessory control, are quite popular within the community of model railway enthusiast. These systems are always to some degree vendor specific and require some central control for performing several parallel tasks as e.g. track signal generation, scheduling of control messages and collection of feedback events. There are already many commercial as well as community maintained solutions for central controls available. However, aside from some community projects, little is known about the inner software of such Microcontroller centered systems. We will report about a FreeRTOS based firmware for the Central Control hardware of the OpenDCC project. The application of a real-time Operating System togetherwith preemptive multitasking poses a non-trivial problem in the context of model railway control, due to the strict timing requirements of many digital model railway protocols. These timing requirements come quickly into conflict with the natural inner delays of real-time Operating Systems. In the context of our work we could successfully solve such conflicts by avoiding specific programming constructs with FreeRTOS.

Livebearing or egg-laying mammals: 27 decisive nucleotides of FAM168

Pramanik, Subrata,Kutzner, Arne,Heese, Klaus International Research and Cooperation Association 2017 Bioscience trends Vol.11 No.2

NP-Completeness of the Logic-Based Scheduling Language RS

Kim, Pok-Son,Kutzner, Arne,Park, Taehoon 국민대학교 2003 기초과학연구소 논문집 Vol.22 No.-

RSV 언어의 부분클래스에 해당하는 언어 RS 를 정의하고, RS 문제해결에 있어서 계산시간과 관련한 복잡도에 대해 연구하는것이 이 논문의 목적이다. RSV에서 세가지 구조적 연산 seq, xor 그리고 pll 이 이용되는 반면 RS에서 단지 두 연산 seq 그리고 pll이 문제 표현을 위한 구조적 연산으로 이용되며, 우리는 이 논문에서 RS-문제가 클래스 NP에 속하며, NP-완전문제에 해당하는 knapsack-문제로 RS-문제를 다항식시간 귀착가능 (polynomial reducible) 함으로 보이므로 RS-문제가 NP-완전함을 증명해 보인다. The language RS, a subclass of the scheduling language RSV (resource constrained project scheduling with variant processes), involves the determining 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 only two structural symbols (operators) `seq’ and ‘p11’, instead of three structural symbols (operators) `seq’, `xor’ and ‘pll’ of RSV, are used to construct activity-terms representing scheduling problems. The purpose of this paper is to investigate which time complexity is needed for solving the problem RS. We show the problem RS belongs to the problem class NP and the well-known NP-complete knapsack problem is polynomial reducible to the problem RS. So the problem RS is NP-complete.

Complexity of the scheduling language

Pok-son Kim,Arne Kutzner,Taehoon Park 한국전산응용수학회 2006 Journal of applied mathematics & informatics Vol.20 No.1-2

Establishing a human adrenocortical carcinoma (ACC)-specific gene mutation signature

Rahane, Chinmay Satish,Kutzner, Arne,Heese, Klaus Elsevier 2019 Cancer genetics Vol.230 No.-

<P><B>Abstract</B></P> <P>Adrenocortical carcinoma (ACC) is a rare and aggressive tumor whose molecular signaling pathways are not fully understood. Using an <I>in-silico</I> clinical data analysis approach we retrieved human gene mutation data from the highly reputed Cancer Genome Atlas (TCGA). ACC-specific gene mutations were correlated with proliferation marker FAM72 expression and Mutsig along with the algorithmic implementation of the 20/20 rule were used to validate their oncogenic potential. The newly identified oncogenic driver gene set (ZFPM1, LRIG1, CRIPAK, ZNF517, GARS and DGKZ), specifically and most repeatedly mutated in ACC, is involved in tumor suppression and cellular proliferation and thus could be useful for the prognosis and development of therapeutic approaches for the treatment of ACC.</P> <P><B>Highlights</B></P> <P> <UL> <LI> LRIG1, ZFPM1, CRIPAK, GARS, ZNF517 and DGKZ are driver genes in ACC. </LI> <LI> ACC-specific gene mutation signature could be useful for therapeutics. </LI> <LI> LRIG1-regulated EGFR signaling could be key to ACC tumorigenesis. </LI> </UL> </P>

Brain plasticity, cognitive functions and neural stem cells: a pivotal role for the brain-specific neural master gene |-SRGAP2-FAM72-|

Ho, Nguyen Thi Thanh,Kutzner, Arne,Heese, Klaus De Gruyter 2018 Biological Chemistry Vol.399 No.1

<P><B>Abstract</B></P><P>Due to an aging society with an increased dementia-induced threat to higher cognitive functions, it has become imperative to understand the molecular and cellular events controlling the memory and learning processes in the brain. Here, we suggest that the novel master gene pair |-SRGAP2-FAM72-| (SLIT-ROBO Rho GTPase activating the protein 2, family with sequence similarity to 72) reveals a new dogma for the regulation of neural stem cell (NSC) gene expression and is a distinctive player in the control of human brain plasticity. Insight into the specific regulation of the brain-specific neural master gene |-SRGAP2-FAM72-| may essentially contribute to novel therapeutic approaches to restore or improve higher cognitive functions.</P>