Generating Feasible Schedules under Complex Metric Constraints

Abstract

In this paper, we consider the problem of finding feasible solutions to scheduling problems that are complicated by separation constraints on the execution of different operations. Following recent work in constraint-posting scheduling, we formulate this problem as one of establishing ordering relations between pairs of operations requiring synchronization of resource usage. This establishes contact with the recently proposed General Temporal Constraint Network (GTCN) model. Exploiting properties of the general GTCN solution procedure, we are able to directly generalize a high performance solution procedure previously developed for a much more restricted class of scheduling problems. Specifically, shortest path information in the underlying temporal constraint network is first used to establish dominance conditions for early pruning of infeasible solutions. Heuristics are then defined for variable/value ordering in the meta-CSP space of possible resolutions of the disjunctive constraints on resource usage. Th ese heuristics are based on use of shortest path information as an estimation of decision flexibility. Experimental evaluation of the resulting heuristic procedure is carried out on a set of randomly generated problems drawn from a manufacturing scenario. Results indicate extremely effective problem solving performance in relation to both the original scheduling procedure that was adapted and the general GTCN solution procedure.