Project scheduling is used in many fields, such as construction, drug development, and scheduling. Such project scheduling has aperiodic characteristics. The aperiodic project scheduling problem is divided into the scheduling problem of determining the sequence of activities with resource constraints and time constraints or when to execute which activity in the already determined sequence. In particular, many studies have been conducted to determine the start time of activities and the end time of projects in a set sequence in the field of construction, production of large ships or aircraft, and military operation planning. The schedule calculation of this project scheduling problem is easily derived through the Forward & Backward algorithm. This is equally applicable to the problem of the existence of time window constraints. In this study, we prove that the Forward & Backward algorithm can be applied to the problem of time window constraints. In addition, it has been identified and proved that a case of discontinuous slack time may occur when applying the existing Forward & Backward algorithm in project scheduling with time window constraints. To solve this problem, the unique schedule is calculated based only on the target time window. Through this, we present a Scheduling Analysis Method that always derives a feasible schedule by analyzing changes in the schedule of the entire project and changes in activities that require focused management. In addition, through network reconstruction, the setting and effectiveness of the Adaptive Feedback Path that can prevent time window violation even in applying the Earliest Starting Rule, the most intuitive method widely used in the actual field, were mathematically identified and verified through experiments. Finally, research on resource leveling is conducted to minimize the use of renewable resources throughout the project. The resource leveling problem is NP-hard, and the computation time increases exponentially as the size gets larger. In this case, the Modular algorithm for leveling by selecting the most ideal subset through the Scheduling Analysis Method is proposed and utilized. As a result, the performance of any leveling-solving method can be improved. Through this, we derive a schedulable schedule even when the earliest starting rule is not always applied advantageously in the field of production planning, and external or managerial aspects must arbitrarily change the start and end time. In addition, it was possible to derive a schedule that does not violate various and complexly applied time window constraints and to derive an activity to be managed intensively.
프로젝트 스케줄링은 건설 계획, 의약품 개발 계획, 일정 계획 등 많은 분야에서 활용되고 있다. 이러한 프로젝트 스케줄링은 비주기적인 특징을 가지고 있다. 비주기적인 프로젝트 스케줄링 문제는 자원제약, 시간제약을 가지는 activity들의 sequence를 결정하거나, 이미 결정된 sequence 상에서 언제 어떤 activity를 실행해야 하는가에 대한 scheduling의 문제로 구분이 된다. 특히, 건설 계획, 대형 선박이나 비행체의 생산 계획, 군의 작전계획 분야에 있어서 정해진 sequence에서 activity들의 시작 시점과 프로젝트의 종료 시간을 판단하기 위한 많은 연구가 선행되어져 있다. 이러한 프로젝트 스케줄링 문제의 스케줄 산출은 Forward & Backward 알고리즘을 통해서 쉽게 계산된다. 이는 Time window 시간 제약의 문제에서도 동일하게 적용이 가능하다. 본 연구에서는 Time window constraints의 제약 문제에서 Forward & Backward 알고리즘의 적용이 가능함을 증명한다. 또한 Time window 제약의 프로젝트 스케줄링에서 기존의 Forward & Backward 알고리즘을 적용할때 발생할 수 있는 비연속적인 Slack time의 발생하는 경우가 존재함을 규명하고 정리하였다. 이러한 문제점을 해결하기 위해 목표 Time window만을 중심으로한 고유의 스케줄을 산출하고, 이를 통해 발생하는 전체 프로젝트의 스케줄의 변화와 중점 관리가 필요한 activity의 변화를 분석하여 항상 feasible한 schedule을 도출하는 ‘Scheduling Analysis’ method를 제시한다. 또한 network의 reconstruction을 통해 실제 현장에서 널리 활용되고 있는 가장 직관적인 방법인 Earliest Starting rule 적용에도 Time window violation을 방지할 수 있는 Adaptive Feedback Path의 설정과 효용성에 대해 수리적으로 규명하고 실험을 통해 입증하였다. 마지막으로 프로젝트 전체의 renewable resource의 활용량을 최소화 하기 위한 Resource leveling에 대한 연구를 진행한다. Resource leveling problem은 NP-hard 문제로 size의 변화에 따라 계산 시간이 exponential 하게 증가한다. 이때에, ‘Scheduling Analysis’ method를 통해 가장 이상적인 subset을 선택하여 leveling하는 Modular algorithm을 제시하고 활용한다. 이로써 leveling solving methods의 performance를 향상시키는 연구를 진행하였다. 이를 통해 생산계획 분야에서 항상 Earliest starting rule이 유리하게 적용되지 않는 상황과, 시작과 종료시점이 외부 영향 혹은 관리적 측면에 의해서 임의적으로 변동되어야 하는 상황에도 항상 schedulable한 스케줄의 도출이 가능해 졌다. 또한 다양하고 복잡하게 적용된 Time window 제약들을 violation하지 않는 스케줄 도출과 그에 따른 집중 관리 대상 activity를 도출할 수 있게 되었다.
