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).

http://abecharles.weebly.com/blog-entries.html

ReplyDeleteThis is genius! I have quite a few equations on my blog too.

The history of mathematics goes a long way back with devices and methods of calculation.

ReplyDeleteMachines Starting with the ancient Abacus,

the slide rule and the logarithms, the mechanical calculating machines, the electromechanical

calculators and finally the electronic computer.