Finite Capacity SchedulingOverview of PresentationSolution AlgorithmsConstructive Constraint-BasedConstructive (con.)Operation/Task AttributesResource Requirement/Resource AttributesConstraintsSlide 9Slide 10Algorithm PseudocodeSimple Example with 4 OrdersTask InstantiationSchedule Order 1Schedule Order 2Schedule Order 3Order 4 infeasibleOrder 4 before 3 also infeasibleSuccess after two backtracksFinal ScheduleProblem with constructive approachConstructive Constraint-Based (con.)Iterative RepairIterative Repair Example – Beer SchedulingSlide 25Beer Scheduling- Operation/Task AttributesSlide 27Time ConstraintsResource Utilization/Capacity ConstraintsResource State ConstraintsCostScheduling DecisionsIterative Repair AlgorithmSlide 34Slide 35Slide 36Iterative Repair (con.)SummaryFinite Capacity Scheduling6.834J, 16.412JOverview of Presentation•What is Finite Capacity Scheduling?•Types of Scheduling Problems•Background and History of Work•Representation of Schedules•Representation of Scheduling Problems•Solution Algorithms•SummarySolution Algorithms•Dispatch Algorithms•MILP–Relation to A*, constructive constraint-based•Constructive Constraint-Based•Iterative Repair–Simulated Annealing–How A* heuristics can be used here (relaxation of deadline constraints)•Genetic AlgorithmsConstructive Constraint-Based-Fox, et. al., ISIS-Best-first search with backtracking-Tasks for orders scheduled one at a time-Incrementally adds to partial schedule at each node in the search-If infeasibility is reached (constraint violation)-Backtrack to resolve constraint-Advantages-Relatively simple, can make use of standard algorithms like A*-Use of A* allows for incorporation of heuristics -Such heuristics are often used by human schedulersConstructive (con.)-Discrete manufacturing example-Automobile assembly-Process plan:AssembleCarUn-assembledCarDoorsAssembledCarAssembleDoorsDoorFramesDoorWindowsDoorMachineChangeoverDoorMachineLabor resources assumedbut not modeled explicitlyhereOperation/Task Attributes-Assemble Doors-Continuous: start_time, finish_time, duration-Discrete: power_windows?-Assemble Car-Continuous: start_time, finish_time, duration-Discrete: deluxe?-Changeover-Continuous: start_time, finish_time, duration-Discrete: start_state, finish_stateResource Requirement/Resource Attributes-Door Machine-Utilization – discrete function of time-Can be 0 or 1, depending on time in scheduling horizon-Power_windows? – discrete function of time-Can be yes or no, depending on time in scheduling horizon-Discrete functions of time represented as collection of discrete events, rather than vector with fixed time intervals-Continuous time rather than discrete time representation-Event is double of value and time-Ex. 0, 5:00-Ex. Collection-((0 0:00) (1 2:00) (0 6:00) (1 12:00))-Collection supports queries of form get_value(time)Constraints-Time-AssembleDoors.finish_time = AssembleDoors.start_time + AssembleDoors.duration-AssembleDoors.duration = 0.5-Changeover.finish_time = Changeover.start_time + Changeover.duration-AssembleCar.finish_time = AssembleCar.start_time + AssembleCar.duration-AssembleCar.duration = 0.5-Changeover.start_time >= AssembleDoors.finish_time-AssembleCar.start_time >= AssembleDoors.finish_timeConstraints-Resource Utilization and Capacity- For all t such that AssembleDoors.start_time <= t <= AssembleDoors.finish_timeDoorMachine.utilization = 1-For all t such that Changeover.start_time <= t <= Changeover.finish_timeDoorMachine.utilization = 1(represented by events (1 start_time) (0 finish_time) in utilization collection)- DoorMachine.utilization <= 1(Automatically enforced by utilization collection mechanism, two start events not allowed without intervening finish event)Constraints-Resource State-For all t such that AssembleDoors.start_time <= t <= AssembleDoors.finish_timeDoorMachine.power_windows? = AssembleDoors.power_windows?(represented by events (pw? start_time) (pw? finish_time) in power_windows? collection)-For all t such that Changeover.start_time <= t < Changeover.finish_timeDoorMachine.power_windows? = Changeover.start_state-At t = Changeover.finish_timeDoorMachine .power_windows? = Changeover.finish_state-Represented by events (start_state start_time) (finish_state finish_time)-If Changeover.start_state != Changeover.finish_stateChangeover.duration = 0.5elseChangeover.duration = 0Algorithm Pseudocode-Instantiate tasks based on process plan and orders-One queue of tasks for each order-Loop-Pick order not yet scheduled-Loop-Pop task from queue for order-Assign task to resource-Propagate constraints-If feasible, continue-If not feasible, backtrackSimple Example with 4 Orders Order Type Due Time1 Standard 3.02 Deluxe 3.03 Standard 3.04 Deluxe 3.0Task Instantiation AssembleDoors1Order 1 QueueChangeover1AssembleCar1Order 2 QueueOrder 3 QueueAssembleDoors2Changeover2AssembleCar2Order 4 QueueAssembleDoors3Changeover3AssembleCar3AssembleDoors4Changeover4AssembleCar4Schedule Order 1 Assign tasks and propagate constraintsDoorMachineTimeAssembleCar1 2 3AssembleDoors1AssembleCar1Schedule Order 2 Assign tasks and propagate constraintsDoorMachineAssembleCar12AssembleDoors1AssembleCar1Changeover1AssembleDoors23AssembleCar2Schedule Order 3 DoorMachineTimeAssembleCar12AssembleDoors1AssembleCar1Changeover1AssembleDoors23AssembleCar2Changeover1AssembleDoors3AssembleCar3Order 4 infeasible-Order deadline is violated-Need to backtrackRO1O2O3O4 InfeasibleRO1O2O3O4O4O3?Order 4 before 3 also infeasibleDoorMachineTimeAssembleCar12AssembleDoors1AssembleCar1Changeover1AssembleDoors23AssembleCar2AssembleDoors4AssembleCar4Changeover4AssembleDoors3AssembleCar3Success after two backtracks-Almost achieves schedule 2 times, then succeeds on third try-Requires search of 3 entire branches of treeRO1O2O3O4O4O3O3O2O4Success!Final ScheduleDoorMachineTimeAssembleCar12AssembleDoors1AssembleCar1AssembleDoors23AssembleCar2AssembleDoors4AssembleCar4Changeover3AssembleDoors3AssembleCar3Problem with constructive approach-Search tree size: (R x O)!-R is number of resources, O is number of orders-Exponential, np complete-As shown in previous example, problems typically not encountered until last few orders are scheduled-As a result, typically searches entire branch of tree before finding out it is infeasible-Swapping to eliminate changeover requires backtracking-Results in significant amount of backtracking-Does not work for large, difficult scheduling problems-Even when heuristics
View Full Document
Unlocking...