Flow shop model switching job order

[12eile...@gmail.com]

Hey AMPL Group,

I'm trying to implement a Algorithm for the flow shop problem. I got the problem, that the program won't order the jobs on a machine in an optimal order, but alsways orders them in the job-numbers order (jobs are set JOB = 1..n;).

How can i fix the problem, to have the order of the jobs switched, if necessary, to get a optimal result (= shorter cycle time) ?

I think there might be something wrong with the definition of the set in the first place, but I really dont know how to fix this problem.

MOD:

#Parameter:

param m integer > 0;    #number of machines
param n integer > 0;    #number of jobs
param R integer > 0;    #a big figure

set MACHINE = 1..m; #set of machines
set MACHINEa = 1..m-1;
set JOB = 1..n;     #set of jobs
set JOBa = 1..n-1;
param p {MACHINE, JOB} integer;    #processing time of job j on machine i


# Variables:

var x {MACHINE,JOB} integer;        #Startingtime von job j on machine i
var y {MACHINE,JOB,JOB} binary;        #binary variable that describes order
var C integer >= 0; # C = cycletime
               

# object and restrictions:

minimize zielfunktion: C;

subject to N1 {i in MACHINE, j in JOB}: #defines cycletime
x[m,j] + p[m,j] <= C;

subject to N2 {i in MACHINEa, j in JOB}: #job must be finished on earlier machine before started on later machine
x[i,j] + p[i,j] <= x[i+1,j];

subject to N2a {i in MACHINE, j in JOBa}: #only one job at a time on the same machine
x[i,j] + p[i,j] <= x[i,j+1];

subject to N3 {i in MACHINE, j in JOB, jj in JOB: j != jj}:
x[i,j] + p[i,j] <= x[i,jj] + R*(1-y[i,j,jj]);

subject to N4 {i in MACHINE, j in JOB , jj in JOB: jj != j && j != jj}:
y[i,j,jj] + y[i,jj,j] == 1; #to order the jobs as defined by y

subject to N5 {i in MACHINE, j in JOB}:
x[i,j] >= 0;

DATA:

param m := 2;
param n := 3;
param R := 1000;
param p:
       1  2  3:=
 1    2  4  1
 2    1  1  6;




 # in this example it processes job1 (2,1) first then job2(4,1) then job3(1,6)
It always processes the jobs in the order of their job name.

param p:
       3  2  1:=
 1    2  4  1
 2    1  1  6; # in this example it processes job1 (1,6) first then job2(4,1) then job3(2,1)

Thank you very much for your advise how to solve this problem.

Eileen

[Robert Fourer]

The only constraint that is affected by the ordering of the jobs is N2a, so you should focus on that constraint as the cause of the incorrect results. You can use the AMPL command "expand N2a" to see exactly the constraints that were generated by "subject to N2a ..." in your model.

Bob Fourer
am...@googlegrouops.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of 12eile...@gmail.com
Sent: Monday, November 13, 2017 10:37 AM
To: AMPL Modeling Language
Subject: [AMPL 15095] Flow shop model switching job order

I'm trying to implement a Algorithm for the flow shop problem. I got the problem, that the program won't order the jobs on a machine in an optimal order, but alsways orders them in the job-numbers order (jobs are set JOB = 1..n;).

How can i fix the problem, to have the order of the jobs switched, if necessary, to get a optimal result (= shorter cycle time) ?

I think there might be something wrong with the definition of the set in the first place, but I really dont know how to fix this problem.

...

[12eile...@gmail.com]

Thank you so much for your help. Indeed, it was N2a, that was stopping the model from working correct.