需按期交货的单件订单选择决策和加工调度问题研究(2)
此外，近50年来，生产调度问题也一直是人们研究的热点，60-70年代建立了调度理论的主体(经典调度理论)哪，它是许多实际调度问题的简化模型。相对经典作业车间调度而言，现实生产中有配合工序约束的车间调度问题更加复杂。配合加工是为保证关键部件定位或加工精度将工件装配在一起加工的方法。目前(50～80)％企业都用到配合加工，常用在精密和超精密加工中，尤其是在模具生产加工中大量使用。故研究配合加工生产车间调度问题具有十分重要的现实意义。
对配合加工的生产调度问题研究上，学者对这类问题研究还比较少，主要采用了启发式规则算法M和一些智能算法嘲，然而这些算法都没有考虑工件交货期。针对该种加工车间，在经典调度模型的基础上，综合考虑这类车间的作业特性、交货期和配合加工的工艺约束等，基于生产调度的各种规则，归纳出配合加工启发式倒排调度规则，建直调度模型并对其求解，且用实例验证和比较分析了调度效果。
Job -Shop 问题（ JSP） 是诸多的关于加工调度的问题中较为典型的一类，它是许多实际问题的简化模型。 一般的JSP可以描述为：
n个工件在m 台机床上加工,每一时刻每台机床最多加工一个工件 一个工件最多在一台机床上加工,一台机床上加工的过程不能间断,机床间缓冲区容量无限,工件j 在机床i上的加工时间dij已知，每一个工件在各台机床上的加工顺序已知，确定每个工件的加工次序使加工性能指标最优。如果每个工件在各台机床上的加工顺序相同。这种JSP就是一般的FloW-Shop问题（FSP）。如果每台机床上各个工件的加工顺序都相同，这种FSP就是置换FloW-Shop 问题（PFSP）本文中加工性能指标是加工完所有工件的时间。
本文中所研究的订单选择问题中的加工调度问题，均可用（JSP）问题的求解方式求解。
在本文中将分三步对订单选择问题进行研究：（1）单生产线单节点的订单选择问题。这是订单选择问题中最为简单基础的模型。（2）多生产线单节点的订单选择问题。此模型考虑到了在实际中许多工厂并非只有一条生产线，相比于单生产线更加接近于实际情况。（3）多节点的订单选择问题。相对于单节点的订单选择问题，此问题的研究考虑到了更多的因素，具有更强的实用性。（在本文中不考虑由延迟交货而导致的惩罚因素，所以在本文中工厂所接受的订单直接根据订单的交货时间排序）
本文所研究的问题由浅入深，由最简单的的单生产线单节点的订单选择问题到多节点的订单选择问题，越来越接近于工厂的实际情况，并且在最后对之前所研究的问题进行对比、分析，进而得出结论。
1.2 研究背景和意义
订单选择问题，最初由Slotnick等人提出，在近10年来得到了广泛的理论研究和实践应用。在此问题的研究中，分枝与界定(Branch and Bound，B＆B)算法被用来快速求解小规模的此类问题，B&B算法通过类似决策树的带有启发式深度搜索的方式来得到较优的近似解。对于大规模的此类问题，Slotnick则建议用启发式算法如退火算法、禁忌搜索、遗传算法来进行近似优化求解。
Ghosh证明这是一个考虑订单排序的O～1整数规划问题，具有NP-hard的计算复杂性，并给出了一种BS(Beam Search，BS)算法来对解空间进行分枝和选优。Alidaee将问题分为排序和选择两部分，运用贪婪式算法(Greedy Method)来进行计算。后来Slotnick还研究过此类问题的多个计划期的订单选择问题，主要是在订单选择时考虑了其未来关联订单的收益影响。
在实践中，订单接受决策和生产计划往往是两个分开的功能，正如我们在一家汽车配件制造厂中所经历到的情形一样。例如，销售部门负责订单接受，而生产部门负责生产计划。销售部门总是希望接受所有的订单，不管是否具备足够的生产能力，因为他们的目标就是销售额。生产部门则希望使产能利用达到最大化，同时尽量减少延迟。管理者在决定是否接受一个订单时，应该平衡考虑该订单所能带来的利润和它对生产资源的影响。因此应将这两方面进行协调以使企业获得最大的收益。
下一篇：关于海信集团江苏渠道冲突探究