流水线调度优化模型武大数模选拔.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世纪是一个注重效率和时间利用率的时代，在工业生产和经济发展中，我

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

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

去留无意，闲看庭前花开花落；宠辱不