柔性车间调度是典型的N-P问题,数学模型如下:
数学模型
假设有n
个工件需要在m
台机器上进行加工。每个工件包含一道或多道工序,每道工序可以在多台机器上进行加工,但每道工序的加工时间随机器的不同而不同。
符号定义
n
:工件数量m
:机器数量- :表示工件
j
的第i
道工序 - :表示工序
O_ij
在机器k
上的加工时间 - :表示所有工件完成加工的最大完工时间(也常称为“makespan”)
- :决策变量,当工序
O_ij
在机器k
上加工时取1,否则取0
目标函数
柔性车间调度的常见目标是最小化最大完工时间,这可以表示为:
其中,的计算依赖于具体的调度方案,即每台机器上各工序的加工顺序和开始时间。
约束条件
柔性车间调度的约束条件主要包括以下几点:
-
同一台机器同一时刻只能加工一个工件:
其中,是工件j
的工序数量,t
表示时间。这个约束确保在任何时刻t
,机器k
上只有一个工件在加工。 -
同一工件的同一道工序在同一时刻只能被一台机器加工:
这个约束确保每个工序只能在一台机器上加工。 -
任意工序开始加工不能中断:
调度方案中已经隐含此约束。 -
同一工件的工序之间存在先后约束:
即工序的顺序是预先确定的。 -
所有工件在零时刻都可以被加工:
这个约束表示调度从时间零点开始。
粒子群算法的流程不再赘述。
完整代码见: https://download.csdn.net/download/corn1949/89414049
算例数据如下:
工件号 | 工序 | M1 | M2 | M3 | M4 | M5 | M6 |
1 | 1 | 3 | 4 | 5 | -1 | -1 | -1 |
1 | 2 | -1 | -1 | 10 | -1 | -1 | -1 |
1 | 3 | -1 | 12 | 9 | 8 | -1 | 5 |
1 | 4 | -1 | 7 | -1 | 2 | 3 | -1 |
2 | 1 | -1 | 11 | -1 | 6 | 7 | -1 |
2 | 2 | -1 | 8 | -1 | -1 | -1 | 6 |
2 | 3 | -1 | -1 | 5 | 11 | -1 | 13 |
3 | 1 | -1 | -1 | 3 | -1 | -1 | -1 |
3 | 2 | 2 | 3 | 3 | -1 | -1 | -1 |
3 | 3 | -1 | -1 | 10 | 4 | 5 | -1 |
3 | 4 | 10 | -1 | 11 | -1 | 3 | -1 |
4 | 1 | -1 | -1 | 12 | -1 | -1 | 7 |
4 | 2 | 8 | 9 | 9 | -1 | 12 | -1 |
4 | 3 | -1 | -1 | 2 | -1 | -1 | -1 |
4 | 4 | -1 | -1 | -1 | 11 | 12 | -1 |
5 | 1 | -1 | -1 | 5 | 8 | -1 | 9 |
5 | 2 | -1 | -1 | -1 | 13 | 12 | 8 |
5 | 3 | 3 | 5 | 6 | -1 | -1 | -1 |
5 | 4 | -1 | -1 | -1 | 5 | 6 | -1 |
6 | 1 | 5 | 7 | 9 | -1 | -1 | -1 |
6 | 2 | -1 | -1 | 11 | 5 | -1 | 10 |
6 | 3 | -1 | -1 | -1 | 4 | 3 | 9 |
6 | 4 | -1 | -1 | -1 | 5 | 10 | -1 |
MATLAB主程序如下:
程序结果如下:
运行时间
rumtime_pso =
5.3394316
粒子群算法优化得到最优目标值
Valuebest =
38
粒子群算法优化得到最优粒子
psobest =
1 至 6 列
0.807799087914073 0.306309227674272 0.442135525692086 0.632880346280301 0.641693389470385 0.520189722967532
7 至 12 列
0.704326938591365 0.596599575086721 0.696891096627419 0.429041868570891 0.585924105261037 0.362582397868678
13 至 18 列
0.559651034778297 0.572796589788628 0.618249276935865 0.413821157586821 0.618559667953546 0.446161435550871
19 至 24 列
0.686582929302922 0.578608572037444 0.420636186679292 0.666470750438744 0.201151952517725 2.93126251429749
25 至 30 列
1.34239826499873 2.49977875898474 2.98664700116511 2.09901832320219 1.71622326495051 1.99067345337225
31 至 36 列
1.16267419492853 3.15741956630322 2.39695846952555 1.71756348576486 2.22413083137163 2.22079424094148
37 至 42 列
1.26734250098306 2.13260511835173 1.88079389045675 2.19794951228853 2.99954380016584 2.29207015694117
43 至 46 列
1 2.58484850789946 3.6176736920122 1.4633026270412
G =
6 1 1 0 5
1 1 2 0 4
4 1 6 0 7
5 1 3 0 5
6 2 4 5 10
3 1 3 5 8
1 2 3 8 18
5 2 5 5 17
2 1 4 10 16
4 2 2 7 16
4 3 3 18 20
6 3 6 10 19
3 2 3 20 23
3 3 4 23 27
4 4 5 20 32
5 3 2 17 22
1 3 3 23 32
2 2 2 22 30
6 4 4 27 32
5 4 5 32 38
3 4 1 27 37
2 3 3 32 37
1 4 4 32 34
outcell =
'零件号' '工序号' '机器号' '开始时间' '结束时间'
[ 1] [ 1] [ 2] [ 0] [ 4]
[ 1] [ 2] [ 3] [ 8] [ 18]
[ 1] [ 3] [ 3] [ 23] [ 32]
[ 1] [ 4] [ 4] [ 32] [ 34]
[ 2] [ 1] [ 4] [ 10] [ 16]
[ 2] [ 2] [ 2] [ 22] [ 30]
[ 2] [ 3] [ 3] [ 32] [ 37]
[ 3] [ 1] [ 3] [ 5] [ 8]
[ 3] [ 2] [ 3] [ 20] [ 23]
[ 3] [ 3] [ 4] [ 23] [ 27]
[ 3] [ 4] [ 1] [ 27] [ 37]
[ 4] [ 1] [ 6] [ 0] [ 7]
[ 4] [ 2] [ 2] [ 7] [ 16]
[ 4] [ 3] [ 3] [ 18] [ 20]
[ 4] [ 4] [ 5] [ 20] [ 32]
[ 5] [ 1] [ 3] [ 0] [ 5]
[ 5] [ 2] [ 5] [ 5] [ 17]
[ 5] [ 3] [ 2] [ 17] [ 22]
[ 5] [ 4] [ 5] [ 32] [ 38]
[ 6] [ 1] [ 1] [ 0] [ 5]
[ 6] [ 2] [ 4] [ 5] [ 10]
[ 6] [ 3] [ 6] [ 10] [ 19]
[ 6] [ 4] [ 4] [ 27] [ 32]
>>
完整代码见: https://download.csdn.net/download/corn1949/89414049
标签:工序,27,机器,fjsp,加工,32,MATLAB,工件,PSO From: https://blog.csdn.net/corn1949/article/details/139567741