this repo has no description
dekker.one
1/***
2!Test
3expected:
4- !Result
5 solution: !Solution
6 Entry:
7 - 62
8 - 4
9 - 18
10 - 47
11 Period: 25
12 Removal:
13 - 0
14 - 14
15 - 43
16 - 57
17 objective: 25
18***/
19
20%------------------------------------------------------------------------------%
21% singHoist2.mzn
22% Peter Stuckey
23% September 30 2006
24%------------------------------------------------------------------------------%
25%------------------------------------------------------------------------------%
26% singHoist2.zinc
27% Jakob Puchinger <jakobp@cs.mu.oz.au>
28% Wed Jun 21
29%------------------------------------------------------------------------------%
30
31%------------------------------------------------------------------------------%
32% Minizinc model of one-hoist scheduling
33%
34% Robert Rodosek and Mark Wallace
35% A Generic Model and Hybrid Algorithm for Hoist Scheduling Problems
36% in Michael J. Maher and Jean-Francois Puget eds.
37% Principles and Practice of Constraint Programming - CP98,
38% Springer, Lecture Notes in Computer Science, volume 1520, 1998.
39
40
41%------------------------------------------------------------------------------%
42% constants
43
44int: NumTanks;
45int: NumJobs;
46array [0..NumTanks, 0..NumTanks] of int: Empty;
47array [0..NumTanks] of int: Full;
48array [1..NumTanks] of int: MinTime;
49array [1..NumTanks] of int: MaxTime;
50
51
52%------------------------------------------------------------------------------%
53% decision variables
54
55int: PerMax = sum([MaxTime[i] | i in 1..NumTanks]);
56
57array [0..NumTanks] of var 0..(NumJobs * PerMax): Entry;
58array [0..NumTanks] of var 0..(NumJobs * PerMax): Removal;
59var 0..PerMax : Period;
60
61%------------------------------------------------------------------------------%
62% model
63
64solve minimize Period;
65
66constraint
67 forall (Tank in 0..NumTanks) (
68 Removal[Tank] + Full[Tank] = Entry[(Tank + 1) mod (NumTanks+1)]
69 );
70
71constraint
72 forall (Tank in 1..NumTanks) (
73 Entry[Tank] + MinTime[Tank] <= Removal[Tank]
74 /\ Entry[Tank] + MaxTime[Tank] >= Removal[Tank]
75 );
76
77constraint
78 Removal[NumTanks] + Full[NumTanks] <= NumJobs * Period;
79
80% disjoint constraint
81constraint
82 forall (T1 in 0..NumTanks-1, T2 in T1+1..NumTanks, K in 1..NumJobs-1) (
83 Entry[(T1 + 1) mod (NumTanks+1)] +
84 Empty[(T1+1) mod (NumTanks+1), T2] + K * Period
85 <= Removal[T2]
86 \/ Entry[(T2 + 1) mod (NumTanks+1)] +
87 Empty[(T2 + 1) mod (NumTanks+1), T1]
88 <= Removal[T1] + K * Period
89 );
90
91constraint
92 Removal[0] = 0;
93
94%------------------------------------------------------------------------------%
95% Test case.
96
97NumTanks = 3;
98NumJobs = 3;
99Empty = array2d(0..NumTanks, 0..NumTanks,
100 [ 0, 2, 3, 3,
101 2, 0, 2, 3,
102 3, 2, 0, 2,
103 3, 3, 2, 0]);
104Full = array1d(0..NumTanks, [4, 4, 4, 5]);
105MinTime = [10, 25, 10];
106MaxTime = [10, 25, 10];
107constraint 0 <= Period /\ Period <= sum([MaxTime[i] | i in 1..NumTanks]);
108
109output [
110 "singHoist2:\n",
111 "Period = ", show(Period), "\n",
112 "Entry[] = [",
113 show(Entry[0]), " ",
114 show(Entry[1]), " ",
115 show(Entry[2]), " ",
116 show(Entry[3]), "]\n",
117 "Removal[] = [",
118 show(Removal[0]), " ",
119 show(Removal[1]), " ",
120 show(Removal[2]), " ",
121 show(Removal[3]), "]\n"
122];