山 东 大 学 硕 士 学 位 论 文
分类号：TP39 单位代码：10422
密 级： 学 号：06910470631
硕 士 学 位 论 文
论文题目：不确定条件下Flow Shop调度问题研究
Research of Flow Shop Scheduling Problems Under Uncertainty
作者
鲁 燕
专业
计算机软件与理论
导师
杨公平 副教授
合 作 导 师
2010年 4 月 5 日
原创性声明和关于学位论文使用授权的说明
原 创 性 声 明
本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。
论文作者签名： 日 期：
关于学位论文使用授权的声明
本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。
(保密论文在解密后应遵守此规定)
论文作者签名： 导师签名： 日 期：
目 录
I摘 要
IIIABSTRACT
1第1章 绪 论
课题研究的背景和意义
本文工作
论文组织
3第2章 生产调度问题综述
生产调度问题的描述
生产调度问题的一般描述
生产调度问题的相关概念
生产调度问题的约束条件
生产调度问题的特点
生产调度问题的分类
生产调度问题的研究方法
传统方法
计算智能方法
基于知识的调度方法
13第3章 Flow Shop调度问题及其算法
Flow Shop调度问题描述
Flow Shop调度问题的求解方法
启发式方法
遗传算法
27第4章 基于满意度的不确定条件下Flow Shop调度问题求解方法
生产调度过程中的不确定性
基于满意度的求解方法
模糊交货期下Flow Shop调度问题描述
满意度方法分析及模拟实验
33第5章 存储时间有限型Flow Shop问题提前_拖期调度
引言
问题描述
数学模型
遗传算法实现
编码
初始群的产生
确定适应度函数
选择操作
交叉操作
变异操作
停止准则
实验分析
38第6章 结束语
39参考文献
42致 谢
43攻读学位期间发表的学术论文
TABLE OF CONTENTS
Abstract in chinese I
Abstract in english III
Chapter 1 Introduction 1
background an purpose of study 1
research content 2
Arrangement 2
Chapter 2 Production Review 3
Description of production scheduling problems 4
The general description 4
related concepts……………………………………………………………………..4
constraint condition 5
Features of production scheduling problems 5
Classification of production scheduling problems 7
Research method of production scheduling problems……………………………...9
traditional method 9
computational intelligence 10
scheduling method based on knowledge 11
Chapter 3 Flow shop scheduling problem and the algorithm 13
Dscription of flow shop scheduling problem 13
Solution method of flow shop scheduling problem 14
heuristic method 14
genetic method 16
Chapter 4 The satisfaction method for flow shop scheduling problem with uncertainty 27
Uncertainty in production scheduling 27
The satisfaction method…………………………………………………………….28
Description of flow shop scheduling problem with fuzzy due time 28
The analysis of satisfaction method and simulation 29
Chapter 5 Earliness and tardiness flow shop scheduling problems with finite intermediate storage 33
Introduction 33
description 33
mathematical model 34
Solving the problem with genetic algorithm 34
code design 34
generate the initial group 35
determine the fitness function 35
selection 35
crossing 35
variation 35
terminate rule 35
experimental analysis 35
Chapter 6 Conclution 38
Reference 39
Acknowledge 42
List of published articles 43
摘 要
生产作业调度问题是研究在有限的资源条件下，如何分配资源以满足某个或某些特定的生产指标，并使得生产企业获得最大的经济利益和社会效益。生产调度在企业生产管理中占据至关重要的战略位置。如何分配现有资源以满足特定的生产目标，从而使企业在日趋激烈的市场竞争中处于领先地位，是企业管理的重点内容。因此，生产作业调度问题一直是许多企业如制造业的研究热点。对生产作业调度问题的研究具有重要的理论意义和现实意义。
本文对生产作业调度问题进行了系统阐述，并对其中的Flow shop调度问题重点研究。由于实际生产过程中存在大量的不确定因素，使得由各种确定性模型和方法得到的优化调度性能指标降低甚至不再可行，因此本文在处理生产调度问题的时候，将生产过程中存在的不确定因素作为一项必不可少的条件。论文介绍了生产调度问题中的不确定因素及其分类，对模糊交货期下的Flow Shop调度问题进行阐述。
生产作业调度问题的研究方法历经由简单到复杂的过程。这些方法从不同程度上表述了具体生产环境中的复杂的、多目标、动态的调度问题的一种抽象和简化。而评估一个调度算法的主要标准是其优化效果的满意度。调度优化算法传统上主要集中于数学规划、简单的规则等方法。近几十年来，关于遗传算法、模拟退火算法、神经网络算法以及模糊逻辑等方法的研究十分活跃，已成为生产作业调度问题研究的热点之一。作为生产调度领域的重要研究方法，遗传算法通过模拟达尔文“优胜劣汰、适者生存”的激励原理以及模拟孟德尔遗传变异理论在迭代过程中的作用，实现了随机优化与有效搜索。本文重点研究遗传算法的基本思想和流程及其参数设计，并将其应用在Flow Shop调度问题的算法研究中。
论文以不确定条件下生产调度问题算法研究为目的，针对Flow Shop调度问题进行研究，研究的一个侧重点是中间存储时间有限型Flow Shop的提前_拖期调度问题。随着流程工业中准时制的发展，企业所追求的目标是尽可能极大化用户的满意水平，使企业所承受的提前_拖期惩罚达到最低目标。论文给出一种解决Flow Shop调度问题的满意度方法。另外由于产品在加工过程中存在不稳定性，所以产品在两个生产单元之间的储罐中的存储时间只能为一个有限值。本文研究了在处理时间不确定的条件下，带不同交货期窗口的存储时间有限型Flow Shop调度问题。采用三角模糊数描述处理时间的不确定性，使用自然数编码方法，随机产生初始种群，以惩罚数的期望值的倒数作为适应度目标函数值，再利用遗传算法中的选择、交叉和变异算子进行求解。根据实验结果证明本文所采用的研究方法是有效的。
关键词：Flow Shop调度；不确定条件；满意度；提前_拖期调度
ABSTRACT
Production scheduling problems is about study of how to allocate resource to meet one or more production targets and allows manufacturers to obtain the maximum economic benefit and social benefit with the conditions of finite resources. Production scheduling occupy a strategic position of importance in production management in the manufacturers. It is the most important thing in management of the manufacturers that how to allocate the available resources to meet the specific production targets in order to keep in lead in the increasingly fierce market competition. Therefore production scheduling problem has been the research focus for many enterprises such as manufacturers all along. The study of production scheduling problem has important theoretical significance and practical significance.
The thesis carries out systematically expounded of the production scheduling problems, and it gives most importance to the research of the Flow Shop scheduling problem. There is so much uncertainty in real production which make the optimal scheduling performance no longer feasible with certainty model and certainty method, so this paper takes the uncertainty in real production as an indispensable condition when resolving production problem. Next is the meaning and classification of the uncertainty in production scheduling problem and the description of Flow Shop scheduling problem under fuzzy due date.
The research methods of production scheduling problems experienced a process from simple to complex. Those methods explains the abstraction and simplification of complex, multi-objective, dynamic scheduling problems in specific production environment from different level. And the main criteria to evaluate a scheduling algorithm is the satisfaction of effect of optimization. Traditionally scheduling optimization method mainly concentrate on mathematical programming, simple rule and so on. In the relate decades, the studies of genetic algorithm, simulated annealing algorithm, neural network algorithm and fuzzy logic has been very active, and these studies has become one area of the scheduling research hotspot. As an important research method, the genetic algorithm realizes random optimization and effective researching by simulating Darwinian principle of the survival of the fittest and the function in the iteration of Mender’s genetic variation, and it has been a most important method in production research field. The main idea and procedure and the design of the parameters about the algorithm is given in the paper, and it is used to research the Flow Shop scheduling problem.
The paper aims to research the production scheduling algorithm with uncertain product condition and focuses on the Flow Shop scheduling problem, and it gives most importance to the research of earlobes and tardiness flow shop scheduling problems with finite intermediate storage. Along with the development of Just-in-time, the enterprises aim to achieve the maximization customer’s satisfaction level which means the punishment value of earlobes and tardiness flow shop scheduling problems should be as small as it can be. The thesis proposes a method of satisfaction to resolve flow shop scheduling problems. What’s more, because the instability of product in production procedure, it can be stored in the intermediate storage between two production units within a finite period of time. The paper studies flow shop scheduling problems with finite intermediate storage with different delivery windows under uncertainty. It describes the uncertainty of processing time using triangular fuzzy members, and using the natural coding method generates initial population randomly. It takes the reciprocal of expectation value of the punishment as the fitness objective function value, which follows the using of selection, crossing and mutation of the genetic algorithm. According to the experimental result the research method of this paper is effective.
Key words: Flow Shop scheduling; uncertainty; satisfaction; earlobes and tardiness
第1章 绪 论
课题研究的背景和意义
流程工业在我国工业生产中具有非常重要的地位,如何增强企业的竞争力、提高企业的经济效益和社会效益是企业面临的首要问题。Flow shop调度问题研究多个作业在处理设备上以相同路径进行处理，如何安排作业序列来获得最优生产目标的问题。人们对flow shop问题在确定条件下的调度算法进行了大量研究[20]，然而，这些算法很难应用于实际的生产过程中。因为在实际生产中存在许多不确定因素，往往导致生产调度方案无法按预定目标正常执行。目前，对不确定因素主要采用模糊数学方法进行描述，关于模糊处理时间的研究文献有很多，例如[21][22][23]。
流水车间调度问题研究工件在一系列生产设备上以相同顺序进行加工的问题。近来人们对流水车间问题研究给予了很大关注，以提高工业企业的生产效率和经济效益。在实际流水车间生产过程中，工件通常受到释放期限和收工期限的约束，即受工件被允许可以开始生产的期限和必须完成生产过程的期限的限制。比如，一个工件必须在所需原料储备完毕后才可以开始生产，并且收工期限必须保证产品能在用户要求的时间内送达。只有同时满足释放期限和收工期限的工件的加工序列才是可行的。传统的调度算法只处理精确数据，当释放期限和收工期限的约束条件发生细微变化时可能会遗漏可行解。实际情况是工件的释放期限和收工期限可以在一定时间段内浮动，即放宽对两者的约束，这样可以得到满足松弛释放期限和收工期限的具有最大满意度的工件加工序列。
现代准时制生产（Just-In-Time）是21世纪企业的先进生产模式，其目的是以最低成本达到客户最大的满意效果。JIT要求产品按时加工并且交货准时。生产企业只要偏离了客户需求的交货期都要受到惩罚。所以企业要尽量避免提前完工或拖期完工。对提前_拖期调度问题的研究要综合考虑实际生产过程中的不确定因素，还要加入必要的约束条件，即中间存储时间是有限的。遗传算法通过对编码后的字符进行搜索，搜索过程从一组可行解开始迭代到另一组解，GA的可操作性和简单性决定了其能够有效解决中间存储时间有限的flow shop提前_拖期调度问题。
本文工作
本文详细阐述了生产调度问题中的Flow Shop调度问题在不确定条件下的研究。主要工作为：
1.对生产调度的相关知识进行阐述，重点是Flow Shop生产调度问题。
2.以模糊数表示相应的模糊Flow Shop调度问题，以模糊释放期限和模糊收工期限来使得工件的加工过程更加符合实际，并通过满意度计算公式可以获得最佳工件序列。
3.对存储时间有限型Flow Shop问题提前_拖期调度，利用遗传算法给出其求解过程，并给出实验分析。
论文组织
本文的研究内容共分为五章：
第一章绪论，简要介绍本课题研究的背景和意义、本文工作和论文的组织方式。
第二章对生产调度问题进行综述，并介绍了生产调度的特点、分类和研究方法。
第三章给出了Flow Shop调度问题的描述和求解方法，并着重介绍遗传算法；
第四章阐述了模糊Flow Shop调度问题，根据其问题描述及相关模糊数，给出了模糊释放期限和模糊收工期限以及满意度计算方法，最后进行了模拟计算；
第五章研究了存储时间有限型Flow Shop问题提前_拖期调度，给出了遗传算法解决该问题的步骤，并进行了实例仿真。
第六章对本文内容做了总结，并对下一步的工作给予展望。
第2章 生产调度问题综述
随着科学技术的飞速发展、市场竞争的日益激烈、人们消费观念的日趋个性化、生产规模的不断扩大，以及生产过程的日益复杂化，促使生产企业必须采取更加先进合理的管理模式和生产方法，来提高自己的综合实力。只有将简单的、局部的控制和凭经验的管理方式逐步转变为充分利用现有资源优势、高效科学的创造效益才能解决企业的经营管理者们的问题。也就是说，企业要在竞争中取得优势，不仅要靠工艺水平的提高和先进设备的研发、引进，更要靠先进的生产和经营手段[10]。
生产作业调度是研究在有限的资源条件下，如何分配资源以满足某个或某些特定的生产指标,并使得生产企业获得最大的经济利益和社会效益。生产调度是流程企业生产管理的重要组成部分。生产调度是CIMS（computer integrate manufacturing system）和CIPS（computer integrated processing system）的一个重要组成部分，是生产管理的核心和关键技术。每当一组通用的资源，比如劳力、材料、设备，必须配合使用并在统一时间段内制成不同的产品时，就会发生调度问题。系统、全面、合理的生产调度方法不仅有助于提高企业的综合自动化水平，而且可以为企业部门带来显著的经济效益。国外的实施状况表明，单纯提高生产装置的控制水平，寻求局部最优的投入产出比，远远低于提高整体管理水平的投入产出比，因此，生产调度的改进是提高企业综合收益的最有利手段[11]。
在介绍调度问题之前，先来阐明什么是排序问题。排序问题是企业生产以及国防、交通运输和各服务行业中普遍遇到的问题；一般的，凡是需要完成多个不同项目就产生了某一类排序问题[1]。排序问题有时会非常复杂，比如同一台设备上要加工的零件可能有多个，一个零件可能有多道工序要到不同的设备上加工，零件的加工工艺也可能不相同。不同任务在不同的机器上不同的加工顺序得出的结果可能差别很大，怎样安排这种顺序，以期得到最优的结果，就是调度问题。
调度问题通常是指对生产过程的作业计划，譬如工件在机器上的加工顺序、生产批量的划分等[2]。调度问题的“设备”可以指工厂中的机床、维修工人、轮船要停靠的码头等，即表示服务者；调度中的“任务”则是等待加工的零件、待维修的机器、将要停靠码头的轮船等，表示服务对象。一般情况下，“设备”和“任务”都有多个。调度问题及时要确定服务者对服务对象的服务顺序和时间，使目标函数取得最优解。
如图1-1所示，车间调度就是根据加工对象的加工需求，运用不同的调度决策规则，规划系统中的加工事件，并根据系统动态仿真运行的结果或者优化结果形成最佳的生产加工顺序，同时实现设备集和任务集的合理最优化结合[4]。
图 2-1生产调度问题的定义
下面将介绍生产调度问题的描述、生产调度问题的分类及其研究方法。
生产调度问题的描述
本小节给出生产调度问题的一般描述，其中的符号作为本文研究问题的统一符号。给出的相关概念以使问题的阐述更加明晰；明确生产调度问题中的约束条件是理解本文研究问题的重要条件。
生产调度问题的一般描述
生产调度问题一般可以描述为：个工件(job)在台机器(machine)上加工，工件在机器上的加工叫做一个工序或操作(operation)，用来表示，其相应的加工时间(processing time)用来表示。一个调度就是在一定时间内分配各工件在机器上的加工时间。
生产调度问题的相关概念
①加工任务，是一组等待调度来进行加工的工件或原材料，有时称为产品或任务。
②机器，是执行加工任务的生产设备或生产单元，每台机器都有生产能力约束。
③时间参数，是与加工人物或及其有关的各种时间参数，如加工任务的准备时间、等待时间、完工时间、中间储罐存储时间、交货期等。
④目标函数性能指标，如完工时间目标函数等。
⑤控制参数，与物料供应和投入有关的各种参数，如物料供应的限制约束、物料投入生产的时间、地点和数量等。
⑥调度规则，是指一组控制生产过程的规则，如各种优先规则、中间存储策略和生产代价调节规则等。
⑦调度算法，是指用数学的语言来表达调度问题的要求，在给定时间参数和调度规则下确定各种控制参数，使得一种或多种性能指标最优。
生产调度问题的约束条件
①每台机器在每个时刻只能加工一个工件。
②一个作业不能同时在不同机器上加工。
③一个作业在一台机器上的加工不允许被中断。
④假定机器在零时刻即可开始工作，没有准备时间。
⑤工件在工序之间可以等待，机器在工件为到达之前可以闲置；但在工件和机器都准备好的情况下机器必须开始工作。
生产调度问题的特点
生产调度问题具有复杂性、随机性、约束性和多目标性的特点。下面分别进行介绍。
1.复杂性。由于生产因素的多样性与复杂性，比如车间中工件、机器、和搬运系统之间的相互影响和作用，再加上工件加工时间、装配时间等因素的影响，导致生产调度问题非常复杂。
2.随机性。在实际的生产调度中有许多随机因素，比如工件到达时间的不确定性、工件的加工时间的不确定性。还有生产中的突发事件，例如机器故障、人为的误操作等，使得生产调度问题具有随机性。
3.约束性。生产调度问题中资源的数量、工件的到期时间及加工顺序等体现了其约束性[5]。
4.多目标性。
生产作业调度问题的目标是对企业资源进行优化配置，提高企业的经济效益。具体在评价调度方案好坏时，评价指标的确定可以根据影响企业成本费用的主要因素来确定，常用的指标有：总流程时间(makespan)、平均流程时间、最大交货期、平均交货期、交货期的工件数、平均在制品库存量和费用指标等。一个好的调度方案，一般应能做到：均衡生产、在制品库存量少、操作人员的等待时间或空闲时间少、准时交货、准备时间短和准备费用少、完成产品的总需求时间短等。
因此，生产作业调度问题一般属于多目标问题，其中典型的性能指标有[2]：
①基于加工完成时间的性能指标，例如最大完成时间(makespan)，平均完成时间，最大流经时间，总流经时间，加权流经时间，平均流经时间。
②基于交货期的性能指标，例如平均推迟完成时间，最大推迟完成时间，平均拖后时间，最大拖后时间，总拖后完成时间，拖后工件个数（完成时间大于交货期的工件个数）或拖后工件比例。
③基于库存的性能指标，例如平均机器空闲时间，最大机器空闲时间。
④多目标综合性能指标，例如流经时间与总拖后时间的综合，为权重，makespan与总拖后时间的综合，完成的提前时间与拖后时间的综合，其中和为权重，为工件完成的提前时间(earlobes)。
生产调度问题的分类
按照生产调度问题中加工机器数目来分，可以分为单机作业调度问题和双机作业调度问题；按照加工工件在机器上的加工次序是否相同来划分，可以分为流水作业调度和非流水作业调度。
(1)单机作业调度问题
若有个工件在1台机器上加工，则共有种作业排列方式。单机问题已有广泛适用的求解方法，其中最著名的是Smith(定理1-1)、Jackson(定理1-2)和Moor(定理1-3)提出的算法。
定理1-1最短加工时间(SPT)规则。对于单机调度问题，使平均流程时间最短的加工顺序为：。其中是第个工件的加工时间。
定理1-2最早交货期(EDD)规则。对于给定交货期的单机作业调度问题，使最大延误时间最小的加工顺序为：。其中是第个工件的交货期。
定理1-3使延误的工件数最小的求解方法。算法如下：
步骤1按EDD规则排列n个工件的加工顺序；
步骤2依次计算每个工件的完工时间，找出第1个延误工件人，转步骤3，如果没有延误工件，转步骤4；
步骤3从开始的k个工件中找出并删除加工时间最长的工件，转步骤2；
步骤4将被删除的工件以任意顺序排列在所得到的部分工件顺序的后面，构成最优加工顺序。
上述三种算法的排序目标是不同的，当排序目标发生改变时，这样的方法可能就不适用了。
(2)双机作业调度问题
设有个工件按相同的顺序在2台机器上加工，要寻找使总流程时间最小的加工顺序。Johnson提出了著名的Johnson算法(定理1-4)。后来，Jackson在Johnson算法的基础上，提出了解决异序双机问题的Johnson扩展方法(定理1-5)。
设有工件 ()在两台机器上按，的顺序进行加工。相应的加工时间为， (含生产准备时间)。
定理1-4Johnson算法。如果min <min，则优先于。若上式左右两项相等，则任一排序均为最佳。步骤如下：
步骤1：从所考虑的第一工序和第二工序的各个值中，找出最小者(如两者相等，任选其一)；
步骤2：该最小值若为，则置于前，若为，就放于后；
步骤3：去掉已排定的工件，回到步骤1，重复以上步骤，直到全部工件排序完成为止。
定理1-5Johnson扩展方法。
令表示只在机器上进行加工的零件集合；表示只在机器上进行加工的零件集合；表示先在机器上加工，然后在上加工的零件集合；表示先在机器上加工，然后在上加工的零件集合。则：
步骤1在机器上按、、的顺序排列；
步骤2在机器上按、、的顺序排列；
步骤3在集合内的零件，按工艺顺序、的Johnson算法进行工件排序;
步骤4在集合内的零件，按工艺顺序、的Johnson算法进行工件排序。
(3)流水作业调度问题
流水作业调度(flow shop scheduling，FSS)问题是指个工件在台机器上加工，每个工件按同一顺序通过台机器， FSS问题在生产中有广泛的实际应用背景，无论是组织成组加工，还是组织多品种混流生产，都会碰到这一问题。有关流水作业调度问题在第三章着重介绍。
(4)非流水作业调度问题
非流水作业调度(Job Shop Scheduling，JSS)问题是指有个工件需要在台机器上加上，每个工件在每台机器上加工的顺序和时间是给定的(但次序不一定相同)，要求确定在每台机器上如何安排各工件的加工顺序及加工起止时间，使得其目标函数为最小。JSS问题是更一般的，从而也是最困难的调度问题。
生产调度问题的研究方法
调度问题的研究方法历经由简单到复杂、从一元到多元的过程。求解调度问题的方法统称为调度优化算法，可以分为精确求解方法和近似求解方法[2]。这些方法从不同程度上表述了具体生产环境中的复杂的、多目标、动态的调度问题的一种抽象和简化。而评估这一个调度算法的主要标准是其优化效果的满意度。最初有关调度问题的研究方法集中在数学规划、系统仿真和简单的规则上，随着各种新的相关学科与优化技术的建立和发展，在调度领域出现了许多新的优化方法，例如基于人工智能、计算智能和实时智能等各种智能调度方法，这些方法己经成为调度方法的主流[7]。
传统方法
⑴整数规划
通过对车间调度问题建立一个整数规划模型，采用基于枚举思想的分枝定界法、割平面法和0-1整数规划法进行求解[8]。由于其计算复杂性，这类方法，不能获得实际应用。
⑵多目标优化
此方法同时考虑不同目标对同一问题的共同作用。对于给定的多个目标分别乘以不同的权重系数，再相加得到目标函数，对此目标函数在多目标的约束集合上求最优解；也可以选取唯一一个优化目标为主要目标，其它目标做约束处理，转化为一个单目标最优化问题。
⑶动态规划
动态规划将求解问题分解成多阶段进行，列出各阶段决策过程的函数方程，利用动态规划的最优化原理进行求解，使复杂问题简单化，且可以利用实际经验来提高求解效率。但通用性降低。
应用传统的优化理论与方法求解车间生产调度问题，存在很大的局限性，如建模困难、求解复杂等，因此很难获得实际应用。
⑷数学规划
该方法是将生产调度问题简化为数学规划模型，采用整数规划、动态规划以及决策分析算法来解决调度最优化或近似优化问题，属于精确调度方法，也称为优化调度方法。数学规划方法的优点是表达清晰，易于在计算机上求解，任务分配和排序的全局性比较好，所有的选择同时进行。这种方法存在建模不确定性和求解空间太大的问题，造成计算困难。
⑸仿真调度方法
通过运行仿真模型来收集数据能对实际系统进行性能和状态等方面的分析，从而能对系统采用合适的控制调度方法。系统仿真方法经常与其他方法结合起来使用。
计算智能方法
常见的基于计算智能的调度方法包括遗传算法、人工神经网络、模拟退火、模糊逻辑等。
1遗传算法
遗传算法简称GA，它是一种新的并行优化搜索方法。它是种模仿生物群体进化过程的一种优化算法，给定一组初始解作为一个群体，通过选择、交叉和变异等遗传操作来搜索最优解。最早是由在1975年提出的。遗传算法的最大优点是通过群体间的相互作用，保持己经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，对于某些问题遗传算法也存在着计算速度较慢的问题。这时通常将遗传算法与其他优化方法结合使用，有利于改善搜索效率。其基本理论内容将在下一章详细论述。
2人工神经网络
人工神经网络是在对人脑组织结构和运行机制认识理解的基础上模拟其结构和智能行为的一种工程系统。人工神经网络具有很强的分布式存储能力和很大的存储空间；具有自学习能力，通过学习建立和改变知识，而且具有推广和抽象能力；人工神经网络容错性很好，在高维空间中每一状态有更多的近邻，使多体效应更加复杂和显著，而且高维空间更易于分类。虽然人们对人工神经网络进行了大量的研究，但是在实际生产中它的应用依然不是很多，而且人工神经网络存在学习效率比较差、难以表达符号知识以及其他知识、计算速度比较慢和计算精度不高等缺点，这些都需要研究人员在今后的研究工作中进一步改进[12]。
3模拟退火算法
模拟退火算法将组合优化问题与统计力学中的热平衡问题类比，它模仿了晶体结晶的冷却过程。在较高温度下，系统状态为，能量(即目标函数)为，选择的一个临域，如果E()<E()，则接受为下一状态，否则以概率接受。经过一定次数（称为Markov链长)的搜索，认为系统在此温度下达到平衡，则降低温度再进行搜索，直到满足结束条件。模拟退火算法显示出了求解优化问题的好处，它可以突破局域搜索的限制，由于模拟退火法能以一定的概率接受差的能量值因而有可能跳出局部极小但它的收敛速度较慢。模拟退火算法在实际应用中往往不能产生最优结果，而且各个参数选择起来比较困难。为了弥补模拟退火算法的不足，可以把它与其他方法，如人工神经网络、遗传算法等方法结合使用。
4模糊逻辑
1965年，美国控制论专家、加利福尼亚大学教授zadeh首先提出了模糊集合的概念，发表了其开创性论文“模糊集合论(Fuzzy sets)。他提出，模糊数学的核心思想就是运用数学手段来仿效人脑思维，对复杂事物进行模糊处理。对模糊逻辑的研究虽然时间还不是很长，但它在智能模拟和智能控制等领域的应用却己有了飞快的发展。人们已经用模糊集理论来开发混杂调度方法，模糊集理论对于建模和求解Job shop调度问题是非常有用的，因为Job shop调度问题本身就具有许多模糊特征，例如不确定的加工次数和约束数量等。模糊系统的显著特点是能够直接地表示逻辑，适合于高级知识表达，具有较强的逻辑功能，但它没有本质的获取知识的能力，模糊规则的确定也比较困难，通常需要领域专家知识的指导。模糊调度方法通常与其他方法结合使用，例如与人工神经网络相结合形成模糊人工神经网络，与分枝定界法结合形成基于模糊规则的分枝定界法等。
基于知识的调度方法
基于知识的调度方法是用人工智能与专家系统自动产生调度或辅助调度，称为智能调度。它能根据系统当前状态和给定的优化目标，对知识库进行有效的启发式搜索和并行模糊推理机制，避开了繁琐的计算，并选择最优的调度策略，为在线决策提供支持。基于知识的调度方法，应用人工智能与专家系统知识，通过知识库与推理机制来求解调度问题，突破了传统算法的局限性。
还有智能专家系统、基于规则的调度方法和约束规划方法等其他调度方法，在此就不一一介绍。
第3章 Flow Shop调度问题及求解方法
Flow Shop调度问题描述
Flow Shop调度问题（flow shop scheduling problem，FSP）是许多实际流水线生产调度问题的简化模型，其研究具有重要的理论意义和工程价值，它也是目前研究最广泛的一类典型调度问题。如第一章所述，Flow Shop调度研究台机器上个工件的流水加工过程，每个零件在各机器上加工顺序相同，同时还有以下约定：
①每个工件在每台机器上只加工一次；
②每台机器一次在某一时刻只能够加工一个工件；
③每个工件同一时刻只能在一台机器上加工；
④各工件在每台机器上所需的加工时间和准备时间已知；
⑤每个工件在机器上的加工顺序是给定的。
⑥每台机器加工的各工件的顺序相同。
要求得到某调度方案使得某项指标最优。
Flow Shop调度问题的数学描述如下[2]。令为工件在机器上的加工时间， 为机器上加工完工件后马上加工工件所需的准备时间（若不加特殊说明，=0），为工件的加工完毕时间，为工件的计划完成时间，一般地，假设各工件按机器1至的顺序进行加工，令为所有工件的一个排序，则可以得到下面的数学模型：
()
()
()
其中，式()表示以最小拖延时间为指标。式()表示以最大完成时间为指标，即Makespan指标。
Flow Shop调度问题的求解方法
通常可将Flow Shop调度问题的求解方法分为精确方法、构造方法、改进方法和神经网络等。精确方法的计算量和存储量较大，仅适合小规模问题，如列举法、分支定界、动态规划等。构造型方法能快速构造解，如Gupta法、Johnson法、Palmer法等，该方法通过一定的规则来构造问题的解，但通常解的质量较差。改进型算法的前提条件是已有若干解，通过在其邻域内不断搜索和对当前解的替换来得到更高质量的解，如遗传算法、模拟退火等，这类算法一般具有较好的优化效果但是过程中存在大量迭代，且需要合适选取算法操作中的各项参数。
首先介绍几种求解置换Flow Shop调度的启发式方法，调度指标为Makespan。
启发式方法
方法
记为工件在机器上的加工时间，该方法首先对每个工件计算参量，然后将工件按参量值递减的顺序进行排序，从而得到一个次优调度。
方法
该方法首先对每个工件计算参量，其中若≤则，否则，然后将工件按参量值递增的顺序进行排列，从而得到一个次优调度。
-Gundry(BG)方法
该方法假设工件一旦开始加工就不允许在加工中途间断工序，直到所以工序的加工完成，即No-wait加工。图描绘了工件1在3台机器上的不间断加工过程。同时，该方法采用线性回归方法，对每个工件假设其加工时间的开始斜率和结束斜率。进而，将开始斜率最大的工件排列在第1个位置，然后将其余工件中开始斜率最接近前一个工件结束斜率的工件排列在下一个位置，依此类推，从而得到一个次优调度。
图工序不间断加工过程
-Dudek-Smith(CDS)方法
该方法首先计算参量和参量，然后对从1至采用Johnson方法分别求解得到个排序，进而采用其中目标值最小的排序为次优调度。其中，双机调度的Johnson方法对于双机问题能够给出最优调度，其步骤如下：
[n/2/F/Fmax调度的Johnson方法]
步骤1：令=1,=。
步骤2：令当前为排序表为。
步骤3：对未排序的工件，找出在一台机器上的最短加工时间和相应的工件编号；若最短加工时间出现在第1台机器上，在转步骤4；否则转步骤5。
步骤4：对最短加工时间出现在第1台机器上且相应的工件为，依次进行如下操作：
（）将工件排列在加工工序的第位，然后从未加工工件表中去掉该工件。
（）令=+1，然后转步骤6。
步骤5：对最短加工时间出现在第2 台机器上且相应的工件为，依次进行如下操作：
（）将工件排列在加工工序的第位，然后从未加工工件表中去掉该工件。
（）令=-1，然后转步骤6。
步骤6：构成去掉已排序规划后的新未排序工件表。若该表非空则转步骤3，否则算法结束。
方法
该方法首先计算参量和参量，然后把原多机排序问题转化为以和为加工时间的双机调度问题，进而用方法得到一个次优调度。
-enscore-Ham(NEH)方法
该方法的基本思想是赋予总加工时间越长的工件越大的在排列中插入优先权，即首先计算各工件在所有机器上的加工时间和，并按递减顺序排列，然后将前两个工件进行最优调度，进而依次将剩余工件逐一插入到以调度的工件排列中的某个位置，使得调度指标最小，直到所以工件调度完毕，从而得到一个次优调度。
方法
该方法对NEH的工件排序规则作了修改，它对各工件计算参量，并按递增顺序进行排序排列。首先选取队列中的第1个工件生成子调度，然后选取队列中的第个工件尝试插入到已生成子调度的第位置，其中，进而令其中使得调度指标最小的方案为新的子调度。如此依次将剩余所有工件进行插入，从而得到一个次优调度。
这些启发式方法具有快速构造调度解的优点，但调度质量有待提高。在此基础上，改进性搜索方法以其优化质量较高而备受重视，如遗传方法。
遗传算法
遗传算法（GA）是受生物进化论和遗传学说的启发而提出的，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。进化论认为每一物种在不断的发展过程中都是越来越适应环境。物种的每个个体的基本特征被后代所继承，但后代又不完全同于父代，所产生的新变化若适应环境则被保留下来。这种优良个体得以生存的思想就是适者生存的原理。遗传学说认为每个细胞中封装有一种指令遗传码，以基因的形式包含在染色体中，每个基因有特殊的位置并控制着某个特殊的性质。每个基因产生的个体对环境有一定的适应性。通过优胜劣汰的自然选择，适应值高的基因结构就保留下来。所有的自然种类都是适应环境而得以生存，这自然适应性是遗传算法的主旋律，遗传算法结合了达尔文适者生存和随机信息交换，前者消除了解中不适应因素，后者利用了原有解己有的知识，从而有力地加快了搜索过程。GA通过模拟“优胜劣汰、适者生存”的原理激励的结构，模拟遗传变异理论在迭代过程中保持已有的结构，同时寻求出更好的结构。
作为一种随机的优化与搜索方法，遗传算法有鲜明的特点[1]:
(l)遗传算法的搜索过程不直接用在变量上，而是作用在变量上编码后的字符上，其操作对象是一组可行解，搜索过程是从问题一个集合开始的，而不是从单个个体开始的，从一组解迭代到另一组解，具有隐含并行搜索特性，减小了陷入局部极小的可能。
(2)遗传算法只需利用目标的取值信息，因而适用于任何大规模、高度非线形的不连续多峰值函数的优化以及无解析表达式的目标函数的优化，具有很强的通用性。
(3)遗传算法可行解集是编码化的，因而具有良好的可操作性和简单性。
(4)遗传算法具有全局搜索能力，适用于依概率的随机搜索过程而非确定性过程，最善于搜索复杂问题和非线性问题。
(5)遗传算法具有并行性，通过对种群的遗传处理可处理大量的模式，并且容易并行实现。
(6)遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
随着计算机技术的发展，GA越来越的到人们的重视。自20世纪80年代以来关于它的理论和应用研究都成了十分热门的课题，目前它己被广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，在生产调度领域的应用尤为突出。本文将重点研究其在流水线中的应用。
遗传算法的基本流程和算法表示
1.通常，遗传算法的设计是按以下步骤进行的：
(1)确定问题的编码方案。由于GA通常不直接作用于问题的解空间，是利用解的某种编码表示来进行进化，因此选择合理的编码机制对算法质量效率有很大影响。
(2)确定适应度函数。由于GA通常基于适应度进行遗传操作，因此合理的适应度能够将各个体的优劣程度得以体现，并适应算法的进化过程。当适应度函数确定以后，自然选择规律是以适应度函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰，生存下来的染色体组成种群，形成可以繁殖下一代的群体。
(3)算法参数的选取。通常包括种群数目、交叉概率、变异概率、进化数等。
(4)遗传算子的设计。通常包括初始化、选择、交叉、变异和替换操作等。
(5)确定算法的终止条件。经过给定次数的迭代处理或是满足目标条件后，把最好的染色体作为优化问题的最优解。终止准则应根据所求解问题的性质，在优化量和效率方面作合理均衡或侧重。
2.标准遗传算法可以如下表示[2]：
(1)令=0，随机产生个初始个体构成初始种群。
(2)评价中各个体的适配值（fitnessvalue）。
(3)判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行一下步骤。
(4)令=0。
(5)根据适配值的大小以一定方式执行复制操作来从中选取两个个体。
(6)若交叉概率，则对选中的个体执行交叉操作来产生两个临时个体；否则将选中的父代个体作为临时个体。
(7)按变异概率对临时个体执行变异操作产生两个新个体放入，并令=+2。
(8)若<，则返回步骤5；否则令=+1，并返回步骤2。
上述算法中，适配值是对个体进行评价的一种指标，是GA进行优化所用的主要信息，它与个体的目标值存在一种对应关系；复制操作（也称选择操作）通常采用比例复制，即复制概率正比于个体的适配值，如此意味着适配值高的个体在下一代中复制自身的概率大，从而可提高种群的平均适配值；交叉操作通过交换两父代个体的部分信息构成后代个体，使得后代集成父代的有效模式，从而有助于产生优良个体；变异操作通过随机改变个体中某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。
用遗传算法求解Flow Shop调度问题
1.编码
编码就是将问题的解用一种码来表示，从而将问题的状态空间与GA的码空间相对应。编码在很大程度上依赖于问题的性质，而且会影响遗传操作的设计。由于GA的优化过程不是直接作用在问题参数本身，而是在一定编码机制对应的码空间上进行的，因此编码的选择是影响算法性能与效率的重要因素。
对函数优化的编码技术主要有二进制编码、十进制编码、实数编码等。
二进制编码将问题的解空间用一个二进制字符串（只有0、1两种字符）表示。十进制编码将问题的解用一个十进制串表示。本文将会采用十进制编码方法。
不同的码长和码制，对问题求解的精度与效率有很大影响，而且算法也将付出较大存储量和相应的转换运算，实数编码将问题的解用一个实数表示。解决了二进制和十进制编码对算法精度和存储量的影响，同时便于优化中引入问题的相关信息，譬如梯度信息。目前在高维复杂优化问题中得到了广泛应用，并取得了较好的效果。
2初始群的产生
大多数学者认为：初始种群只有随机选取才能达到所有状态的遍历，从而最优解在遗传算法的进化中最终得以生存，但是初始种群的随机选取加大了进化的代数，因而加大了计算时间。因此，一些学者提出应该用其他的一些启发式算法或经验选择一些比较好的染色体(种子)作为初始种群。考虑到搜索的效率和质量，一方面要求尽量使初始种群分散地分布于解空间，另一方面可以采用一些简单方法或规则产生一些解作为初始个体。但这时种子的选取可能缺乏代表性，可能产生早熟而无法求出最优解。在应用时具体问题具体分析。
种群数目是影响算法最终优化性能和效率的因素之一。通常，种群数目太小时，不能提供足够的采样点，以至算法性能很差，甚至得不到问题的可行解。种群太大时，尽管可增加优化信息以阻止早熟收敛的发生，但无疑会增加计算量，从而使收敛时间太长。当然，在优化过程中种群数目是允许变化的，也可以将较大规模的种群分解成若干子种群进行进化。本文采用随机产生初始种群方法。
3确定适应度函数
进化论中的适应度，一是表示某一个体对环境的适应能力，二是可以表示个体繁殖后代的能力。个体的适应度高，被选择的概率就高；反之，被选择的概率就低是遗传算法评价解的优劣程度的唯一标准。适应度函数的选取非常重要，它是算法演化过程的驱动力和进行自然选择的唯一依据，直接影响到遗传算法的收敛速度能否找到最优解。不同的问题，适应度函数有不同的选取方法，例如函数优化问题可直接将函数本身或其倒数作为适应度函数，而复杂系统的适应度函数一般不那么直观，需研究者自己设计，但要能够准确反映问题本身性质并且便于计算。
适应度函数设计主要满足以下条件：
(l)单值、连续、非负、最大化：该条件很容易理解和实现。
(2)合理、一致性：要求适应度函数反映对应解的优劣程度，该条件往往很难衡量。
(3)计算量小：适应度函数设计应尽可能简单，这样可以减少计算时间和空间上的复杂性，降低计算成本。
(4)通用性：强适应度对于某类具体问题应尽可能通用，最好无需使用者改变适应度函数中的参数。从目前而言，这个条件应该是不属于强要求。
常见的适应度函数有以下几种[9]：
(l)目标函数映射成适应度函数
对于求解效能函数和利润函数的最大值问题，一种最自然的想法就是将目标函数作为适应度函数。但是许多优化问题是求取费用函数的最小值，而遗传算法要求适应度函数越大个体越好。因此，在不少场合采用问题的目标函数作为个体的适应性度量时，必须将目标函数转化为求最大值形式。还有一种非常用的方法是将适应度函数取为目标函数的倒数。本文采用模糊数的期望值的倒数作为目标函数。
(2)适应度定标
在设计遗传算法时，群体的规模一般比实际物种的规模小得多，因此个体繁殖数量的调节在遗传操作中就比较重要。如果群体中某个体的适应度大大超过群体的平均适应值，则按照适应值比例选择时，该个体很快就会在群体中占有绝对的比例，从而导致算法较早地收敛到一个局部最优点，这种现象称为过早收敛。此时应该缩小这个个体的适应度。另一方面，在搜索过程的后期，虽然群体中存在足够的多样性，但群体的平均适应值可能会接近群体的最优适应值，导致群体中实际上已不存在竞争，搜索目标难以得到改善，出现了停止现象。在这种情况下，应该放大个体的适应度，以提高个体之间的竞争力。这种对适应度的缩放调整称为适应度函数的定标。定标己成为保持进化过程中竞争水平的重要技术。目前，主要定标方法有：线性定标、截断、乘幂定标和指数变换。
4选择操作
选择操作用于避免有效基因的损失，使高性能的个体得以更大的概率生存，从而提高全局收敛性和计算效率。目前，主要有适应值比例选择(轮盘赌选择)、基于排名的选择、锦标赛选择、父子竞争选择等。
(1)适应值比例选择
遗传算法最基本的选择方式是根据个体适应值的比例进行选择，即轮盘赌选择。其基本是根据每个染色体适应值的比例来确定该个体的选择概率。对于给定的规模为N的种群，第i个个体的选择概率为。
是群体中第个个体的适应值，为群体适应值之和，显然适应度函数值高的个体具有较大的选择概率。选择的过程就是旋转轮盘若干次(次数等于种群规模)。每次为新种群选择一个个体，这是一个随机选择过程。
缺点是：在算法进行的早期，个别超强染色体具有控制选择过程的趋势，而在晚期，个体选择概率差别不大，竞争并不激烈，呈现出随机搜索的行为。
(2)基于排名的选择
“排名”就是将种群中的所有个体按照适应值的大小进行排序，每个个体的序号称为它的“排名”。根据每个个体的排名来确定其选择概率以减少选择压力。因为造成种群早熟收敛的原因往往是出现了适应值远远高于种群的平均适应值的“超强个体”。 “超强个体”生成大量的后代，并使得种群中其他一些适应值较低的个体不能生成后代。基于“排名”的选择方法可以对选择压力进行调节，避免产生这种现象。常用的方法有两种：线性排名选择和非线性排名选择。
(3)锦标赛选择
标赛选择方式是将上一代群体中的个体和本次遗传操作产生的所有新个体放到一起，按适应值从大到小的顺序排队，然后取排在前面的个个体组成新一代群体。是GA另一种常用的选择方式。
(4)父子竞争选择
遗传算法的交叉算子作用与某两个父个体时，会产生两个子个体，父子两代共四个个体平等竞争，淘汰两个低适应值个体，保留两个高适应值个体。遗传算法的变异算子作用于某一个父代个体时，会产生一个子代个体，如果子代个体的适应值比父代个体高则用子代个体取代父代个体；否则保留父代淘汰子代个体。
本文采用轮盘赌选择方法。
5交叉操作
交叉操作用于组出新的个体，在解空间中进行有效搜索，同时降低对有效模式的破坏概率。
二进制编码GA通常采用单点交又和多点交叉。
(1)单点交叉
首先随机确定一个交叉位置，然后对换交叉点后的子串。譬如，父串为(0101|100)和(1100|111)，若单点交叉位置为4，则后代个体为(0101|111)和(1100|100)。
(3)多点交叉
首先随机确定多个交叉位置，然后对换相应的子串。若两点交叉，交叉位置为1，5，父代个体同上，则后代个体为(0|1001|00)和(1|1011|11)。
十进制编码GA的交叉操作类似于二进制编码GA。
实数编码GA通常采用双个体算术交叉或多个体算术交叉。
(1)双个体算术交叉
针对选中的两个个体进行如下交叉，即
，
其中随机数，，为父代个体，，为后代个体。
(2)多个体算数交叉。
针对多个选中的个体进行如下交叉，即，其中为父代个体，为后代个体，且
组合优化中的置换编码GA通常采取部分映射交叉、顺序交又、循环交叉，基于位置的交叉等。
(1)部分映射交叉(PMX)
整个交叉操作过程由两步来完成，首先随机选出两个交叉点，交换父代个体交叉点之间的片段，然后根据交叉区域内各基因值之间的映射关系来修正交叉区域之外的各基因座的基因值。
例：
父代1
7
3
2
8
1
6
5
4
父代2
6
8
1
3
5
2
4
7
I随机选取交叉位置(两点交叉)
II交换双亲中交叉点之间的子串
父代1
7
3
2
8
1
6
5
4
父代2
6
8
1
3
5
2
4
7
III确定基因关系
父代1
7
3
1
3
5
6
5
4
父代2
6
8
2
8
1
2
4
7
1
3
5
2
8
1
VI用对应关系将后代合法化，得到后代
子代1
7
8
1
3
5
6
2
4
子代2
6
3
2
8
1
5
4
7
对于父代1的剩余基因，由于7不与(135)冲突，直接填入，3存在冲突，3的映射基因为8不冲突填入，6不冲突，填入， 5冲突，5的映射基因为1，依然冲突，1的映射基因为2不冲突，填入，4不冲突，直接填入，得到子代1。
(2)顺序交叉(OX)
对两交叉位置间的基因串进行交换，其他位置的基因根据父代个体位置的相对顺序来确定。
例如;若父代个体和交叉点同上，操作如下:
I随机选取交叉位置(3、7)(两点交叉)
II在原先父代个体中删除另一父代个体交叉点间的基因
父代1
7
3
2
8
1
6
5
4
父代2
6
8
1
3
5
2
4
7
父代1
7
2
8
6
4
父代2
6
3
5
4
7
III从第二个交叉点后开始循环填入剩余基因
父代1
2
8
6
4
7
父代2
3
5
4
7
6
VI交换双亲中的交叉点之间的子串，得到后代
父代1
2
8
1
3
5
6
4
7
父代2
3
5
2
8
1
4
7
6
这种算子在构造后代时从一个父体中选取一个基因片段并保持另一个父体中基因编码的相对次序。
(3)循环交叉(CX)
一部分基因由两个父个体相应位置基因构成的环来确定，而其他的基因另取自另一父个体。操作如下：
I根据双亲相应的基因的位置找出一个循环，如
父代1
8
2
3
1
4
5
6
7
父代2
7
4
2
8
6
1
3
5
II分别把父代的循环上的基因复制到下后代上
III将另一父体的剩余基因填满剩余的位置，得到后代
父代1
8
1
5
7
父代2
7
8
1
5
父代1
8
4
2
1
6
5
3
7
父代2
7
2
3
8
4
1
6
5
这种算子在构造后代时，每个基因编码及其所处位置都来自某一个父体。CX保留了父体序列中元素的绝对位置。
本文采用部分映射交叉PMX。
6变异操作
变异操作是指染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。用以改善局部搜索能力，并有利于增加群体的多样性，一定程度上克服早熟收敛。
实数编码中通常采用扰动式变异，即对原先个体附加一定机制的扰动来实现变异，即其中和分别为新旧个体，为扰动幅度参数，为随机扰动变量。可以服从高斯分布、柯西分布、均匀分布，也可以为混沌变量或梯度信息。
组合优化问题中的置换编码GA通常采用互换、逆序和插入变异
(1)互换变异，即随机选取一个染色体的两个不同基因，交换其位置，如下图：
I选择两个基因
II交换位置得到后代
父代
1
2
3
4
5
6
7
8
后代
1
2
6
4
5
3
7
8
(2)逆序变异，即将染色体中两个不同随机位置间的基因串逆序。如下图所示：
I选择两个位置，确定基因串
II将基因串逆序得到后代
父代
1
2
3
4
5
6
7
8
后代
1
2
6
5
4
3
7
8
(3)插入变异：即随机选取一个染色体的两个不同位置，将一个基因插入另一个位置，如下图所示：
I选择两个位置
父代
1
2
3
4
5
6
7
8
II将后代一个位置的基因插入前一个位置，得到后代
后代
1
2
6
3
4
5
7
8
本文采用逆序变异方法。
第4章 基于满意度的不确定条件下Flow Shop调度问题求解方法
实际生产调度系统中往往存在大量不确定因素，譬如加工时间的不确定性、交货期的不确定性等，因此研究不确定条件下的Flow Shop调度问题具有重要的现实意义。不确定条件下的Flow Shop调度问题也可以称为模糊Flow Shop调度问题。该问题受到越来越多的重视，Slowinski等编著了《模糊调度》一书专门介绍这方面的研究[32]。但是这类研究还处于起步和发展阶段，许多方面尚需进一步深入研究和完善[2]。本章首先介绍生产调度过程中的不确定性，重点阐述模糊交货期下的Flow Shop调度问题，并提出一种以加工工件的满意度来决定生产调度的方法。
生产调度过程中的不确定性
确定是相对的，不确定是绝对的。世界以一种非常确定的不确定性方式运行着。不确定性是事物固有的一种客观属性。不确定性广泛地存在于各种社会现象、自然现象及工程实践之中。顾名思义，不确定性是确定性的反面，它可以理解为不肯定性、不确知性、变化性和不准确性、随机性、偶然性。由于事物在其发生、发展及演变过程中受到来自不同方面的诸多因素的共同影响，使得它的状态始终体现为一种不稳定、模糊、无序或混沌等现象，这种现象即被认为是事物的不确定性。随着社会的进步和科学的发展，人类对社会实践的认识越来越深入，所涉及的系统也越来越庞大，越来越复杂，不确定性的表现也将越来越突出，越来越复杂。
关于生产调度问题的研究成果中，有相当一部分是基于这样一种共同的假设，就是所有的参数都是确定的，而且调度一旦下达到车间，就会按部就班的执行。这种假设并不现实，在实际生产过程中，存在大量的不确定因素，比如原料供应、产品需求及加工时间等等，使得由各种确定性模型和方法得到的优化调度性能指标降低甚至不再可行。
在实际流水车间生产过程中，工件通常受到释放期限和收工期限的约束，即受工件被允许可以开始生产的期限和必须完成生产过程的期限的限制。比如，一个工件必须在所需原料储备完毕后才可以开始生产，并且收工期限必须保证产品能在用户要求的时间内送达。只有同时满足释放期限和收工期限的工件的加工序列才是可行的。传统的调度算法只处理精确数据，当释放期限和收工期限的约束条件发生细微变化时可能会遗漏可行解。实际情况是工件的释放期限和收工期限可以在一定时间段内浮动，即放宽对两者的约束，这样可以得到满足松弛释放期限和收工期限的具有最大满意度的工件加工序列。
因此在处理生产调度问题的时候，必须要考虑生产过程中存在的不确定因素。因此根据不确定因素的起因或来源，可以进行如下简单分类。
1.系统固有的不确定因素：由于实际工业生产工艺过程的复杂性，各种化学、物理、热力学等数据很难获得，与这类不确定性相关的信息通常从实验实际记录的数据中进行分析后获得。
2.生产过程中产生的不确定性：这类不确定性主要包括生产过程中各体介质的流速、温度、压力等的变化和设备的处理能力。如在某生产过程中中间产品的稳定存放时间。
3.外部环境的不确定性：企业的生产是受外部环境的影响，产品的需求量，价格、能源、原材料的供应及其他外部环境因素构成不确定因素。
4.离散不确定性：比如设备的故障，机械、仪表的失效、人工误操作等等。这类不确定性对企业的组织生产造成很大的困难。
基于满意度的求解方法
模糊交货期下Flow Shop调度问题描述
考虑n工件和m设备的流水车间问题，每个工件包含3个模糊参数：模糊加工时间、模糊释放期限和模糊收工期限。工件在设备上以相同路径进行加工，一台设备在同一时刻只能加工一个工件。令为工件的模糊释放时间，为在设备j上的模糊加工时间，为在设备j上的模糊完成时间，的计算公式为
= EMBED EMBED (),
=(,) EMBED (),
= EMBED EMBED (),
=(,) EMBED (),
其中和分别代表模糊加法和模糊取极大。对加工序列中的每个工件求出它在最后一个设备上的模糊完成时间（即），从而可以利用的模糊收工期限与的隶属度函数求得交点,交点的纵坐标就是的最大满意度，再利用下一节的公式()求得的满意度。
问题目标是求出具有最大满意度的工件加工序列，即。
满意度方法分析及模拟实验
模糊加工时间
工件的模糊加工时间经研究表明大多为图所使得的模糊数，记为=，隶属度函数为
= (),
图 模糊加工时间隶属度函数1
函数和均为严格单调函数。当=且=时，加工时间表示为图 所示三角模糊数。
图 模糊加工时间隶属度函数2
模糊释放期限和模糊收工期限
模糊释放期限记为=(,)，其满意度隶属度函数为
= (),
在[,]内满意度线性增加，在之后满意度为1。
模糊收工期限记为=(,)，其满意度隶属函数为
= ()，
在之前满意度为1，在[,]内满意度线性减少。如图所示。
图 满意度隶属函数
工件加工序列的满意度
当工件的释放期限和收工期限都是模糊数时，其开始与结束时间的约束条件以一定满意度成立。我们以和分别标记工件的模糊释放期限与模糊收工期限，为的模糊完成时间。对给定的工件序列X=(,,…,)，X的满意度计算公式为：
Sat(X)=(Sat()) ( )
对每个工件，令是的结束时间，关于释放期限和收工期限的满意度计算公式为：
Sat ()=min() ()
现在假定=(,)，=(,)，如果工件可以在之后开始，引入≥0，工件的释放期限可描述为一个梯形隶属函数=(,,+,+)，如图。根据式(),的满意度将在和的交点处取得最大值，最大满意度以表示。此交点不受影响，因此求解值只考虑的左边部分，在图中将其表示为最早释放期限，类似的，以E()和E()表示总加工时间和最早完成时间，并且E()=E()+E()。图说明当<+时如何计算值，工件必须在开始在结束才能得到最大满意度。当≥+时=1。
图梯形隶属度函数
图简化的隶属度函数
模拟计算
以一个2-设备3-工件flow shop问题为例，见表，假定工件装入设备的顺序是X：--。首先要求得序列中每个工件的最大满意度，然后才能得到该序列的满意度。由式()-()得到工件的最早完成时间，而后利用式()计算满意度。
对工件，由=(4,7)得到E()=(4,7,7)；计算E()，由= E()=(4,7,7) (1,2,3)=(5,9,10)，= EMBED =(5,9,10) (4,5,6)=(9,14,16)，得到E()=(9,14,16)。由图可得知=，=和=，从而得到Sat ()即=，=，=。同理得到工件2、3的相应值，Sat ()=1，Sat ()=，所以工件序列X的满意度为。
用相同方法可以求得工件的不同加工序列的满意度，最终得到具有最大满意度的加工序列。满意度方法能够以较高效率解决一般规模的Flow Shop调度问题。对庞大规模的同类问题的研究尚待继续深入。
表工件的各种时间数据
(4,7)
(1,2,3)
(4,5,6)
(12,20)
(3,4)
(5,7,9)
(3,5,9)
(21,26)
(5,8)
(6,7,8)
(5,8,9)
(19,27)
图实验数据隶属度函数
第5章 存储时间有限型Flow Shop问题提前_拖期调度
引言
现代准时生产制（just-in-time）要求产品按时加工、准时交货，提前_拖期调度问题引起极大关注。面对客户需求，企业无论是提前完工还是拖期完工，只要偏离客户规定的交货期，企业都要受到一定的惩罚。提前_拖期调度问题研究的是如何合理安排作业，使得企业因为提前完工或是拖期完工而受到的惩罚最小。提前_拖期调度也可描述为交货期窗口调度。本小节综合考虑了产品处理时间的不确定性，引入了中间产品存储时间有限的约束条件，采用三角模糊数描述处理时间的不确定性，并应用遗传算法进行求解。
问题描述
如上所述，Flow Shop调度问题研究m台机器上个工件的流水加工过程，每个工件在各机器上的加工顺序相同，约定每个工件在每台机器上只能加工一次，每台机器在同一时刻只能加工一个工件，而且，每个工件的加工必须在前一个工件加工完毕后才能进行生产。在存储时间有限型中间储罐的Flow Shop调度模型中，由于某些产品在加工过程中具有不稳定性，因此在储罐中存储的时间是一个有限值，在此时间段内，必须进入下一台机器进行加工。
存储时间有限型flowshop问题提前_拖期调度问题的数学描述如下：
令表示工件在机器上的加工时间，包括装配时间、传输时间、加工时间及清洗时间等，是变化的不确定量，采用三角模糊数表示；和分别表示工件在机器上的开始时间和完成时间，为工件的完成时间；表示工件在机器和机器间的中间储罐存储策略；工件的交货期窗口为，其中和分别表示工件的最早和最晚交货期。当<称工件提前，当>则产品 i拖期。如果工件在交货期窗口之外完工将受到惩罚，提前惩罚权重记为，拖期惩罚权重，一般地 EMBED EMBED 。
数学模型
()
惩罚值目标函数为所有产品惩罚数之和：
(4-3-2)
其中，产品的惩罚值为：
(4-3-3)
其中应用了两种模糊运算：模糊加法和模糊极大运算。根据模糊数学的有关定义，两种运算分别定义为：
设两个模糊数为=(,,)，= (,,)，则有
+=(+,+,+)
max(,)=(max(,),max(,),max(,))
遗传算法实现
编码
本例根据Flow Shop生产的特性，工件编码采用通常的十进制编码方式，即自然数编码。例如对于工件数为5的Flow Shop问题，每个染色体代表工件的序号，个体12345表示工件1先加工，然后是工件2，依次类推，每个个体表示一个加工顺序。这种编码方式的好处是直观性很强。
初始群的产生
本例中，对于有个工件的Flow Shop问题，我们定义初始群的大小为，个染色体是随机生成的。
确定适应度函数
本例中，根据上面的数学模型计算出产品的惩罚值，此时得到的是三角模糊数，再利用求期望值公式，将作为适应度目标函数。
选择操作
本例采用轮盘式选择策略。
交叉操作
本例采用部分映射交叉PMX。
变异操作
采用逆序遍历。
停止准则
根据问题类型的不同和规模的大小，设置最大迭代次数或是否找到可接受的解作为停止准则，把满足停止准则的当前代的最好个体作为最优解输出。
实验分析
上述算法用VC++进行编程，对10个加工产品、5个生产单元的Flow Shop调度问题进行仿真研究，考虑了处理时间的不确定性（表）、中间储罐的最大存储时间（表）以及交货期窗口和提前-拖期惩罚权重（表），如图1所示随着算法的不断演化，适应度目标函数值越来越趋于最优并趋向稳定，验证了算法的收敛性。
表模糊Flow Shop调度问题产品的加工时间
job
unit1
unit2
unit3
unit4
unit5
1
125,130,130
21,23,27
98,110,120
32,33,35
36,37,43
2
84,87,100
66,80,90
85,87,100
80,92,95
39,40,44
3
77,80,86
24,25,28
60,67,80
120,130,150
120,130,140
4
8,10,15
120,123,130
10,11,15
70,79,80
100,110,120
5
80,88,90
20,21,25
11,12,16
30,33,38
2,6,8
6
120,140,149
95,99,110
82,90,100
90,101,110
15,16,20
7
25,27,29
6,8,10
68,70,80
47,50,52
55,60,63
8
25,30,32
120,130,135
60,69,80
100,104,120
110,117,140
9
100,104,110
75,78,90
49,56,60
1,3,7
100,109,118
10
110,130,150
110,130,134
31,35,40
14,17,18
50,56,60
表 中间储罐最大存储时间
job
between U1 ,U2
between U2 ,U3
between U3 ,U4
between U4 ,U5
1
18
17
10
16
2
9
5
14
13
3
6
11
15
13
4
15
20
16
3
5
10
20
24
3
6
14
21
2
7
7
19
7
13
19
8
22
6
19
15
9
12
11
13
7
10
15
27
25
8
表 交货期窗口的提前_拖期权重
job
交货期窗口
提前/拖期权重
1
355，445
3，4
2
950，1050
3，4
3
680，720
4，5
4
370，420
6，5
5
955，1155
4，5
6
820，870
3，3
7
250，350
3，4
8
770，820
4，4
9
855，955
3，5
10
810，860
3，3
图适应度目标函数演化曲线
第6章 结束语
生产调度问题中的流程工业在我国的工业生产中具有非常重要的地位，研究Flow Shop调度优化问题对提高企业的竞争力、促进经济社会发展起着至关重要的作用。由于实际生产中存在着大量不确定因素，所以对模糊生产调度的研究在现阶段受到重视。将释放期限和收工期限的约束条件以模糊数来表示，并利用满意度计算公式，可以获得有较高满意度的工件加工序列。中间存储时间有限型Flow Shop调度问题是模糊生产调度中比较重要的一种，论文借鉴遗传算法对其进行求解，并通过实验加以证明，求得结果值的曲线比较科学。
本文的主要工作表述如下：
1.对生产调度的相关知识进行阐述，重点是Flow Shop生产调度问题。
2.以模糊数表示相应的模糊Flow Shop调度问题，以模糊释放期限和模糊收工期限来使得工件的加工过程更加符合实际，并通过满意度计算公式可以获得最佳工件序列。
3.对存储时间有限型Flow Shop问题提前_拖期调度，利用遗传算法给出其求解过程，并给出实验分析。
参考文献
[1] 陈荣秋.排序理论与方法.华中理工大学出版社,1987：1~3
[2] 王凌.车间调度及其遗传算法.清华大学出版社,2003：1
[3] 唐恒永,赵传立.排序引论.科学出版社,2002：23~48
[4] 陈亮，马柯.遗传算法在车间调度问题中的应用.西安工程科技学院2002-12
[5] 宋毅，王万良.基于遗传算法的生产调度方法及其软件方法.浙江工业大学，2000
[6] Graves S review of production scheduling[J].Operations Research. 1981,29(4):646-675
[7] 程俊刚，戴国忠.流程企业生产调度方法与应用研究.中国科学软件研究院，2003
[8] 李培根.应用0-1整数规划解决FMS作业计划问题.组合机床与自动化加技术，1998，3:25
[9] 王景恒，郭海楼.基于遗传算法的作业车间调度问题研究.长春光学精密机械学.2001-10
[10] 徐震浩.基于免疫优化算法的不确定性间歇生产过程调度问题研究[D].华东理工大学，博士论文，2004.
[11] 王军，金以慧.连续过程生产调度的研究策略[J].系统工程理论与实践，1998，18(2):40-46.
[12] 程俊刚，戴国忠.流程企业生产调度方法与应用研究.中国科学软件研究院，2003
[13] 徐震浩, 顾幸生. 用模糊截集解决不确定条件下的具有中间存储时间有限的 flow shop调度问题 [C] .第五届全球智能控制与自动化大会. 杭州:电力与电气工程师协会, 2004, 4:2923 - 2927.
[14] 顾幸生. 不确定条件下的生产调度 [J ]. 华东理工大学学报,(自然科学版)2000,26 5 :441 - 446.
[15] ISHII H,MASUDS T. Two scheduling problems with fuzzyduedate[J]. Fuzzy Sets and Systems,1992, 46(3): 339-347·
[16] Pistikopoulos E N. Uncertainty in process design and operations[J]. Computers Chem Eng,1995, 19 (Suppl) :5532563.
[17] Masatoshi S Tetsuya M. An efficient genetic algorithm for job shop scheduling problems with fuzzy processing time and fuzzy duedate[J]. Comput Ind Eng,1999, 36 (2) :325-341.
[18] Wiede J R W, Kuriyan K Peklatitis G V. Determination of completion times for serial multi-product processes[J].Comput Chem Eng, 1987, 11(4) :3372344.
[19] Reeves .,Yamada T.,Solving the Csum Permutation Flowshop Scheduling Problem by Genetic Local Search,IEEE International Conference on Evolutionary Computation,(1998),230-234
[20] Prinedo M, (2002), Scheduling Theory, Algorithms, and Systems, Second Edition, Prentice Hall, 2002
[21] McCahon S., and Lee E. S. (1990), “Job sequencing with fuzzy processing times”, Computers and Mathematics with Applications, , , pages 31-41
[22] Petrovic S., and Song X. (2003), “A new approach on two-machine flow shop problem with uncertain processing time”. In Proceedings of the International Symposium on Uncertainty, Modeling and Analysis, ISUMA 2003, pages 110-115, University of Maryland, College Park, USA, Sept 21-24, 2003
[23] Sakawa M, Kubota R, (2000), “Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms”, European Journal of Operational Research, vol. 120, no. 2, pages 393-407
[24] 徐震浩.基于免疫优化算法的不确定间歇生产过程调度问题研究[D].华东理工大学，博士论文，2004
[25] 李歧强，生产调度问题研究[D].浙江大学博士论文，1998.
[26] 陈雄，万位水，徐心和.车间作业调度方法的综述[C].第九界 控制与决策年会论文集，1997.
[27] 陈雄，李海刚，吴启迪.基于遗传算法的Job-shop调度问题的研究[J].同
济大学学报，2002，30(1).
[28] 依杨，汪定伟.软计算求解并行多机成组工件提前/拖期惩罚调度问题[J].自动化学报，2002，28(5).
[29] M T Rodammer, K P White. A recent survey of production scheduling[J]. IEEE Transactions on Systems, Man and Cybernetics,1988,18(6).
[30] B. Srinibasan, D. Bonvin, E. Visser, S. Palanki. Dynamic optimization of batch processes II. Role of maesurements in handling uncertainty [J]. computers and chemical Engneering,2002,27(1).
[31] M T Jenson. Robust and flexible scheduling with evolutionary computation[D]. University of Aarhus,PhD Dissertation,2001.
[32] Slowinski R, Hapke M. 2000. Scheduling under fuzziness. New York: Physica-Verlag.
[33] Wang L, Zheng D Z. 2002. A modified evolutionary programming for flow shop scheduling. International Journal of Advanced Manufacturing Technology, .
[34] Wang L, Zheng D Z. 2003. An effective hybrid heuristic for flow shop scheduling. International Journal of Advanced Manufacturing Technology,21(1).
[35] Wanf L, Zheng D Z. 2002. Finite-time performance analysis for genetic algorithm. Progress in Natural Science, 12(12).
致 谢
本文的研究工作是在导师杨公平副教授的悉心指导下完成的。杨老师为此倾注了大量的心血，循循善诱地启发，开拓我的思路，培养我发现问题、分析问题和解决问题的能力。对我所写的文章杨老师都要作仔细的审阅，关键的问题经常要作认真仔细的讨论，使我的科研论文写作水平得到了大幅度的提高。他严谨的治学态度，敏锐的洞察力，以及踏实勤恳的工作精神都给我留下了深刻的印象，这些无疑将成为我受益终生的宝贵财富。在此，谨向杨老师表示最真挚的谢意。
感谢山东大学计算机科学与技术学院的老师们几年来的悉心教育与指导。
衷心感谢所有曾经关心我、帮助我的师长、同事和朋友们。
攻读学位期间发表的学术论文
具有模糊处理时间的flow shop问题生产评价方法，福建电脑，2008，第9期，P86，第一作者。
学位论文评阅及答辩情况表
论文评阅人
姓 名
专业技术职务
所 在 单 位
对论文总体评价※
答 辩 委 员 会 成
员
姓 名
专业技术职务
所 在 单 位
备 注
主 席
委
员
答辩委员会对论
文的总体评价※
答辩秘书
答辩日期
备注
优秀为“A”；良好为“B”；合格为“C”；不合格为“D”。
PAGE II
