[Oz] Scheduling: MT10 Without Compiler
Benjamin Inden
benjamin.inden at FernUni-Hagen.de
Wed Feb 7 22:28:23 CET 2001
Hi,
For a seminary on constraint programming, I am working on a script for solving
the MT10 problem. I need a simple script, so I want a straightforward solution
without a compiler (like in the tutorial). Unfortunately, the script is too slow.
On a Pentium III-600 / 64 MB RAM with Linux, it takes about 99.8% of CPU time
(according to the "top" command), but after 6 hours, it has computed only about
400 choice nodes. All solved nodes are suspended (light green). With Windows 98 SE,
it seems to be still slower.
Is there a mistake in the script, or is there a way to speed it up?
----------------------------
local MT10Solve Earlier in
proc {MT10Solve Start}
Dur = dur(pa:0 a1:29 a2:78 a3:9 a4:36 a5:49 a6:11 a7:62 a8:56 a9:44 a10:21
b1:43 b2:90 b3:75 b4:11 b5:69 b6:28 b7:46 b8:46 b9:72 b10:30
c1:91 c2:85 c3:39 c4:74 c5:90 c6:10 c7:12 c8:89 c9:45 c10:33
d1:81 d2:95 d3:71 d4:99 d5:9 d6:52 d7:85 d8:98 d9:22 d10:43
e1:14 e2:6 e3:22 e4:61 e5:26 e6:69 e7:21 e8:49 e9:72 e10:53
f1:84 f2:2 f3:52 f4:95 f5:48 f6:72 f7:47 f8:65 f9:6 f10:25
g1:46 g2:37 g3:61 g4:13 g5:32 g6:21 g7:32 g8:89 g9:30 g10:55
h1:31 h2:86 h3:46 h4:74 h5:32 h6:88 h7:19 h8:48 h9:36 h10:79
i1:76 i2:69 i3:76 i4:51 i5:85 i6:11 i7:40 i8:89 i9:26 i10:74
j1:85 j2:13 j3:61 j4:7 j5:64 j6:76 j7:47 j8:52 j9:90 j10:45 pe:0)
Start = {FD.record start [pa a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 c1 c2 c3 c4 c5 c6 c7 c8 c9 c10
d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10
f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 g1 g2 g3 g4 g5 g6 g7 g8 g9 g10
h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10
j1 j2 j3 j4 j5 j6 j7 j8 j9 j10 pe] 0#FD.sup}
Tasks = tasks(m1:[a1 b1 c2 d3 e2 f7 g2 h2 i1 j2]
m2:[a2 b6 c1 d1 e3 f2 g1 h3 i2 j1]
m3:[a3 b2 c4 d2 e1 f1 g4 h1 i5 j3]
m4:[a4 b5 c3 d8 e5 f4 g3 h10 i3 j8]
m5:[a5 b3 c10 d4 e6 f9 g10 h5 i9 j9]
m6:[a6 b8 c6 d10 e4 f3 g6 h4 i4 j7]
m7:[a7 b7 c8 d5 e10 f8 g5 h6 i7 j4]
m8:[a8 b9 c7 d7 e8 f10 g9 h9 i8 j10]
m9:[a9 b10 c5 d6 e7 f5 g8 h7 i10 j5]
m10:[a10 b4 c9 d9 e9 f6 g7 h8 i6 j6])
in
Start.pa = 0
%% precedence constraints
Start.pa + Dur.pa =<: Start.a1
Start.a1 + Dur.a1 =<: Start.a2
Start.a2 + Dur.a2 =<: Start.a3
Start.a3 + Dur.a3 =<: Start.a4
Start.a4 + Dur.a4 =<: Start.a5
Start.a5 + Dur.a5 =<: Start.a6
Start.a6 + Dur.a6 =<: Start.a7
Start.a7 + Dur.a7 =<: Start.a8
Start.a8 + Dur.a8 =<: Start.a9
Start.a9 + Dur.a9 =<: Start.a10
Start.pa + Dur.pa =<: Start.b1
Start.b1 + Dur.b1 =<: Start.b2
Start.b2 + Dur.b2 =<: Start.b3
Start.b3 + Dur.b3 =<: Start.b4
Start.b4 + Dur.b4 =<: Start.b5
Start.b5 + Dur.b5 =<: Start.b6
Start.b6 + Dur.b6 =<: Start.b7
Start.b7 + Dur.b7 =<: Start.b8
Start.b8 + Dur.b8 =<: Start.b9
Start.b9 + Dur.b9 =<: Start.b10
Start.pa + Dur.pa =<: Start.c1
Start.c1 + Dur.c1 =<: Start.c2
Start.c2 + Dur.c2 =<: Start.c3
Start.c3 + Dur.c3 =<: Start.c4
Start.c4 + Dur.c4 =<: Start.c5
Start.c5 + Dur.c5 =<: Start.c6
Start.c6 + Dur.c6 =<: Start.c7
Start.c7 + Dur.c7 =<: Start.c8
Start.c8 + Dur.c8 =<: Start.c9
Start.c9 + Dur.c9 =<: Start.c10
Start.pa + Dur.pa =<: Start.d1
Start.d1 + Dur.d1 =<: Start.d2
Start.d2 + Dur.d2 =<: Start.d3
Start.d3 + Dur.d3 =<: Start.d4
Start.d4 + Dur.d4 =<: Start.d5
Start.d5 + Dur.d5 =<: Start.d6
Start.d6 + Dur.d6 =<: Start.d7
Start.d7 + Dur.d7 =<: Start.d8
Start.d8 + Dur.d8 =<: Start.d9
Start.d9 + Dur.d9 =<: Start.d10
Start.pa + Dur.pa =<: Start.e1
Start.e1 + Dur.e1 =<: Start.e2
Start.e2 + Dur.e2 =<: Start.e3
Start.e3 + Dur.e3 =<: Start.e4
Start.e4 + Dur.e4 =<: Start.e5
Start.e5 + Dur.e5 =<: Start.e6
Start.e6 + Dur.e6 =<: Start.e7
Start.e7 + Dur.e7 =<: Start.e8
Start.e8 + Dur.e8 =<: Start.e9
Start.e9 + Dur.e9 =<: Start.e10
Start.pa + Dur.pa =<: Start.f1
Start.f1 + Dur.f1 =<: Start.f2
Start.f2 + Dur.f2 =<: Start.f3
Start.f3 + Dur.f3 =<: Start.f4
Start.f4 + Dur.f4 =<: Start.f5
Start.f5 + Dur.f5 =<: Start.f6
Start.f6 + Dur.f6 =<: Start.f7
Start.f7 + Dur.f7 =<: Start.f8
Start.f8 + Dur.f8 =<: Start.f9
Start.f9 + Dur.f9 =<: Start.f10
Start.pa + Dur.pa =<: Start.g1
Start.g1 + Dur.g1 =<: Start.g2
Start.g2 + Dur.g2 =<: Start.g3
Start.g3 + Dur.g3 =<: Start.g4
Start.g4 + Dur.g4 =<: Start.g5
Start.g5 + Dur.g5 =<: Start.g6
Start.g6 + Dur.g6 =<: Start.g7
Start.g7 + Dur.g7 =<: Start.g8
Start.g8 + Dur.g8 =<: Start.g9
Start.g9 + Dur.g9 =<: Start.g10
Start.pa + Dur.pa =<: Start.h1
Start.h1 + Dur.h1 =<: Start.h2
Start.h2 + Dur.h2 =<: Start.h3
Start.h3 + Dur.h3 =<: Start.h4
Start.h4 + Dur.h4 =<: Start.h5
Start.h5 + Dur.h5 =<: Start.h6
Start.h6 + Dur.h6 =<: Start.h7
Start.h7 + Dur.h7 =<: Start.h8
Start.h8 + Dur.h8 =<: Start.h9
Start.h9 + Dur.h9 =<: Start.h10
Start.pa + Dur.pa =<: Start.i1
Start.i1 + Dur.i1 =<: Start.i2
Start.i2 + Dur.i2 =<: Start.i3
Start.i3 + Dur.i3 =<: Start.i4
Start.i4 + Dur.i4 =<: Start.i5
Start.i5 + Dur.i5 =<: Start.i6
Start.i6 + Dur.i6 =<: Start.i7
Start.i7 + Dur.i7 =<: Start.i8
Start.i8 + Dur.i8 =<: Start.i9
Start.i9 + Dur.i9 =<: Start.i10
Start.pa + Dur.pa =<: Start.j1
Start.j1 + Dur.j1 =<: Start.j2
Start.j2 + Dur.j2 =<: Start.j3
Start.j3 + Dur.j3 =<: Start.j4
Start.j4 + Dur.j4 =<: Start.j5
Start.j5 + Dur.j5 =<: Start.j6
Start.j6 + Dur.j6 =<: Start.j7
Start.j7 + Dur.j7 =<: Start.j8
Start.j8 + Dur.j8 =<: Start.j9
Start.j9 + Dur.j9 =<: Start.j10
Start.a10 + Dur.a10 =<: Start.pe
Start.b10 + Dur.b10 =<: Start.pe
Start.c10 + Dur.c10 =<: Start.pe
Start.d10 + Dur.d10 =<: Start.pe
Start.e10 + Dur.e10 =<: Start.pe
Start.f10 + Dur.f10 =<: Start.pe
Start.g10 + Dur.g10 =<: Start.pe
Start.h10 + Dur.h10 =<: Start.pe
Start.i10 + Dur.i10 =<: Start.pe
Start.j10 + Dur.j10 =<: Start.pe
%% capacity constraints
{Schedule.serialized Tasks Start Dur}
%% labelling
{Schedule.firstsLastsDist Tasks Start Dur}
end
proc {Earlier Old New}
Old.pe >: New.pe
end
{ExploreBest MT10Solve Earlier}
end
-----------------------------
Thanks in advance for any hints,
Benjamin Inden
benjamin.inden at fernuni-hagen.de
-
Please send submissions to users at mozart-oz.org
and administriva mail to users-request at mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.
More information about the mozart-users
mailing list