置换流水车间调度问题的MATLAB求解.doc

物流运筹实务课程设计题目:置换流水车间调度问题的 MATLAB 求解置换流水车间调度问题的 MATLAB 求解目录一、前言……………………………………………………………………… 5 二、问题描述………………………………………………………………… 6 三、算法设计………………………………………………………………… 7 四、实验结果……………………………………………………………… 15 摘要自从 Johnson 1954 。安排合理有效的生产调度是生产活动能井然有序开展,生产资源得到最佳配置,运作过程简明流畅的有力保证。流水车间调度问题是许多实际流水线生产调度问题的简化模型。它无论是在离散制造工业还是在流程工业中都具有广泛的应用。因此,对进行研究具有重要的理论意义和工程价值。流水线调度问题中一个非常典型的问题,而置换流水线调度问题作为 FSP 问题的子问题,是一个著名的组合优化问题。该问题是一个典型的 NP难问题,也是生产管理的核心内容。随着生产规模的扩大,流水线调度问题的优化对提高资源利用率的作用越来越大,因此对其研究具有重要的理论和现实意义。关键字:流水车间,单件小批量生产, jsp 模型, Matlab 前言企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中, 所以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地位。车间生产计划与控制的核心理论是调度理论。车间调度问题是一类重要的组合优化问题。为适应订货式、多品种、小批量生产的需要,引进了置换流水车间调度概念。在置换流水车间调度优化后,可以避免或大大减少流程工作时间、提高生产效率。因此,研究成组技术下车间调度问题是很有必要的。生产调度,即对生产过程进行作业计划,是整个个先进生产制造系统实现管理技术、优化技术、白动化与计算机技术发展的核心。置换流水车间调度问题是许多实际生产调度问题的简化模型。生产计划与调度直接关系着企业的产出效率和生产成本,有效的计划与调度算法能最大限度地提高企业的效益。调度问题是组合优化问题,属于 NP问题,难以用常规力一法求解。随着制造业的快速发展,大规模定制生产、全球化制造等思想的提出,使车间调度问题呈现出以下的新特点:约束条件多,时间复杂度高,空问复杂度高。这将导致在许多情况下,求解所建立的数学模型的快速性无法满足,如果采用适度线形化处理之后求解,将会因简化太多而使结果严承失真。所以需选择功能强大的数值计算工具来实现这一问题的求解。 MATLAB 恰好提供了这样的平台。 MATLAB 是一个高度集成的系统,集科学计算、图像处理、声音处理于一体,具有极高的编程效率。典型 JSP 模型分析与 Matlab 的应用结合使流水车间调度问题迎刃而解。最大完工时间是生产调度中最常用的性能度量指标之一,最大完工时间越短,则说明产品总的生产周期越短,生产能力越大;此类调度问题的优化研究有助于提高企业的生产效率与资源利用率。一、问题描述流水车间调度问题通常可以描述为 n 个工件要在 m 台机器上加工,每个工件有 m 道工序,每道工序都要在不同的机器上加工,所有工件的加工顺序都相同,问题的目标是确定每台机器上工件的加工顺序及开工时间,使得特定的性能指标最优。置换流水车间调度问题 PFSP 是对流水车间调度问题的进一步约束,即约定每台机器上所有工件的加工顺序相同,其解空间的规模为!n ,远远小于流水车间调度问题的规模( !) mn 。本次课程实验主要研究 PFSP 中的最小化最大完工时间问题,利用三元组表示法( max F prmu C )求解 Carlier (1978) 提出的 8个算例、以及 Reeves (1995) 提出的 21 个算。由于三台机器以上的调度问题被证明是 NP 难问题,对于大规模的调度,至今仍未出现求解最优的方法,常常采用启发式算法来求解近优解。本案例主要采用 instance car 2进行求解。案例:某产品,需要经过 4 道工序对 13 个工件进行加工,这 13 个工件的生产流程是一样的。加工时间表见下: 表4-3 某产品加工时间表 12345678910111213 t j1789 630 214 573 218 658 214 207 785 696 532 12457 工件号加工时间 t j2930 214 257 896 532 142 547 865 321 124 12345 678 t j321475 320 124 752 147 532 145 763 214 257 854 123 t j4320 142 753 214 5