Local constraint based analysis in resource constrained scheduling

Abstract

Resource constrained scheduling problems are generally solved by optimization techniques which cannot accomodate large size problems with respect to computation time. Yet, fast and near optimal schedules are required in actual dynamic environments. A method which has a quick response to dynamic conditions is the usage of dispatching rules which are tested and evaluated in simulation studies or against static optimal solutions. The disadvantage of heuristics lies in their performance dependence on problem characteristics. Constraint based analysis (CBA) approach employed here stands midway between the latter two methods. The performance criterion is imposed on the scheduling process as a constraint together with resource limitations. These constraints are considered as locally essential at each scheduling decision point and activities are sequenced in accordance with the constraints. In this research, the local essential conditions are explained in detail and the static and quasi-dynamic algorithms for resource constrained scheduling in which they are incorporated are conveyed. Static solutions for· the previously solved project scheduling test problems obtained employing local CBA are compared with well-known heuristics as well as with the optimal solutions. Furthermore, CBA results for static job-shop problems representing various shop cha~acteristics are compared with heuristics.