1.一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征在于,包括以下步骤,a.分析FJSP‑AGV问题特性,确定调度目标和约束条件;
b.定义参数和决策变量,将FJSP‑AGV调度目标和约束条件数学化,构建MILP模型;
c.使用CPLEX求解器验证模型的有效性;
d.输出最优解调度方案,包括工序开始时间、AGV到达时间、机床选择以及AGV选择。
2.根据权利要求1所述的一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征还在于,FJSP‑AGV问题特性包括,给定数量的加工工件,在给定数量的机床上进行加工,每个工件包含多道工序,某工件的某道工序在多个机床中选其一进行加工,工件的运输由多辆AGV负责,工件设置初始位置,初始位置与机床之间以及机床与机床之间具有距离,AGV的运输过程包括空载行程和负载行程,空载行程表示AGV需要从当前机床位置行驶到目标机床位置取工件;负载行程表示AGV取得工件后从所在机床位置运送到加工机床所在位置;
FJSP‑AGV调度目标是为每道工序分配机床以及AGV,并确定工序在机床上的加工次序和AGV上的运输次序,从而得到整个生产过程的最大完工时间最小化的最优调度方案。
3.根据权利要求2所述的一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征还在于,FJSP‑AGV满足以下约束条件,初始状态约束,所有机床和AGV在0时刻可用,所有工件0时刻可加工;
机床占用约束,每台机床在同一时刻最多只能加工一道工序;
AGV占用约束,每台AGV在同一时刻最多运输一个工件;
工件加工约束,任一工件在任一时刻只能在一台机床上加工,任一工件在不同机床间运输时只能由一台AGV运输;同一工件的不同工序按照给定的先后顺序进行加工,不同工件的工序之间是独立的,没有加工先后约束;
工件运输和加工时间关系约束,工件只有当其运输到所在加工机床才能开始加工,工件运输必须等到该工件在某一机床上完成后才能进行;
最大完工时间约束,最大完工时间不小于所有工件最后一道工序的完工时间;
其它约束,忽略同一机床上不同工件间的转换时间,AGV速度恒定,不考虑AGV路径干涉。
4.根据权利要求3所述的一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征还在于,参数定义包括,,工件序号;
,工件总数;
,工件集合, ;
,工序序号;
,工件 的工序数;
,工件 的工序集合, ;
,工件 的工序集合, ,工序0为虚拟工序,表示工件的起始工序,其加工时间为0;
,AGV序号;
,机床编号;
,工件 的第 道工序;
,机床总数;
,所有机床集合, ,机床0表示工件起始位置LU;
,工序 的可选机床总数;
,AGV的数量;
,AGV集合, ;
,工序 的可选机床集合;
,工序 在机床 上进行加工所需要的时间;
,机床 与 之间的运输时间, 表示工件起始位置LU到机床 间的运输时间;
,一个极大的正整数;
决策变量定义包括,
,0‑1决策变量,如果工序 选择在机床 上加工并由AGV 进行运输,;否则, ;
,0‑1决策变量,在某一机床上,如果 在工序 之前进行加工,;否则, ;
,0‑1决策变量,在某一AGV上,如果 在工序 之前进行运输,;否则, ;
,连续决策变量,表示工序 的开始时间;
,连续决策变量,表示AGV 运输工序 到所选机床的时间;
,连续决策变量,表示最大完工时间。
5.根据权利要求4所述的一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征还在于,初始状态约束数学化,包括约束(11)、约束(12)、约束(13), (11)
(12)
(13)
其中,约束(11)约束决策变量 的取值范围;约束(12)和(13)约束决策变量 的取值范围。
6.根据权利要求4所述的一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征还在于,机床占用约束数学化,包括约束(7)和约束(8), (7)
(8)
其中,对偶约束(7)和(8)表示安排在同一机床上不同工序先后加工顺序约束;当和 选择在机床 上加工时,即 和 ,如果 ,约束(7)约束 在 之后加工,约束(8)恒成立;如果 ,约束(8)约束在 之前加工,约束(7)恒成立;当 和 有一个或者都不在机床 上加工时,对偶约束(7)和(8)恒成立。
7.根据权利要求4所述的一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征还在于,AGV占用约束数学化,包括约束(9)和约束(10), (9)
(10)
其中,对偶约束(9)和(10)表示同一AGV运输不同工序到其所选机床的先后顺序约束;
当 和 分别选择在机床 和 上加工并由AGV 运输时,即 和 ,如果 ,约束(9)约束AGV 先运输 后运输 ,约束(10)恒成立;如果,约束(10)约束AGV 先运输 后运输 ,约束(9)恒成立;当 和有一个或者都不在机床 和 上加工并由AGV 运输时,对偶约束(9)和(10)恒成立。
8.根据权利要求4所述的一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征还在于,工件加工约束数学化,包括约束(1)和约束(4), (1)
(4)其中,约束(1)表示工序 只能选择在一台机床上加工,且只能由一台AGV进行运输;
约束(4)限定工件起始位置在LU位置,虚拟工序0由AGV1运输。
9.根据权利要求4所述的一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征还在于,工件运输和加工时间关系约束数学化,包括约束(2)、约束(3)、约束(5), (2)
(3)
(5)
其中,约束(2)表示工序 只有当其运输到所在加工机床才能开始加工;约束(3)表示如果 和 分别选择在机床 到 上加工时, 被运输到所在机床 的时间不小于 的完工时间 以及从机床 到 的运输时间 之和;约束(5)表示工件的首道工序运输到所选机床的时间约束。
10.根据权利要求4所述的一种基于混合整数规划模型的FJSP‑AGV的建模方法,其特征还在于,最大完工时间约束数学化,包括约束(6), (6)
其中,约束(6)表示最大完工时间不小于所有工件最后一道工序的完工时间。