I have been working on an assignment where I have to optimize the scheduling problem for 2 parallel gantry cranes. I made a mathematical model for 1 crane and also text it on CPLEX. It works fine but I couldn’t make the adjustments for 2 cranes (sometimes results are infeasible and sometimes with errors). It would be great if someone helped me out. Thank you 🙂

Mathematical model:

G2|r_j|∑T_j

Objective Function:

f = min∑T_j

Constraints:

Job ordering decision variable:
x_jj= 0
x_(jk )+ x_kj=1
x_jk+ x_kl- x_jl  ≤1
Tardiness definition:
T_j≥ S_j  +  p_j- d_j
T_j≥0
Start time:
S_k+H × x_kj  ≥ S_j+ p_j
S_j+H × x_jk  ≥ S_k+ p_k
H=max⁡(r_j )+ ∑_jp_j
Release date:
S_j  ≥ r_j
Where:
T = tardiness
j = jobs/tasks
x = binary decision variable
S = starting time
p = processing time
H = large constant
r = release time

CPLEX code:

int n = 4; // number of jobs
int p[1..n] = [12, 8, 15, 9];
int r[1..n] = [0, 0, 0, 0];
int d[1..n] = [16, 26, 25, 27];

// Calculate H
int H = max(i in 1..n) r[i] + sum(i in 1..n) p[i];

dvar boolean x[1..n][1..n];
dvar float+ S[1..n]; // Start times, non-negative
dvar float+ T[1..n]; // Tardiness, non-negative

// Objective: Minimize total tardiness
minimize sum(j in 1..n) T[j];

// Constraints
subject to {
// Tardiness constraints
forall(j in 1..n) {
T[j] >= S[j] + p[j] - d[j];
}

    // xjj constraints
    forall(j in 1..n) {
        x[j][j] == 0;
    }
    
    // Ordering constraints
    forall(j in 1..n, k in 1..n : j != k) {
        x[j][k] + x[k][j] == 1;
    }
    
    // Transitive constraints
    forall(j in 1..n, k in 1..n, l in 1..n : j != k && k != l && j != l) {
        x[j][k] + x[k][l] - x[j][l] <= 1;
    }
    
    // Temporal constraints
    forall(j in 1..n, k in 1..n : j != k) {
        S[k] + H * x[k][j] >= S[j] + p[j];
        S[j] + H * x[j][k] >= S[k] + p[k];
    }
    
    // Release date constraints
    forall(j in 1..n) {
        S[j] >= r[j];
    }

}

Output:

execute {
writeln("Start times: ", S);
writeln("Tardiness: ", T);
writeln("Job ordering matrix: ", x);
}

I need help in the following areas:

1. I introduced 1 more decision variable for assigning a task to either crane 1 or 2 but results become infeasible. Can someone help me out to make a mathematical model for 2 cranes/ can someone help to modify my 1 crane code for 2 cranes?
2. I know how to solve 1 crane tardiness problem on paper by branch and bound method. How to apply branch and bound (B&B method) for 2 parallel cranes? For 2 gantry cranes scheduling problem, how to validate it by B&B method?

Thank you!