流程型生产企业订单选择问题及方法研究

庄晓霞 王军

摘 要：近年来，随着我国经济增长速度的逐渐回落，生产企业越来越重视进行产能规划，流程型生产企业进行产能规划的关键在于订单选择。传统的订单选择问题把生产排序和订单选择分开进行考虑，订单选择的优劣完全依赖排序的结果。文章研究了流程型生产订单选择与生产排序的相互关系，提出一个以利润最大化为目标的非线性0-1规划模型，模型同时考虑订单排序和选择。利用Lingo 11.0对模型进行求解检验，结果表明，当订单规模不超过16个时，可以在有效时间内得到模型最优解；对大规模订单选择问题，还需要提出效率更高的求解非线性0-1规划问题的算法。

关键词：流程型生产；订单选择；生产排序；非线性0-1规划

中图分类号：F273 文献标识码：A

Abstract： In recent years， along with the economic growth of China declining slowly， the process production enterprises pay more and more attention to the production capacity planning. Order selection problem becomes the key to the production capacity planning in the process production enterprise. The traditional order selection problem separates production scheduling and order selection. The merits of the order selection depend entirely on sorting result. This paper studies the relationship of the order selection and the production scheduling on process production orders and proposes a nonlinear 0-1 programming model aiming at profit maximization， simultaneously considering the order sorting and selection. The model is solved by using Lingo 11.0 inspection. And results show that model optimal solution can be obtained in the effective time， when the order size is less than 16. For large-scale order selection problem， a more efficient algorithm for solving the nonlinear 0-1 programming problem still need to be put forward.

Key words： process production； order selection； production scheduling； nonlinear 0-1 programming

0 引 言

近年来，随着我国经济增长速度的逐渐回落，中国经济进入新常态，倡导改变增长方式，调整产业结构。这样的背景下生产企业越来越重视进行产能规划，尤其是流程型生产企业，订单选择问题已成为流程型生产企业产能规划的关键问题。

流程型生产企业，如化工、冶金、饲料等行业，由于其自身生产的特殊性，订单的生产转换成本很高，一个订单完成后下一个订单才会开始。在企业进行产能规划的背景下，产能往往是有限的，订单延期会导致成本增加或惩罚，而订单提前会导致库存成本增加，这就使得生产排序和订单选择显得尤为重要。

订单选择问题的研究已经持续了二十年。订单选择问题的研究通常是在订单按照某种规则排序后进行的，常用的排序规则有先到先得（FCFS）、最早完工时间（EDD）、最短工作时间（SPT）和最大利润等规则，而后再对排序后的订单进行筛选。Slotnick开创性地研究了在工厂生产能力有限、存在延迟惩罚情况下，怎样从大量的订单中筛选利润最大化的订单集合[1]。在引入与生产次序相关的生产准备时间的情况下，对于批量订单，Wester提出了单机器环境下的订单接受策略[2]。Luebbe R提出用约束理论确定生产优先权的方法，从而建立了基于约束理论的订单选取模型[3]。李娟等提出将外包、声誉损失与订单选择结合起来，研究在企业利润最大化下对订单的选择性接受问题[4]。

订单排序问题的研究通常是在假设已经确定订单的情况下进行的。由于不同订单的完工时间存在差异，考虑到延迟惩罚成本及机器空闲浪费等因素，订单过多或过少也会影响企业的服务水平和利润。宋华明等研究了流水线平衡与产品排序对流水线完工时间的交互影响，提出了一种协同进化算法，优化混合装配流水线完工时间[5]。廖朝辉等研究了基于层次分析法和模糊综合评价的订单优先等级策略，从交货期指标、订单金额、客户重要性等方面确定评价指标，用层次分析法确定权重，以评语等级比例确定模糊评价矩阵，最后以各等级分数的总和作为订单优先级别的依据[6]。

传统的订单选择问题把生产排序和订单选择分开进行考虑，订单选择的优劣完全依赖生产排序的结果。而在流程型生产中，生产排序直接影响订单选择决策，而订单选择又反过来影响生产排序。许绍云等（2014）将不被选择投放的订单视为推迟投放，考虑推迟投放加上机器闲置以及订单拖期的总惩罚成本，研究了流水车间的订单投放问题，通过建立以最小化总惩罚成本为目标的整数规划模型，对单个计划期内的订单投放和订单排序进行联合决策[7]。本文通过分析流程型生产订单选择与生产排序之间的相互关系，在Slotnick模型的基础上提出一个以最大化利润为目标的新模型，同时考虑订单排序和订单选择。

1 Slotnick模型

假设企业产能有限，订单存在延迟惩罚，以利润最大化为目标，企业选择部分订单进行生产。假设n个订单按照i=1…n顺序进行了排序（订单i的处理顺序优先于订单i+1）；Q表示按时完成订单i将获得的收益；p表示订单j的处理时间；d表示订单i的最迟交货期限；w表示订单i的延期处罚权重；C表示选择并完成订单i的时间。

模型如下：

maxxQ-wC-d （1）

st. （2）

模型设定了一个0-1变量x，x=1时表示接受订单，x=0时表示放弃该订单。模型以最大化利润为目标，表示当订单的完工时间超过了该订单要求的交货期时受到的惩罚。如果提前完成订单，对企业不产生影响，即没有任何意义。

Slotnick模型在不同的订单排序规则下，得到的订单选择问题的最优解不同。例如有以下4个订单，按序到达，每个订单的利润Q、在机器上的处理时间批p、延期交货处罚权重w及交货期d的数值如表1所示。

我们以先到先得（FCFS）排序原则进行排序，订单顺序为1-2-3-4，Slotnick模型给出的最优解为选择订单顺序1-2-3，放弃订单4，利润值为64，订单3导致延期处罚4个单位，实现净利润为60。以最短工作时间（SPT）排序原则进行排序，订单顺序为2-3-1-4，Slotnick模型给出的最优解为选择订单顺序2-3-1，放弃订单4，由于没有延期处罚，实现净利润值为64。

Slotnick订单模型将订单选择与生产排序分开考虑，在不同的订单排序规则下，得到的最优订单选择不同，不能保证得到整个问题的全局最优解，因此研究同时考虑生产排序和订单选择，提出一个求解整个问题全局最优解的模型具有理论和现实意义。

2 新的订单选择模型

在流程型生产中，生产排序直接影响订单选择决策，而订单选择又反过来影响生产排序。基于Slotnick模型，通过分析流程型生产订单选择与生产排序之间的相互关系，提出一个新的订单选择模型，同时考虑订单排序和订单选择。

2.1 基本假设

（1）假设产品生产的产能有限，考虑单个计划期内的订单选择与排序。

（2）假设企业在选定的某个时刻（定为0时刻）接到所有订单并根据已经收到的订单的具体信息（包括每个订单的处理时间，到期时间，利润，延期处罚权重）进行选择并处理。

（3）假设订单从生产到处理完成过程中，没有库存，不考虑库存成本。

2.2 模型描述

假设订单j，j∈1，2，…，n，n为订单总数；Q表示订单j的收益；p表示订单j的处理时间；d表示订单j的交货期；w表示订单j的权重；C表示选择并完成订单j的时间；S表示第i顺序生产的订单的完成时间；x为决策变量，若x=1表示选择订单j且将其放在第i顺序加工处理，否则x取0。对每个订单j来说，如果不接受，则订单不存在排序问题，如果接受，则必须将订单安排在一个顺序上生产。即每个订单至多被允许排在一个顺序上生产，约束条件为∑x≤1， j=1，2，…，n。同样，对每个顺序i来说，至多允许在此顺序上生产一个订单，考虑约束条件∑x≤1， i=1，2，…，n。对上述2个约束条件，若其同时等于1，表示选择所有订单并排序，这类似于指派问题。当2个约束条件不同时为1时，表示只选择部分订单进行排产。通常企业以利润最大化为目标，并且由于自身产能有限，一般不会选择所有订单，而只是选择部分订单进行排产。

优化模型如下：

Max∑∑xQ-wC-d （3）

st. （4）

该模型仍然以利润最大化为最优目标，但不再是在已知生产排序的情况下单独考虑订单选择，而是同时集中考虑订单选择与生产排序。设定变量S，等式S=S+∑px表示第i顺序生产的订单完成时间等于第i-1顺序生产的订单完成时间与第i顺序生产的订单处理时间之和，C表示完成订单j的时间。

2.3 模型验证及分析

为了验证模型的有效性，取上述4个订单的算例进行分析和求解。4个订单共有64种排列组合方式，通过计算比较每种排列组合方式实现的利润大小，可知当选择订单1、2、4，放弃订单3，并按照订单4-2-1顺序排产时，利润最大为79。调用Lingo软件对新建的模型进行运行求解，得到模型最优解，如表2所示。

表2显示，通过构建的模型得到的最优解为选择订单1、2、4，放弃订单3，订单依次按照4-2-1的顺序排产，实现的利润值为79，与上述计算得到的结果一致。由此证明此模型是有效可行的。

2.4 模型复杂度分析

本文构建的模型为非线性0-1规划模型，随着订单数的增加，模型计算量呈指数增长。为了测试该模型的运行效率，随机产生5组订单进行计算（订单数n分别取4、8、12、16、20），计算机处理器频率2.20GHZ，内存2.0G，通过Lingo逐一运行，每组运行10次，得到模型计算效率如表3，单位为秒。

由表3可知，在订单规模不超过16个的情况下，流程型生产企业的订单选择和排序问题可通过本文建立的模型在一定的有效时间内得到最优解。而且从前3组实验结果可以看出，模型的计算时间随订单数的增加大致上呈指数增长，这与非线性整数规划的求解理论相一致，研究同时考虑订单选择和生产排序的联合优化问题属于NP-hard问题。

3 结束语

传统的订单选择问题把生产排序和订单选择分开进行考虑，订单选择的优劣依赖于生产排序的结果。本文基于Slotnick订单选择模型，通过分析订单选择与生产排序之间的相互关系，研究了同时考虑订单选择与生产排序的流程型生产企业的订单选择问题，提出一个以利润最大化为目标的非线性0-1规划模型。由于模型中0-1变量数量的增加，模型的计算复杂性提高，利用Lingo11.0对模型进行求解检验。结果表明，本模型在订单规模较小（不超过16个）时，可在有效时间内得到最优解，对于大规模订单，则需要相对较长的时间。此模型建立在一般性问题条件下，对大规模订单求解问题有一定的限制性，后续还需要提出效率更高的求解非线性0-1规划问题的算法，对大规模订单问题进行求解分析。

参考文献：

[1] Susan A. Slotnick， Thomas E. Morton. Order Acceptance with Weighted Tardiness[J]. Computers & Operations Research， 2007，34：3029-3042.

[2] W Wester， J Wijgaard， M Zijm. Order Acceptance Strategies in a Production-to-Order Environment with Setup Times and Due—dates[J]. International Journal of Producction Research， 1992，30（6）：1313-1326.

[3] 张人千. 考虑时间序列关联的订单选择决策比较研究[J]. 管理科学学报，2009，12（3）：44-54.

[4] 李娟，王军. 基于外包的流程型生产订单选择问题研究[J]. 物流科技，2014，37（2）：68-70.

[5] 宋华明，马士华. 混合装配流水线上最小makespan的协同优化[J]. 系统工程理论与实践，2007，27（2）：153-160.

[6] 廖朝辉，胡盛强，张毕西，等. 基于层次分析法和模糊综合评价的订单优先等级策略[J]. 科技管理研究，2011，31（24）：191-194.

[7] 许绍云，李铁克，王柏林，等. 修复式约束满足算法求解流水车间订单投放问题[J]. 制造业自动化，2014（3）：1-6.