《典型优化问题的遗传算法求解—10调度问题》由会员分享，可在线阅读，更多相关《典型优化问题的遗传算法求解—10调度问题（105页珍藏版）》请在金锄头文库上搜索。
1、典型优化问题的模型与算法-R031典型问题调度问题调度问题(Scheduling Problems)东北大学 系统工程研究所东北大学 系统工程研究所2014.09调度问题一类典型的优化问题。一类典型的优化问题。 广义地讲，调度问题考虑的是：广义地讲，调度问题考虑的是： 随着随着时间的变化时间的变化，如何，如何调度有限的资源调度有限的资源在在执行任务执行任务的同时的同时满足 特定约束满足 特定约束。 资源可能在本质上是很不相同的资源可能在本质上是很不相同的: 人力、人力、 金钱、金钱、 机器、机器、 工具、工具、 材料、材料、 能源等等。能源等等。 任务也可以有不同的解释，从制造系统的机器划分到
2、计算机系 统的信息处理。一项任务通常可以用下面的因素来表示特征任务也可以有不同的解释，从制造系统的机器划分到计算机系 统的信息处理。一项任务通常可以用下面的因素来表示特征: 完成时间、完成时间、 预期时间、预期时间、 相对紧急权重、相对紧急权重、 处理时间处理时间 资源消耗。资源消耗。 同时，一组反映任务之间先后同时，一组反映任务之间先后约束的结构约束的结构可以用不同的方式定 义。另外还可以考虑可以用不同的方式定 义。另外还可以考虑度量调度性能好坏的不同判据度量调度性能好坏的不同判据.典型优化问题的模型与算法-R032典型优化问题的模型与算法-R033特点调度问题几乎在现实环境调度问题几乎在现
3、实环境(特别是工业工程领 域特别是工业工程领 域)中中无处不在无处不在。许多制造工业提出的调度问题从本质上讲非常 复杂，许多制造工业提出的调度问题从本质上讲非常 复杂，难以用传统优化方法求解难以用传统优化方法求解。通常这些难于求解的问题都表示为满足非常复 杂约束的通常这些难于求解的问题都表示为满足非常复 杂约束的组合优化问题组合优化问题。这些问题这些问题带有有限数量的可行解带有有限数量的可行解。这些问题属于这些问题属于NP难的问题难的问题。经典调度问题的分类流水车间调度问题流水车间调度问题作业车间调度问题作业车间调度问题机器调度问题机器调度问题扩展调度问题：扩展调度问题：群体作业调度群体作业调
4、度资源约束的项目调度资源约束的项目调度多处理器调度多处理器调度车辆与路径调度车辆与路径调度典型优化问题的模型与算法-R034制造业生产模式按生产计划方式分类按生产计划方式分类面向订单生产，面向订单生产，强调准时高效，客户订单到达后才开始组织生产。强调准时高效，客户订单到达后才开始组织生产。面向库存生产，面向库存生产，在客户订单到达之前就已开始生产，生产计划以库存为 基础。在客户订单到达之前就已开始生产，生产计划以库存为 基础。混合生产模式，混合生产模式，一方面根据预测，保留较大的库存，另一方面以一定的 实时生产能力来满足高度客户化的订单需求。一方面根据预测，保留较大的库存，另一方面以一定的 实
5、时生产能力来满足高度客户化的订单需求。典型优化问题的模型与算法-R035制造业生产模式按生产过程的工艺流程特征分类按生产过程的工艺流程特征分类 离散式生产：离散式生产：产品是由离散的零部件装配而成，零部件以各自的工艺过程 通过各个生产环节，物料运动呈离散状态。产品是由离散的零部件装配而成，零部件以各自的工艺过程 通过各个生产环节，物料运动呈离散状态。例如属于生产资料生产的机械、电子设备制造业，属于生活 资料生产的机电整合消费产品制造业。例如属于生产资料生产的机械、电子设备制造业，属于生活 资料生产的机电整合消费产品制造业。 离散型制造企业的生产方式多为单件、小批量、多品种离散型制造企业的生产方
6、式多为单件、小批量、多品种 流程式生产：流程式生产：在生产过程中，物料均匀、连续地按一定工艺顺序运动，生 产流程具有连续性的特点和要求在生产过程中，物料均匀、连续地按一定工艺顺序运动，生 产流程具有连续性的特点和要求 例如冶炼、化工、酿造等例如冶炼、化工、酿造等 混合流程式生产：混合流程式生产：这是一种既具有流程式生产特征，又具有离散式生产特征的 复杂生产方式，其生产过程并不完全是一个自动生产线。其 典型特征是生产分阶段进行，设备按阶段使用，在不同的生 产阶段遵循不同的生产方式，一般产品不可数，加工过程是 间歇式的。这是一种既具有流程式生产特征，又具有离散式生产特征的 复杂生产方式，其生产过程
7、并不完全是一个自动生产线。其 典型特征是生产分阶段进行，设备按阶段使用，在不同的生 产阶段遵循不同的生产方式，一般产品不可数，加工过程是 间歇式的。典型优化问题的模型与算法-R036Flaw Shop和和Job Shop调度问题是最典型和最重要的两 种车间调度问题。调度问题是最典型和最重要的两 种车间调度问题。 车间调度问题具有以下几个特点车间调度问题具有以下几个特点: 复杂性复杂性: 由于生产车间中工件、机器、缓存及搬运系统之间相互影响、相 互作用、每个作业又要考虑它的加工时间、操作顺序、交货期等 ，因而相当复杂。由于生产车间中工件、机器、缓存及搬运系统之间相互影响、相 互作用、每个作业又要
8、考虑它的加工时间、操作顺序、交货期等 ，因而相当复杂。 动态随机性动态随机性: 在实际的生产调度系统中存在很多随机的和不确定的因素，比如 作业到达时间的不确定性、设备的损坏在实际的生产调度系统中存在很多随机的和不确定的因素，比如 作业到达时间的不确定性、设备的损坏/修复、作业交货期的改变 、紧急定单等。修复、作业交货期的改变 、紧急定单等。 多目标性多目标性: 实际的计划调度往往是多目标的。生产调度的性能指标可以是成 本最低、库存费最少、生产周期最短、生产切换最少、设备利用 率最高、最短的延迟，最小的提前或者拖期惩罚等。这种多目标 性导致调度的复杂性和计算量急剧增加。实际的计划调度往往是多目标
9、的。生产调度的性能指标可以是成 本最低、库存费最少、生产周期最短、生产切换最少、设备利用 率最高、最短的延迟，最小的提前或者拖期惩罚等。这种多目标 性导致调度的复杂性和计算量急剧增加。 多约束性多约束性: 生产车间中资源的数量、缓存的数量、工件的加工时间和加工顺 序都是约束。此外还有一些人为的约束，如要求各机器上的负荷 平衡等等。生产车间中资源的数量、缓存的数量、工件的加工时间和加工顺 序都是约束。此外还有一些人为的约束，如要求各机器上的负荷 平衡等等。车间调度问题的几个特点典型优化问题的模型与算法-R037典型优化问题的模型与算法-R038典型问题流水车间调度问题流水车间调度问题(Flow-
10、shop Scheduling Problems)问题描述一般描述一般描述n 个工件要在个工件要在 m 台机器上加工，台机器上加工，每个工件需要经过每个工件需要经过 m 道工序，每道工序要求不同 的机器。道工序，每道工序要求不同 的机器。n 个工件在个工件在 m 台机器上的加工顺序相同。台机器上的加工顺序相同。工件工件 i 在机器在机器 j 上的加工时间是给定的，设为上的加工时间是给定的，设为 tij (i=1,n; j=1,., m)。问题的目标问题的目标求求 n 个工件在每台机器上最优的加工顺序，使最 大流程时间达到最小。个工件在每台机器上最优的加工顺序，使最 大流程时间达到最小。典型优化
11、问题的模型与算法-R039问题描述对该问题常常作如下假设对该问题常常作如下假设:每个工件在机器上的加工顺序是每个工件在机器上的加工顺序是: 1,2,m;每台机器同时只能加工一个工件每台机器同时只能加工一个工件;一个工件不能同时在不同的机器上加工一个工件不能同时在不同的机器上加工;工序不能预订工序不能预订;工序的准备时间与顺序无关，且包含在加工时间 中工序的准备时间与顺序无关，且包含在加工时间 中;工件在每台机器上的加工顺序相同，且是确定的。工件在每台机器上的加工顺序相同，且是确定的。典型优化问题的模型与算法-R0310三类FSP问题确定型流水车间问题确定型流水车间问题假定工件的加工时间是已知的
12、确定量假定工件的加工时间是已知的确定量随机型流水车间问题随机型流水车间问题加工时间按照一定的概率分布而变化加工时间按照一定的概率分布而变化模糊型流水车间问题模糊型流水车间问题每个工件的模糊交货期表示为决策者对工件完成 时间的满意度每个工件的模糊交货期表示为决策者对工件完成 时间的满意度典型优化问题的模型与算法-R0311实际调度问题往往更加复杂，例如：实际调度问题往往更加复杂，例如：通常要满足一定的约束条件通常要满足一定的约束条件顾客的交货时间、顾客的交货时间、资源约束、资源约束、工艺约束等工艺约束等性能指标通常可以分成多种类型性能指标通常可以分成多种类型最大能力指标最大能力指标最大生产率、最
13、大生产率、最短生产周期最短生产周期等等成本指标成本指标最大利润、最小化运行费用、最小投资、最大收益等最大利润、最小化运行费用、最小投资、最大收益等客户满意度指标客户满意度指标最短的延迟，最小提前或者拖后惩罚等最短的延迟，最小提前或者拖后惩罚等实际调度问题典型优化问题的模型与算法-R0312确定型确定型FSP的一个实例：的一个实例：4个工件、个工件、2台机器台机器工件顺序：工件顺序：j3, j2, j4, j1.调度调度S如下：如下： S = (t31(0-3), t21(3-4), t41(4-10), t11(10-15), t32(3-9), t22(9-11), t42(11-16),
14、t12(16-20)实例Job i1234ti 15136ti 24265M1M2time4-job and 2-machine problemMakespan : 20 (units)j3j2j4j1j3j2j4j11234567891011121314151617181920典型优化问题的模型与算法-R0313墙纸行业生产调度问题墙纸行业生产调度问题装饰布企业车间生产调度装饰布企业车间生产调度飞机维修调度问题飞机维修调度问题化工涂料生产的配料及调度化工涂料生产的配料及调度集装箱码头装卸作业的调度问题集装箱码头装卸作业的调度问题汽车总装车间调度汽车总装车间调度柔性流水车间调度问题柔性流水车间
15、调度问题冷轧厂热处理车间冷卷热处理生产调度问题冷轧厂热处理车间冷卷热处理生产调度问题炼钢炼钢-连铸浇次组合与排序连铸浇次组合与排序石油、化工等流程工业石油、化工等流程工业应用典型优化问题的模型与算法-R0314两台机器FSP的最优调度Johnson规则：规则： 最优调度中工件最优调度中工件 i 排在工件排在工件 j 之前，之前， 如果如果:最优顺序可以直接利用这个结果通过两个工序之间的 检查来构造。最优顺序可以直接利用这个结果通过两个工序之间的 检查来构造。 令令 I 表示工件序列，表示工件序列，S 表示顺序，表示顺序，Johnson算法可以描述为：算法可以描述为：,min,min1221ji
16、jittttinput: ti1, ti2, job list I, output: best schedule S step 1: Let U = i| ti10, i0 是与每个工件相对应的单位提前和单位拖期惩罚。是与每个工件相对应的单位提前和单位拖期惩罚。对于一个给定的调度对于一个给定的调度 ，基本，基本E/T调度问题可以写成：调度问题可以写成：惩罚可以采用不同的度量方法，可以对工件给出相同或不同的惩罚惩罚可以采用不同的度量方法，可以对工件给出相同或不同的惩罚交货期可以是给定的，或者与工件顺序同时优化；交货期可以是给定的，或者与工件顺序同时优化；最简单的模型是考虑所有工件有共同的交货期，更一般的模型是允许 有不同的交货期。最简单的模型是考虑所有工件有共同的交货期，更一般的模型是允许 有不同的交货期。即
