This example shows the trace of solving Open-Shop Scheduling (OSS) instance
gp03-01 by Guéret and Prins.
makespan
: due time to complete all operations
s_i_j
: start time of the operation O_i_j
where
i
is the job number and j
is the machine number.
-
p_i_j
: process time of the operation O_i_j
given as follows.
p_0_0 = 661
, p_0_1 = 6
, p_0_2 = 333
p_1_0 = 168
, p_1_1 = 489
, p_1_2 = 343
p_2_0 = 171
, p_2_1 = 505
, p_2_2 = 324
-
q_i_j_k_l
: boolean variable meaning operation O_i_j
precedes
operation O_k_l
- Constrains:
s_i_j + p_i_j <= makespan
(for all i
and j
)
- q_i_j_i_l or (s_i_j + p_i_j <= s_i_l)
(for all i
and j < l
)
q_i_j_i_l or (s_i_l + p_i_l <= s_i_j)
(for all i
and j < l
)
- q_i_j_k_j or (s_i_j + p_i_j <= s_k_j)
(for all i < k
and j
)
q_i_j_k_j or (s_k_j + p_k_j <= s_i_j)
(for all i < k
and j
)
In the diagram, each rounded box corresponds to each
s_i_j
, and
each arrow corresponds to each
q_i_j_k_l
.