在glpk（gusek）中实施开放式车间调度算法

Question

我已经尝试在gusek中实现“开店调度”算法，请使用以下代码：

。dat：

param endTime := 2809 ;
param nMach := 4 ;
param nJobs := 3 ;

param duration:  
        1    2    3 :=
   1  121  661    6
   2  333  168  489
   3  343  621  212
   4  171  505  324 ;

。mod：

param endTime integer > 0;
param nMach integer > 0;
param nJobs integer > 0;

param duration {1..nMach, 1..nJobs};

var Start {1..nMach, 1..nJobs} integer >= 0, <= endTime;
var Makespan integer >= 0, <= endTime;

minimize Objective: Makespan;

subject to NoJobConflicts 
      {m in 1..nMach, j1 in 1..nJobs, j2 in j1+1..nJobs}:
   Start[m,j1] + duration[m,j1] <= Start[m,j2]  or
   Start[m,j2] + duration[m,j2] <= Start[m,j1];

subject to NoMachineConflicts 
      {m1 in 1..nMach, m2 in m1+1..nMach, j in 1..nJobs}:
   Start[m1,j] + duration[m1,j] <= Start[m2,j]  or
   Start[m2,j] + duration[m2,j] <= Start[m1,j];

subj to MakespanDefn {m in 1..nMach, j in 1..nJobs}:
   Start[m,j] + duration[m,j] <= Makespan;

但是我收到以下错误：“约束语句中的语法错误。上下文：... tart [m，j1] +持续时间[m，j1] <=起始[m，j2]或”。

据我所知，gusek用于线性问题，但运算符“或”用于非线性问题。

有没有一种方法可以使用gusek解决此问题。

欢迎任何提示。

Answer 1

类似约束

x + a ≤ y  or   
y + b ≤ x 

可以用big-M约束来实现：

x + a ≤ y + M⋅δ   
y + b ≤ x + M(1-δ)
δ ∈ {0,1}

其中M是足够大的常数（要选择得尽可能紧密）。

因此，您的情况：

subject to NoJobConflicts 
      {m in 1..nMach, j1 in 1..nJobs, j2 in j1+1..nJobs}:
   Start[m,j1] + duration[m,j1] <= Start[m,j2] + M*d1[m,j1,j2];

subject to NoJobConflicts2 
      {m in 1..nMach, j1 in 1..nJobs, j2 in j1+1..nJobs}:
   Start[m,j2] + duration[m,j2] <= Start[m,j1] + M*(1-d1[m,j1,j2]) ;

M可以是计划范围的长度，d1是一个二进制变量。

与其他情况类似。在那里，您应该使用其他二进制变量。例如d2。