2003 · 49 citations · 10 references
ManagementIndustrial EngineeringCapacity PlanningOptimizationSchedulingResource-constrained SchedulingSchedule OptimizationScheduling OptimizationAirlift OperationsFlexibilityScheduling ConstraintsScheduling HeuristicsSolution Generation
In this paper we consider the solution of scheduling problems that are inherently over-subscribed. In such problems, there are always more tasks to execute within a given time frame than available resource capacity will allow, and hence decisions must be made about which tasks should be included in the schedule and which should be excluded. We adopt a controlled, iterative repair search approach, and focus on improving the results of an initial priority-driven solution generation procedure. Central to our approach is a new retraction heuristic, termed max-flexibility, which is responsible for identifying which tasks to (temporarily) retract from the schedule for reassignment in an effort to incorporate additional tasks into the schedule. The max-flexibility heuristic chooses those tasks that have maximum flexibility for assignment within their feasible windows. We empirically evaluate the performance of max-flexibility using problem data and the basic scheduling procedure from a fielded airlift mission scheduling application. We show that it produces better improvement results than two contention-based retraction heuristics, including a variant of min-conflicts[Minton et al., 1992], with significantly less search and computational cost. temporarily applicability of 1
10
Upendra Dave · Journal of the Operational Research Society · 1995 · 487 citations
Management, Industrial Engineering, Operations Management +12
Scheduling and rescheduling with iterative repair
Monte Zweben, Eugene Davis, Brian Daun et al. · IEEE Transactions on Systems Man and Cybernetics · 1993 · 273 citations · Full text
Solution Reuse in Dynamic Constraint Satisfaction Problems
Thomas Schiex · 1994 · 178 citations