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