典型优化问题的遗传算法求解-10调度问题

《典型优化问题的遗传算法求解-10调度问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、典型问题调度问题(SchedulingProblems)东北大学系统工程研究所2014.09典型优化问题的模型与算法-R031调度问题一类典型的优化问题。广义地讲，调度问题考虑的是：随着时间的变化，如何调度有限的资源在执行任务的同时满足特定约束。资源可能在本质上是很不相同的:人力、金钱、机器、工具、材料、能源等等。任务也可以有不同的解释，从制造系统的机器划分到计算机系统的信息处理。一项任务通常可以用下面的因素来表示特征:完成时间、预期时间、相对紧急权重、处理时间资源消耗。同时，一组反映任务之间先后约束的结构可以用不同的方式定义。另外还可以考

2、虑度量调度性能好坏的不同判据.典型优化问题的模型与算法-R032特点调度问题几乎在现实环境(特别是工业工程领域)中无处不在。许多制造工业提出的调度问题从本质上讲非常复杂，难以用传统优化方法求解。通常这些难于求解的问题都表示为满足非常复杂约束的组合优化问题。这些问题带有有限数量的可行解。这些问题属于NP—难的问题。典型优化问题的模型与算法-R033经典调度问题的分类流水车间调度问题作业车间调度问题机器调度问题扩展调度问题：群体作业调度资源约束的项目调度多处理器调度车辆与路径调度……典型优化问题的模型与算法-R034制造业生产模式按生产计划方式分类

3、面向订单生产，强调准时高效，客户订单到达后才开始组织生产。面向库存生产，在客户订单到达之前就已开始生产，生产计划以库存为基础。混合生产模式，一方面根据预测，保留较大的库存，另一方面以一定的实时生产能力来满足高度客户化的订单需求。典型优化问题的模型与算法-R035制造业生产模式按生产过程的工艺流程特征分类离散式生产：产品是由离散的零部件装配而成，零部件以各自的工艺过程通过各个生产环节，物料运动呈离散状态。例如属于生产资料生产的机械、电子设备制造业，属于生活资料生产的机电整合消费产品制造业。离散型制造企业的生产方式多为单件、小批量、多品种流程式生产：在

4、生产过程中，物料均匀、连续地按一定工艺顺序运动，生产流程具有连续性的特点和要求例如冶炼、化工、酿造等混合流程式生产：这是一种既具有流程式生产特征，又具有离散式生产特征的复杂生产方式，其生产过程并不完全是一个自动生产线。其典型特征是生产分阶段进行，设备按阶段使用，在不同的生产阶段遵循不同的生产方式，一般产品不可数，加工过程是间歇式的。典型优化问题的模型与算法-R036车间调度问题的几个特点FlawShop和JobShop调度问题是最典型和最重要的两种车间调度问题。车间调度问题具有以下几个特点:复杂性:由于生产车间中工件、机器、缓存及搬运系统之间相互影响、相互作用

5、、每个作业又要考虑它的加工时间、操作顺序、交货期等，因而相当复杂。动态随机性:在实际的生产调度系统中存在很多随机的和不确定的因素，比如作业到达时间的不确定性、设备的损坏/修复、作业交货期的改变、紧急定单等。多目标性:实际的计划调度往往是多目标的。生产调度的性能指标可以是成本最低、库存费最少、生产周期最短、生产切换最少、设备利用率最高、最短的延迟，最小的提前或者拖期惩罚等。这种多目标性导致调度的复杂性和计算量急剧增加。多约束性:生产车间中资源的数量、缓存的数量、工件的加工时间和加工顺序都是约束。此外还有一些人为的约束，如要求各机器上的负荷平衡等等。典型优化问题的模

6、型与算法-R037典型问题流水车间调度问题(Flow-shopSchedulingProblems)典型优化问题的模型与算法-R038问题描述一般描述n个工件要在m台机器上加工，每个工件需要经过m道工序，每道工序要求不同的机器。n个工件在m台机器上的加工顺序相同。工件i在机器j上的加工时间是给定的，设为tij(i=1,…,n;j=1,...,m)。问题的目标求n个工件在每台机器上最优的加工顺序，使最大流程时间达到最小。典型优化问题的模型与算法-R039问题描述对该问题常常作如下假设:每个工件在机器上的加工顺序是:1,2,…,m;每台机器同时只能加工一个工

7、件;一个工件不能同时在不同的机器上加工;工序不能预订;工序的准备时间与顺序无关，且包含在加工时间中;工件在每台机器上的加工顺序相同，且是确定的。典型优化问题的模型与算法-R0310三类FSP问题确定型流水车间问题假定工件的加工时间是已知的确定量随机型流水车间问题加工时间按照一定的概率分布而变化模糊型流水车间问题每个工件的模糊交货期表示为决策者对工件完成时间的满意度典型优化问题的模型与算法-R0311实际调度问题实际调度问题往往更加复杂，例如：通常要满足一定的约束条件顾客的交货时间、资源约