Wednesday, March 25, 2009

A machine scheduling problem

Hello

I'm new to AMPL.  I have  a scheduling problem that is giving me
trouble. I have a set of unrelated machines.  I have a set of jobs.
Each job has a set of operations to perform in order.  I want to
minimize the time of completion of the last job/operation pair
processed. Below is my .mod file. In the data section I have two test
cases - one is commented and one is not.

The commented test has no problems. The solver finds the solution. The
uncommented test case gives the following:

CPLEX Error  1217: No solution exists.
CPLEX Error  1217: No solution exists.
CPLEX Error  1262: No basis exists.
CPLEX 7.1.0: integer infeasible.
1894 MIP simplex iterations
39 branch-and-bound nodes; no basis.

Like I said I am new to this type of programming. Does anybody smarter
than me see a problem with any of my constraints? Or a comment on what
usually causes error 1217 and 1262?

#################################### .mod file
set job;
set oper;
set mach;
param first > 0;
param last  > first;
set T := first .. last;

var max_val;
var asgn { job, oper, mach, T } binary;
var sched  { mach, T } >= 0;
var delay  { mach, T } >= 0;

param time { job, oper, mach } >= 0;

minimize z: max_val;

# the last scheduled task for each machine is less than or equal to
our objective
subject to max_val_constraint { m in mach }:  sched[m,last] <=
max_val;

# sched[m,t] is the completion time of the task machine m is doing at
time t
# sched[m,t] = sched[m,t] + delay[m,t] + { time to process assigned
task}
subject to mach_sched_0 { m in mach, t in T: t>1}:
  sched[m,t] = sched[m,t-1] + delay[m,t] +
    sum{ i in job, j in oper } asgn[i,j,m,t] * time[i,j,m];

subject to mach_sched_1 { m in mach }:
  sched[m,1] = delay[m,1] +
    sum{ i in job, j in oper } asgn[i,j,m,1] * time[i,j,m];

# for each job/operation pair, only assign it to be processed once
subject to jobtask_assign_cnt { i in job, j in oper }:
  sum{ m in mach, t in T } asgn[i,j,m,t] = 1;

# for each machine at time t, assign only one task to process
subject to machtime_assign_cnt { m in mach, t in T }:
  sum{ i in job, j in oper } asgn[i,j,m,t] <= 1;

# for job i oper j, make sure job i, oper j-1 has been previously assigned
subject to jobtask_ordering { i in job, j in oper, t in T: j>1 }:
  sum{ m in mach } asgn[i,j,m,t] >= sum{ m in mach } asgn[i,j-1,m,t];

subject to delay_constraint { m in mach, t in T }:
  delay[m,t] >= 0;

data;

set job  := 1 2 3 ;
set oper := 1 2 3 4;
set mach := 1 2 ;

param first := 1;
param last  := 12;

param time :=
[1,*,*]: 1 2 :=
1 1 4
2 2 2
3 3 3
4 4 4

[2,*,*]: 1 2 :=
1 2 4
2 2 1
3 1 6
4 1 2

[3,*,*]: 1 2  :=
1 3 4
2 2 3
3 3 1
4 4 3;

# test that works
#set job  := 1 2;
#set oper := 1 2;
#set mach := 1 2 3;
#set T := 1 2 3 4;
#
#param time :=
#[1,*,*]: 1 2 3 :=
#1 1 2 3
#2 1 2 3
#
#[2,*,*]: 1 2 3 :=
#1 1 2 3
#2 1 2 3;

The constraint

# for job i oper j, make sure job i, oper j-1 has been previously assigned
subject to jobtask_ordering { i in job, j in oper, t in T: j>1 }:
  sum{ m in mach } asgn[i,j,m,t] >= sum{ m in mach } asgn[i,j-1,m,t];

does not seem to be formulated correctly. It says that all operations have to be executed in the same time period t. For this data set you have four operations and only two machines available. The smaller data set had two operations which can be allocated to the available two machines. If you really want (i,j-1) to be finished before (i,j) you probably need to keep track when each task (i,j) finishes. I believe your current formulation mixes up time slots t and completion times modeled via sched[m,t]. If your execution times are small integer, then map everything to time slots. If your execution times are floating point numbers, you should look into a continuous time formulation (e.g. through x[i,j,ii,jj,m] = 1 iff (i,j) precedes (ii,jj) on machine m).