The job shop scheduling problem has a wide range of applications in industry. The problem we will explore is a simple job shop scheduling for a print shop. The print shop has 6 machines: [printer, stapler, sorter, binder, packager, copier], and schedules a number of jobs over a two day (48 hour) period. Each job is a sequence of tasks which have a name, duration (in hours) and machine that they must be performed on. A schedule assigns a start time for each task, so that no task starts before the previous task in the job has finished, and no machine is busy with two tasks at the same time. The main user defined predicate defined to solve the scheduling problem is data(TaskList, Jobs, Machines, Vars) where
- TaskList is a list of tasks. Each task is represented as a term task(Name, Duration, Machine, StartTime) where Name, Duration, StartTime are the name, start time, and duration of the task, Machine is the machine the task needs.
- Jobs is a list of jobs which in turn by definition is a list of tasks. Each job in this list consists of the tasks that make up this job in the order that they should be completed,
- Machines is the list of all machines in the shop, and
- Vars is the list of all start time variables (of the tasks).
As an example, data/4 below describes a pair of small advertising print jobs.
data( %%% First argument is a list of tasks with name, duration %%% and machine and start time (unconstrained) [ task(ad1_copy, 4, copier, AC1), task(ad1_sort, 4, sorter, AS1), task(ad1_pack, 3, packager, AD1), task(ad2_copy, 5, copier, AC2), task(ad2_sort, 4, sorter, AS2), task(ad2_pack, 4, packager, AD2) ], %%% second argument is a list of lists of task names to be %%% performed in order [[ad1_copy,ad1_sort,ad1_pack], [ad2_copy,ad2_sort,ad2_pack] ], %%% third argument is the list of different machines [copier,sorter,packager], %%% fourth argument is the list of all start time variables [AC1,AS1,AD1,AC2,AS2,AD2] ).
The file ’job.pl’ above, containing the data/4, should be saved under the same directory as your program. When your program is tested, it should be able to handle more jobs and each job may have more tasks. This program uses the template schedule-template.pl, below.
%% This is a program stub for the job shop scheduling problem %% given in the project. % Load in finite domain module :- use_module(library(clpfd)). % Other modules you may use are loaded here % You must use the following to load in the data :-['job.pl']. % Your definition of the userdefined constraint jobshop(L) should be here. member(X,[X|_]). member(X,[_|T]):- member(X,T). jobshop(L) :- data(W,X,_,Z), init(W), precLL(X,W), capacity(W), labeling([],Z), L = Z. init([]). init(TASKLIST):- TASKLIST=[task(_,D,_,ST)|T], ST in 0..48, ST+D #=< 48, init(T). precLL([], _). precLL(JOBS,TASKLIST) :- JOBS = [H|T], precL(H, [2], TASKLIST), precLL(T,TASKLIST). precL(_, [], _). precL([], _, _). precL(JOBS, _, TASKLIST) :- JOBS=[H|T], T=[HH|TT], member(task(H,D1,_,T1), TASKLIST), member(task(HH,_,_,T2), TASKLIST), T1 + D1 #< T2, %write(H), write('-'), write(HH),write('\n'), precL(T, TT,TASKLIST). exlude(T1, D1, T2, _) :- T1 + D1 #< T2. exlude(T1, _, T2, D2) :- T2 + D2 #< T1. capacity([]). capacity(TASKLIST) :- TASKLIST = [task(J,D,M,_)|T], %write(J), write('-'), write(D), write('-'), write(M), write('-'), write(ST), write('\n'), nonoverlaps(J,D,M,T,TASKLIST), capacity(T). nonoverlaps(_,_,_,[],_). nonoverlaps(J,D,M,L,TASKLIST) :- L = [task(_, _, M2, _) | T], M \= M2, nonoverlaps(J,D,M,T,TASKLIST). nonoverlaps(J,D,M,L,TASKLIST) :- L=[task(_,D2,M2,T2)|T], M = M2, member(task(J,D,M,T1),TASKLIST), exlude(T1,D,T2,D2), nonoverlaps(J,D,M,T,TASKLIST). % Your rules should not go below this line % Don't delete or comment away the following %% Output the solution myoutput :- jobshop(L), write('The starting time of the tasks are: \n'), myprint(L, 1). %% this is to output the sarting time myprint([], _). myprint([X|L], I) :- write('task '), write(I), write(' starts at '), write(X), write('\n'), Y #= I+1, myprint(L, Y). %% initiat the output. :- myoutput.
Sample query and output under Sicstus Prolog
banana$ sicstus SICStus 3.11.2 (sparc-solaris-5.7): Wed Jun 2 11:43:16 MET DST 2004 Licensed to ttu.edu | ?- ['schedule-template.pl']. % consulting /home/undergrad3/ebaldelo/schedule-template.pl... % loading /usr/local/lib/sicstus-3.11.2/library/clpfd.po... % module clpfd imported into user % loading /usr/local/lib/sicstus-3.11.2/library/atts.po... % module attributes imported into clpfd % loading /usr/local/lib/sicstus-3.11.2/library/lists.po... % module lists imported into attributes % loaded /usr/local/lib/sicstus-3.11.2/library/lists.po in module lists, 10 msec 18528 bytes % loaded /usr/local/lib/sicstus-3.11.2/library/atts.po in module attributes, 10 msec 46400 bytes % loading /usr/local/lib/sicstus-3.11.2/library/assoc.po... % module assoc imported into clpfd % module lists imported into assoc % loaded /usr/local/lib/sicstus-3.11.2/library/assoc.po in module assoc, 20 msec 17988 bytes % module lists imported into clpfd % loading /usr/local/lib/sicstus-3.11.2/library/ordsets.po... % module ordsets imported into clpfd % loaded /usr/local/lib/sicstus-3.11.2/library/ordsets.po in module ordsets, 0 msec 21496 bytes % loading /usr/local/lib/sicstus-3.11.2/library/ugraphs.po... % module ugraphs imported into clpfd % module ordsets imported into ugraphs % module lists imported into ugraphs % module assoc imported into ugraphs % loading /usr/local/lib/sicstus-3.11.2/library/random.po... % module random imported into ugraphs % module assoc imported into random % loading foreign resource /usr/local/lib/sicstus-3.11.2/library/sparc-solaris-5.7/random.so in module random % loaded /usr/local/lib/sicstus-3.11.2/library/random.po in module random, 20 msec 7776 bytes % loaded /usr/local/lib/sicstus-3.11.2/library/ugraphs.po in module ugraphs, 70 msec 84872 bytes % loading foreign resource /usr/local/lib/sicstus-3.11.2/library/sparc-solaris-5.7/clpfd.so in module clpfd % loaded /usr/local/lib/sicstus-3.11.2/library/clpfd.po in module clpfd, 170 msec 829440 bytes % consulting /home/undergrad3/ebaldelo/job.pl... % consulted /home/undergrad3/ebaldelo/job.pl in module user, 0 msec 912 bytes The starting time of the tasks are: task 1 starts at 0 task 2 starts at 5 task 3 starts at 10 task 4 starts at 5 task 5 starts at 11 task 6 starts at 16 % consulted /home/undergrad3/ebaldelo/schedule-template.pl in module user, 200 msec 836040 bytes yes | ?-