Scheduling Window of feasible values 0020503070 100402060 X1in[10,20] 2-40-300-1030 X2in[40,50] 3-20-1020050 °X3in[20,30 4-60-50-20-400 X4in[60,70 d-graph Scheduling without Search: Solution by Decomposition Can assign variables in any order, without backtracking Select value for 1 503070 [0,20] 1A00402060 2-40-300-1030 3-20-1020050 4-60-50-20-400 d-graph
Scheduling: Window of Feasible Values 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph • X1 in [10, 20] • X2 in [40, 50] • X3 in [20, 30] • X4 in [60, 70] Latest Times Earliest Times Scheduling without Search: Solution by Decomposition 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph • Select value for 1 Æ 15 [10,20] • Can assign variables in any order, without backtracking
Solution by decomposition Can assign variables in any order, without backtracking 0 23 Select value for 1 503070 5[10,20] 10/0402060 2-40-300-1030 3-20-1020050 4-60-50-20-400 d-graph Solution by Decomposition Can assign variables in any order, without backtracking Tighten bound of Y using all selected X: YEX+ XY Select value for 1 0020503070 Select value for 2 00402060 consistent with 1 2|-40-300-1030 40,50],15+[ 3-20-1020050 4-60-50-20-400 d-graph
0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph • Select value for 1 Æ 15 [10,20] Solution by Decomposition • Can assign variables in any order, without backtracking. Solution by Decomposition 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph • Select value for 2, consistent with 1 Æ 45 [40,50], 15+[30,40] • Select value for 1 Æ 15 • Can assign variables in any order, without backtracking. • Tighten bound of Y using all selected X: Y X + |XY|
Solution by decomposition Can assign variables in any order, without backtracking Tighten bound of Y using all selected X: YEX+XY 01234 Select value for 1 0020503070 →15 · Select value for2 00402060 consistent with 1 240-300-1030 45,50] 3-20-1020050 4-60-50-20-400 d-graph Solution by Decomposition Can assign variables in any order, without backtracking Tighten bound of Y using all selected X: YEX+ XY 234 Select value for 1 0020503070 Select value for 2 00402060 consistent with 1 2|-40-300-1030 45[45,50 3-20-1020050 4-60-50-20-400 d-graph
Solution by Decomposition 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph • Select value for 2, consistent with 1 Æ 45 [45,50] • Select value for 1 Æ 15 • Can assign variables in any order, without backtracking. • Tighten bound of Y using all selected X: Y X + |XY| Solution by Decomposition 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph • Select value for 2, consistent with 1 Æ 45 [45,50] • Select value for 1 Æ 15 • Can assign variables in any order, without backtracking. • Tighten bound of Y using all selected X: Y X + |XY|
Solution by decomposition Can assign variables in any order, without backtracking Tighten bound of Y using all selected X: YEX+XY 01234 Select value for 1 0020503070 →15 Select value for 2 00402060 consistent with 1 240-300-1030 3 -20-10 200 50 Select value for 3 4-60-50-20-400 consistent with 1 2 d-graph Solution by Decomposition Can assign variables in any order, without backtracking Tighten bound of Y using all selected X: YEX+ XY 234 Select value for 1 00205030|70 Select value for 2 100402060 consistent with 1 2-40-300-1030 45 20 1020050 consistent with 1 2 4-60-50-20-40 25,30 d-graph
Solution by Decomposition 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph • Select value for 2, consistent with 1 Æ 45 • Select value for 1 Æ 15 • Select value for 3, consistent with 1 & 2 Æ 30 [20,30], 15+[10,20],45+[-20,-10] • Can assign variables in any order, without backtracking. • Tighten bound of Y using all selected X: Y X + |XY| Solution by Decomposition 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph • Select value for 2, consistent with 1 Æ 45 • Select value for 1 Æ 15 • Select value for 3, consistent with 1 & 2 Æ 30 [25,30] • Can assign variables in any order, without backtracking. • Tighten bound of Y using all selected X: Y X + |XY|