流水线调度优化模型武大数模选拔.pdfVIP

题目：流水线车间调度优化模型

【摘要】

通过对问题的分析，流水线车间调度问题可以归结为一个整数规划问题，本

论文中根据题目所给的条件以及实际情况依次建立起两个模型。在满足加工时间最

短的前提下，基于对问题约束条件不同的翻译得到两个模型从而得到不同的生产顺

序，为决策者提供了更多的生产方案。联系生产生活实际情况，放松加工工件必须

遵循相对顺序不变这一约束条件，提出模型的改进方向。

模型一，根据题目要求即每个工件的加工顺序为弯折——焊接——装配且每

台机器每次只能处理一个加工件。构造一个每行每列只含一个1其余元素为0的矩

阵，通过矩阵乘积实现对原来工件工序耗时的行变换，整个过程相当于遍历。建立

线性规划模型，利用LINGO软件求解。结果为当加工顺序为4—1—3—6—5—2

时，用时最短为35min，利用Excel作出甘特图使整个生产安排流程更加清晰，引

入时间利用率的概念即加工工件的时间占开启时间的百分比，得到在加工顺序为

4—1—3—6—5—2时机器一（弯折）机器二（焊接）机器三（装配）的时间利用

率依次为

，

，

，从而可从机器负载评价加工过程。

模型二，将每台机器每次只能处理一个加工件这一约束条件翻译为一旦开始

顺序确定，则后续工序仍按原顺序进行。引入0—1变量表示两工件生产顺序，建

立0—1规划模型，利用LINGO软件求解。结果为当加工顺序为1—3—6—4—5—2

时，用时最短为35min。利用甘特图对结果进行分析与检验，得到3台机器的时间

利用效率分别为

，为决策者选择方案提供了更多的参考指标。

讨论本文所建模型的优点和缺点，横向的对比两个模型。在工件数目相对较

多（在十这一数量级上）的情况下选择模型一求解，LINGO可以在短时间内给出答

案；在数据量较少的情况下运用模型二求解，因为它模型建立过程简单易懂，编程

容易。但是对于工件数目处于百个数量级时，两种模型均无法在短时间内得到答

案，需要建立新的模型，设计新的算法求解此类大规模排序问题。

针对模型的部分缺点提出优化改进方案，改变初始工件加工各工序耗时矩

阵，即动态设立初始点以弥补LINGO软件只能输出一组最优解的局限，得出当加工

顺序为3—1—6—5—4—2，4—1—6—5—3—2，3—4—1—6—5—2，1—4—6—

5—3—2时也能使加工时间最短为35min，提供了更多的可选择方案。联系实际生

产，根据各机器单位时间的工作成本不同，可以建立多目标规划模型，既要使总的

时间最短又要使整个加工过程机器的总成本最低，同时实现时间和成本的最优化。

可以为决策者提供更实用的生产工件加工顺序规划。

文末简述了模型的推广与应用。将此线性整数规划模型稍作修改就可以运用

到安排面试人员的面试顺序、单机调度最优化、公交车的调度等问题。枚举的思想

可以用到一些小规模的排序问题中，利用优化软件也可以快速求得其最优解。可以

为实际生产生活解决问题带来极大地便利。

【关键词】流水线调度线性整数规划模型甘特图LINGO

1问题重述

21世纪是一个注重效率和时间利用率的时代，在工业生产和经济发展中，我

们竭尽全力去节省时间，在有限的时间内尽可能多的创造财富。所以，根据实际的

生产需要及生产要求合理的安排生产的顺序尤为重要。

生产调度即将分好批的生产任务落实到加工设备上，以使某代价最小，所谓

的某代价最小也即优化目标。所谓的流水线车间调度即有一组功能不同的机床，待

加工的零件包含多道工序，每道工序在一台机床上加工，所有零件的加工顺序相

同。

在本问题中，共有3个机床，6种待加工零件，每种零件需要经过3道工

序，每台机床同一时间只能加工一种工件，确定了开始时的加工顺序随后的加工顺

序不会改变。

建立适当的数学模型，确定加工件的先后顺序，使得加工所有用件用时最

短。

6种工件加工工序需时（分钟）见下表1：

表1：6种加工工件各工序耗时表（min）

加工件123456

弯折363557

焊接542445

装配524636