在 glpk (gusek) 中实现 Open Shop Scheduling 算法

Question

我尝试使用以下代码在 gusek 中实现 'open shop scheduling' 算法：

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

但我收到以下错误："syntax error in constraint statement. Context: ...tart [ m , j1 ] + duration [ m , j1 ] <= Start [ m , j2 ] or "。

据我所知，gusek 用于线性问题，而运算符 'or' 用于非线性问题。

有没有办法使用 gusek 解决这个问题。

欢迎任何提示。

Answer 1

类似

的约束

x + a ≤ y  or   
y + b ≤ x

可以用大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。

在 glpk (gusek) 中实现 Open Shop Scheduling 算法

Implement Open Shop Scheduling algorithm in glpk (gusek)

linear-programming

glpk