车间调度建模系列2|复杂车间调度问题描述

获取更多资讯,赶快关注公众号(名称:智能制造与智能调度,公众号:deeprlscheduler)吧!

三维析取图模型建模系列目录

  针对存在上一篇文章中特点(车间调度建模系列1|复杂车间调度问题特点)的复杂作业车间调度问题,综合考虑动态工时动态工作日历周转运输外协等复杂约束,其描述如下:

   N J NJ NJ个工件需要在 N M NM NM台机床上加工,每个工件 J i J_i Ji​包含 N O i NO_i NOi​道工序,其中 O i h O_{ih} Oih​为工件 J i J_i Ji​的第 h h h道工序。每道工序 O i h O_{ih} Oih​均可以在可选机床集合 M i h \boldsymbol{M}_{i h} Mih​中的任意一台 M m M_m Mm​上进行加工,工序 O i h O_{ih} Oih​在机床 M m M_m Mm​上的加工时间为 P i h m P_{ihm} Pihm​。目标就是在满足以下约束的前提下优化一个或多个生产目标。

  下面列出了用于问题表述的符号。

(1)索引

m , n , r m,n,r m,n,r:机床序号, m , n , r = 1 , 2 , 3 , . . . , N M m,n,r=1,2,3,...,NM m,n,r=1,2,3,...,NM;

i , j i,j i,j:工件序号, i , j = 1 , 2 , 3 , . . . , N J i,j=1,2,3,...,NJ i,j=1,2,3,...,NJ;

h , l h,l h,l:工件工序序号, h = 1 , 2 , 3 , . . . , N O i , l = 1 , 2 , 3 , . . . , N O l h=1,2,3,...,NO_i,l=1,2,3,...,NO_l h=1,2,3,...,NOi​,l=1,2,3,...,NOl​;

o o o:所有工序索引, o = 1 , 2 , 3 , . . . , N O o=1,2,3,...,NO o=1,2,3,...,NO;

(2)参数

M \boldsymbol{M} M:总的机床集合;

J \boldsymbol{J} J:总的工件集合;

N M NM NM:机床数量;

N J NJ NJ:工件数量;

N O NO NO:工序数量;

N O i NO_i NOi​:工件 i i i的工序总数;

M i h \boldsymbol{M}_{i h} Mih​:工件 i i i的第 h h h道工序的可选加工机床集合;

N M i h NM_{ih} NMih​:工件 i i i的第 h h h道工序的可选机床数;

O i h O_{ih} Oih​:工件 i i i的第 h h h道工序;

O \boldsymbol{O} O:所有工序集合;

O r e a d y \boldsymbol{O}_{ready} Oready​:当前就绪任务集合;

O i h m O_{ihm} Oihm​:工件 i i i的第 h h h道工序在机床 m m m上加工;

O i ′ h ′ m O_{i^{\prime} h^{\prime} m} Oi′h′m​:机床 m m m上排在工序 O i h O_{ih} Oih​前的一道工序;

P i h m P_{ihm} Pihm​:工件 i i i的第 h h h道工序在机床 m m m上的加工时间;

P i h P_{ih} Pih​:工件 i i i的第 h h h道工序在所有可选机床上的平均加工时间;

S i h m S_{ihm} Sihm​:工件 i i i的第 h h h道工序在机床 m m m上的开始加工时间;

C i h m C_{ihm} Cihm​:工件 i i i的第 h h h道工序在机床 m m m上的完成加工时间;

L L L:一个足够大的正数;

C i C_i Ci​:工件 i i i的完成时间;

C m a x C_{max} Cmax​:所有工件中最晚的完成时间, C max ⁡ = ∑ i = 1 N J max ⁡ { C i } C_{\max }=\sum_{i=1}^{N J} \max \left\{C_{i}\right\} Cmax​=∑i=1NJ​max{Ci​} ;

d i d_i di​:工件 i i i的交货期;

w i w_i wi​:工件 i i i的权重;

b i b_i bi​:工件 i i i的批量;

T i T_i Ti​:工件 i i i的拖期, T i = max ⁡ { 0 , C i − d i } T_{i}=\max \left\{0, C_{i}-d_{i}\right\} Ti​=max{0,Ci​−di​};

O C i h OC_{ih} OCih​:工序 O i h O_{ih} Oih​的单位时间加班成本;

C C i h CC_{ih} CCih​:工序 O i h O_{ih} Oih​的外协成本;

T C i h TC_{ih} TCih​:工序 O i h O_{ih} Oih​的单位转运批量运输成本;

t b i h tb_{ih} tbih​:工序 O i h O_{ih} Oih​的转运批量;

(3)决策变量

x i h m = { 1 ,  如果工序  O i h  选择机器  M m 0 ,  否则  x_{i h m}=\left\{\begin{array}{l} 1, \text { 如果工序 } O_{i h} \text { 选择机器 } M_{m} \\ 0, \text { 否则 } \end{array}\right. xihm​={1, 如果工序 Oih​ 选择机器 Mm​0, 否则 ​

y i h j l m = { 1 ,  如果  O i h m  先于  O j l m  加工  0 ,  否则  y_{i h j l m}=\left\{\begin{array}{l} 1, \text { 如果 } O_{i h m} \text { 先于 } O_{j l m} \text { 加工 } \\ 0, \text { 否则 } \end{array}\right. yihjlm​={1, 如果 Oihm​ 先于 Ojlm​ 加工 0, 否则 ​

o o i h = { 1 ,  如果工序  O i h  加班  0 ,  否则  o o_{i h}=\left\{\begin{array}{l} 1, \text { 如果工序 } O_{i h} \text { 加班 } \\ 0, \text { 否则 } \end{array}\right. ooih​={1, 如果工序 Oih​ 加班 0, 否则 ​

c o i h = { 1 ,  如果工序  O i h  外协  0 ,  否则  c o_{i h}=\left\{\begin{array}{l} 1, \text { 如果工序 } O_{i h} \text { 外协 } \\ 0, \text { 否则 } \end{array}\right. coih​={1, 如果工序 Oih​ 外协 0, 否则 ​

(4)目标函数

 Minimize  C max ⁡ (2.1) \text { Minimize } C_{\max }\tag{2.1}  Minimize Cmax​(2.1)

 Minimize  T W T = ∑ i = 1 N J w i ⋅ T i (2.2) \text { Minimize } T W T=\sum_{i=1}^{N J} w_{i} \cdot T_{i}\tag{2.2}  Minimize TWT=i=1∑NJ​wi​⋅Ti​(2.2)

 Minimize  T O C = ∑ o i h ∈ O o o i h ⋅ O C i h ⋅ P i h m (2.3) \text { Minimize } T O C=\sum_{o_{i h} \in \boldsymbol {O}} o o_{i h} \cdot O C_{i h} \cdot P_{i h m}\tag{2.3}  Minimize TOC=oih​∈O∑​ooih​⋅OCih​⋅Pihm​(2.3)

 Minimize  T C C = ∑ o i h ∈ O c o i h ⋅ C C i h (2.4) \text { Minimize } \quad T C C=\sum_{o_{i h} \in \boldsymbol {O}} c o_{i h} \cdot C C_{i h}\tag{2.4}  Minimize TCC=oih​∈O∑​coih​⋅CCih​(2.4)

 Minimize  T T C = ∑ i = 1 N J ∑ h = 1 N O i − 1 b i t b i ⋅ T C i h (2.5) \text { Minimize } T T C=\sum_{i=1}^{N J} \sum_{h=1}^{N O_{i-1}} \frac{b_{i}}{t b_{i}} \cdot T C_{i h}\tag{2.5}  Minimize TTC=i=1∑NJ​h=1∑NOi−1​​tbi​bi​​⋅TCih​(2.5)

(5)约束

 s.t.  { C i ≥ 0 , C i h m ≥ 0 , ∀ i , h , m ( a ) S i h m + x i h m × P i h m ≤ C i h m , ∀ i , h , m ( b ) ∑ m ∈ M i h x i h m = 1 , ∀ i , h ( c ) C i h m ≤ S i ( h + 1 ) n , i ∈ [ 1 , N J ] , h ∈ [ 1 , N O i − 1 ] ( d ) S i h m + P i h m ≤ S j l m + L ( 1 − y i h j l m ) , ∀ i , h , m , j , l ( e ) (2.6) \text { s.t. }\left\{\begin{array}{l} C_{i} \geq 0, C_{i h m} \geq 0, \forall i, h, m \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(a)\\ S_{i h m}+x_{i h m} \times P_{i h m} \leq C_{i h m}, \forall i, h, m \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(b)\\ \sum_{m \in \boldsymbol{M}_{i h}} x_{i h m}=1, \forall i, h \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(c)\\ C_{i h m} \leq S_{i(h+1) n}, i \in[1, N J], h \in\left[1, N O_{i}-1\right] \quad\quad\quad\quad\quad\quad\quad(d)\\ S_{i h m}+P_{i h m} \leq S_{j l m}+L\left(1-y_{i h j l m}\right), \forall i, h, m, j, l \quad\quad\quad\quad\quad\quad(e) \end{array}\right.\tag{2.6}  s.t. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​Ci​≥0,Cihm​≥0,∀i,h,m(a)Sihm​+xihm​×Pihm​≤Cihm​,∀i,h,m(b)∑m∈Mih​​xihm​=1,∀i,h(c)Cihm​≤Si(h+1)n​,i∈[1,NJ],h∈[1,NOi​−1](d)Sihm​+Pihm​≤Sjlm​+L(1−yihjlm​),∀i,h,m,j,l(e)​(2.6)

目标2.1-2.5分别用于最小化制造期、总加权拖期、总加班成本、总外协成本和总运输成本;不等式2.6(a)表示工件和每道工序的完成时间不能为负;不等式2.6(b)表示考虑日历情况下工序完成时间与开始时间间隔不能小于工序工时,只有当此间隔内均为上班班次(包括正常上班和加班)时等式才成立;等式2.6©意味着每道工序只能分派到一台机床上;不等式2.6(d)表明只有前道工序结束了后道工序才能开始,保证了顺序约束;不等式2.6(e)确保在同一机床上同一时刻最多只能加工一个工序,即满足能力约束。

上一篇:Codeforces Round #767 (Div. 2) 题解


下一篇:2. 字符串设备的创建