《Handbook of Optimizing Package: easyopt.jar》

 

 

 

 

 

 

 

 

 

 

 

AEOM

December, 2021

目   录

前   言... 1

第一章           easyopt.jar功能简介... 2

1.1 easyopt.jar功能简介... 2

1.2 easyopt.jar导入eclipse. 2

第二章           车间调度理论基础... 4

2.1 车间调度问题... 4

2.1.1 车间调度问题概述... 4

2.1.2 车间调度问题表示法和分类... 5

2.2 常见车间调度问题... 7

2.2.1 并行机调度PMS问题... 7

2.2.2 置换流水车间调度问题PFSP. 8

2.2.3 零等待流水车间调度问题NWFSP. 10

2.2.4 零空闲流水车间调度问题NIFSP. 11

2.2.5 阻塞流水车间调度问题BFSP. 11

2.2.6 混合流水车间调度问题HFSP. 13

2.2.7 作业车间调度问题JSP. 14

2.3 经验规则算法... 16

2.3.1 经验规则算法简介... 16

2.3.2 Johnson算法... 17

2.3.3 CDS算法... 17

2.3.4 Palmer算法... 20

2.3.5 Palmer算法... 22

2.4 智能优化算法... 23

2.4.1模拟退火算法SA简介... 24

2.4.2遗传算法GA简介... 26

2.4.3蚁群算法ACO简介... 29

2.4.4粒子群优化PSO简介... 33

2.4.5教学算法TLBO简介... 35

第三章           easyopt.chart包中类和方法的使用... 38

3.1 easyopt.chart包结构... 38

3.2 GantChart类及其使用... 38

3.3 OptSeriesChart类及其使用... 40

第四章           easyopt.common包中类和方法的使用... 43

4.1 easyopt.common包结构... 43

4.2 EasyMath类及其使用... 43

4.2.1 数组排序方法sortArray. 43

4.2.2 产生随机编码的方法... 45

4.3 EasyArray类及其使用... 45

4.3.1 EasyArray类中封装的方法... 45

4.3.2 字符串转换为数组的方法... 47

4.3.3 数组操作的方法... 47

4.3.4 EasyArray类中方法使用示例... 47

4.4 GA类及其使用... 49

4.4.1 GA类中封装的方法... 49

4.4.2 GA类中初始化种群方法的使用... 50

4.4.3 GA类中选择算子方法的使用... 51

4.4.4 GA类中交叉算子方法的使用... 52

4.4.5 GA类中变异算子方法的使用... 53

4.5 ACO类及其使用... 55

4.5.1 ACO类中封装的方法... 55

4.5.2 ACO类中初始化信息素的方法... 55

4.5.3 ACO类中根据信息数生成路径的方法... 57

4.5.4 ACO类中更新信息素的方法... 58

4.6 PSO类及其使用... 59

4.6.1 PSO类中封装的方法... 59

4.6.2 PSO类中初始化位置和速度向量的方法... 60

4.6.3 PSO类中由位置向量转换为作业排序的方法... 61

4.6.4 PSO类中从一维数组中找出最小值序号的方法... 62

4.6.5 PSO类中位置和速度更新的方法... 62

4.7 TLBO类及其使用... 63

4.7.1 TLBO类中封装的方法... 63

4.7.2 TLBO类中初始化班级成绩的方法... 64

4.7.3 TLBO类中成绩向量转换为作业排序的方法... 65

4.7.4 TLBO类中从顺序数中随机找出两个不同数值的方法... 66

4.7.5 TLBO类中学生成绩更新的方法... 66

4.8 Rules类及其使用... 67

4.8.1 Rules类中封装的方法... 67

4.8.2 Rules类中EDD方法... 67

4.8.3 Rules类中FCFS方法... 68

4.8.4 Rules类中FEDD方法... 68

4.8.5 Rules类中FLPT方法... 69

4.8.6 Rules类中FSPT方法... 70

第五章           easyopt.model包中类和方法的使用... 72

5.1 easyopt.model包结构... 72

5.2 Order类及其使用... 72

5.3 Process类及其使用... 73

5.4 Task类及其使用... 74

第六章           easyopt.shopSch包中类和方法的使用... 76

6.1 easyopt.shopSch包结构... 76

6.2 Schedule类及其使用... 76

6.2.1 Schedule类中封装的方法... 77

6.2.2 Schedule类中方法的使用... 77

6.3 Scheduling类及其使用... 80

6.3.1 Scheduling类中封装的方法... 80

6.3.2 Scheduling类中方法的使用... 81

第七章           easyopt.shopSch.pms包中类和方法的使用... 90

7.1 easyopt.shopSch.pms包结构... 90

7.2 PMS类及其使用... 90

7.2.1 PMS类中封装的方法... 90

7.2.2 PMS类中计算和优化方法的使用... 93

7.3 QmPMS类及其使用... 101

7.3.1 QmPMS类中封装的方法... 101

7.3.2 QmPMS类中计算和优化方法的使用... 102

7.4 SynPMS类及其使用... 108

7.4.1 SynPMS类中封装的方法... 108

7.4.2 SynPMS类中计算和优化方法的使用... 110

第八章           easyopt. shopSch.fsp包中类和方法的使用... 119

8.1 easyopt. shopSch.fsp包结构... 119

8.2 Rules4PFSP类及其使用... 119

8.2.1 Rules4PFSP类中封装的方法... 119

8.2.2 Rules4PFSP类中封装方法的使用... 120

8.3 FSP类及其使用... 125

8.3.1 FSP类中封装的方法... 125

8.3.2 FSP类中封装方法的使用... 127

8.4 NWFSP类及其使用... 139

8.4.1 NWFSP类中封装的方法... 139

8.4.2 NWFSP类中封装方法的使用... 142

8.5 NIFSP类及其使用... 151

8.5.1 NIFSP类中封装的方法... 151

8.5.2 NIFSP类中封装方法的使用... 154

8.6 BFSP类及其使用... 164

8.6.1 BFSP类中封装的方法... 164

8.6.2 BFSP类中封装方法的使用... 166

8.7 HFSP类及其使用... 175

8.7.1 HFSP类中封装的方法... 175

8.7.2 HFSP类中封装方法的使用... 178

第九章           easyopt. shopSch.jsp包中类和方法的使用... 187

9.1 easyopt. shopSch.jsp包结构... 187

9.2 JSPCommon类及其使用... 187

9.2.1 JSPCommon类中封装的方法... 187

9.2.2 JSPCommon类中封装方法的使用... 188

9.3 JSP类及其使用... 192

9.3.1 JSP类中封装的方法... 192

9.3.2 JSP类中封装方法的使用... 195

 

 

 

 

前   言

优化计算工具包easyopt.jar是在jdk1.8平台上开发的，可用于jdk1.8及其之后版本的环境。

本说明书是基于easyopt.jar V20220331版本编写的，用于帮助用户理解easyopt.jar车间调度计算和优化包中的类和方法的作用和使用方法。

本说明书结合easyopt.jar的API文档学习和使用更易于理解和掌握。

 

第一章  easyopt.jar功能简介

1.1 easyopt.jar功能简介

easyopt.jar包主要包含了进行车间调度计算或智能优化过程中所使用的类和方法集合，当前主要包括如下的子包：

表1.1 easyopt.jar功能简介

1.2 easyopt.jar导入eclipse

easyopt.jar包导入相关开发环境同其他jar包的导入步骤相同，这里以将easyopt.jar导入eclipse为例进行说明。

Step1： 在eclipse中新建项目；

Step2： 在项目中新建一个文件夹lib；

Step3： 将easyopt.jar粘贴到lib文件夹中，参看图1.1；

图1.1 easyopt.jar包添加进项目lib文件夹

Step4：在项目上点右键，选择Build Path，再选择Configure Build Path，然后在弹出界面中单击“Add JARs”按钮，将本项目中前面粘贴的easyopt.jar加入项目，如图1.2所示。

图1.2 easyopt.jar导入项目

       后续即可直接调用该包中的类和方法，具体参看第三章及其后的说明。

 

 

第二章  车间调度理论基础

2.1 车间调度问题

2.1.1 车间调度问题概述

车间调度所研究的问题是将稀缺资源分配给在一定时间内的不同任务。它是一个决策过程，在大多数制造和生产系统及信息处理环境中扮演着重要的角色。随着生产规模的不断扩大，调度和决策对企业的管理和生产的重要性日渐凸显。好的调度方案可以提高企业的生产水平，使资源利用更合理，并提高市场竞争力。

车间调度问题一般是指在一定时间内，通过可用共享资源的分配和生产任务的排序，来满足指定的性能指标。车间调度问题一般可以描述为：针对某项可以分解的工作（如钢铁加工等），在一定的约束条件下（如工艺次序约束、资源约束、交货期约束等），如何安排其组成部分（工序）所占用的资源（如加工机床、缓冲区等）、加工时间及先后次序，以便使得某项或多项目标（如最大完成时间、总流经时间、等待时间等）最优化。

车间调度问题受多种因素影响，包括：产品的加工次序、车间生产能力、加工设备性能、原料可用性、批量大小、加工成本、产品的投产期和交货期、零等待约束、零空闲约束、设备维修时间约束、模糊时间约束等。上述约束条件中，有些是生产过程中必须满足的，如交货期、生产能力、原材料供应、设备维修、产品加工次序等；有些约束条件则需要达到一定的满意度，如生产成本、批量大小等；另外，还有些约束条件是动态变化的，具有一定的不确定性，如设备故障维修、原材料供应的变化、模糊加工时间等。

车间调度问题的性能指标是评价调度方案优劣的依据，实际车间调度问题涉及的主要性能指标包括生产周期最短、客户满意度最高、设备利用率最高、约束惩罚最小、利润最大化、成本最低等。

 

2.1.2 车间调度问题表示法和分类

在调度问题中，一般存在m台机器(machine) {M₁ ,…，M_m} ,n个工件(Job) {J₁,…， J_n},每个工件有多道工序。一个调度问题通常用三元组α\β\γ来描述，其中：

α描述机器环境；

β提供加工特征和约束的细节，可能包含任何一项，也可能包含多个选项；

γ描述最小化的目标，可以包含一个目标，也可以包含多个目标。

调度问题分类及其标识如表2.1所示。

表2.1调度问题分类及其标识

 

 

 

2.2 常见车间调度问题

2.2.1 并行机调度PMS问题

某车间需要完成n个作业的生产加工，这些作业只需要经过1次操作即可完工，车间配置了m台设备用于进行这些作业的生产加工， 这m台设备的功能基本相同，均可以进行这些作业的生产加工，即这些设备为并行可替换设备，生产管理人员需要确定这n个作业中在m台并行机上的分配， 以及每台设备上所分配作业的加工先后关系，以达成某些运作目标的优化，这个决策问题称之为单阶段并行机调度（Single Stage Parallel Machine Scheduling，SSPMS或PMS）。

现实生产运作系统中，作业可能需要通过多道工序方能完成生产加工，而在作业的某一道或某几道工序中可能存在着 多台可选机器设备，构成了多阶段的、具有并行机的车间调度问题，这一类问题一般归纳到柔性流水车间或柔性作业车间调度问题中，因此，一般并行机研究主要指单阶段并行机。

虽然单阶段并行机看起来作业流程只有一道，好像比较容易进行生产组织， 但是根据现实生产过程中涉及问题的特征和优化目标，该类问题任然具有很强的优化需求。PMS优化过程中可能需要考虑的因素有：作业交货时间due time、作业释放时间release time、作业拆分约束job splitting、加工过程设备是否具有独占性preemptive vs. nonpreemptive、设备是否存在故障、设备前后加工不同类型作业是否存在调整时间setup time、调整时间是否同作业顺序或机器相关sequence-dependent or sequence-independent、作业在不同机器上加工时间是否存在不同heterogeneous、优化目标是完工时间最小makespan还是总拖期最小tardiness等。

2.2.2 置换流水车间调度问题PFSP

流水车间调度问题（Flow Shop Scheduling Problem, FSP）是研究最广泛的生产调度问题之一，具有很强的工程应用背景。研究表明：约有25%的生产制造系统、组装线和服务设施可简化为FSP模型。FSP研究n个工件在m台机器上的流水加工过程。以金属导线生产线为例进行说明：待生产的n个客户订单为生产不同规格的导线，生产过程为铜丝依次经过圆线拉丝、扁线辊压、漆包、换位成型四道工序，客户订单可以看作n个独立的作业，各项作业的加工顺序必须按照严格的先后顺序执行，这就是一个流水车间调度问题。调度优化的目标就是确定这n项订单的先后加工顺序，以达到特定生产绩效指标最优。

一般地，FSP描述为：有n个独立的工件按照相同的工艺路线在m台机器上加工，即每个工件需要经过m道工序，这些工序分别要求不同的机器，并且各工序的加工过程不能中断。

同时假设：（1）所有工件在零时刻都可以加工；（2）机器可以连续工作并且机器之间存在无限大的缓冲区；（3）一个工件不能同时由多台机器加工，一台机器也不能同时加工多个工件；（4）已知各工序的加工时间，工件的准备时间包含在加工时间内或者可以忽略不计。

优化目标是：确定各工件的生产次序，即一个加工序列，使得某项生产指标最优，其中常见的生产指标有最大完成时间、总流经时间和机器闲置时间等。优化最大完成时间有利于提高生产率，优化总流经时间可以均衡地利用生产资源和减小在线库存，而优化机器闲置时间则可提高机器利用率。

图2.1为三个工件、四台机器的流水车间调度甘特图，从图中可以看出，工件 1、2、3的加工顺序都是从机器1到机器4，而且同一工件后道工序的开工时间不能早于其前道工序的完工时间。

图2.1 三工件四机器的流水车间调度甘特图

根据相关文献，以最大完成时间、总流经时间和机器闲置时间为优化目标的FSP分别记为、和。显然，上述问题的解空间规模均为。

通常假设流水车间中所有机器上各个工件的加工次序相同，即只需要考虑n个工件在第一道工序上的排序即可，这些工件在后面的机器上的排序同第一道序的排序完全相同，这类问题称为置换流水车间调度问题（Permutation FSP,PFSP），总的排序选择为个不同的排列。

类似地，可将以最大完成时间、总流经时间和机器闲置时间为优化目标的PFSP分别记为、和。尽管PFSP的解空间远远小于FSP,但已证明和为NP-hard问题。至今没有一个具有多项式计算复杂度的全局优化算法。

2.2.3 零等待流水车间调度问题NWFSP

在炼钢、食品加工、化工和制药等生产制造过程中，加工对象一旦开始加工就不能中断，直到完成其全部工序的操作。例如，在钢铁生产企业的炼钢-连铸生产过程中，为实现热送热装的生产方式，减少钢液在空气中的温降，希望钢液在前后工序间的加工过程零等待。这类作业一旦在第一道工序开工后，后续工序之间不能出现等待的流水车间问题称之为零等待流水车间调度问题（No-Wait Flowshop Scheduling Problem,NWFSP)。

以最大完成时间和总流经时间为优化目标的零等待流水车间调度问题分别记为和。研究表明，当机器数量时，这类调度问题即为NP-hard问题。目前，NWFSP问题及求解算法已成为学术界和工业界共同关注的热点课题。

图2.2  三工件四机器的零等待流水车间调度甘特图

以置换流水车间的三工件、四工序问题为例，如果为零等待调度问题，则其甘特图如图3.2所示，可以看出工件2和工件3为了不在后续的工序出现等待机器空闲情况，在第一道序都推迟了开工时间。

2.2.4 零空闲流水车间调度问题NIFSP

在集成电路、纺织和陶器等许多产品的生产制造过程中，不允许机器停止运转, 这就是所谓的零空闲调度问题。譬如，在采用照相平板印刷法生产集成电路的过程中，所使用的分挡器是一种昂贵的设备，一旦运行是不希望其停止的；陶器滚筒干燥炉的使用过程中要耗费大量的天然气，由于炉中的热惯性较大,其停止和开启都需要几天的时间，因此，在设备运行时，也希望是连续工作的。这类考虑某台设备一旦开工在将全部任务完成之前不能空闲的流水车间调度问题称之为零空闲流水车间调度问题(No-Idle Flowshop Scheduling Problem,NIFSP)。

一般地，NIFSP描述为：有n个独立的工件按照相同的工艺路线在m台机器上加工，即每个工件需要经过m道工序，这些工序分别要求不同的机器，而这些机器一旦开工在将全部作业完成之前不允许空闲，记为：F_m∣perm ,no-idle∣Cmax。

以置换流水车间的三工件、四工序问题为例，如果为零空闲调度问题，则其甘特图如图2.3，可以看出为了实现机器一旦开工则不能空闲的要求，工件1在机器3和机器4上均推迟了开工时间。

图2.3  三工件四机器的零空闲流水车间调度甘特图

2.2.5 阻塞流水车间调度问题BFSP

在化工、钢铁制造和食品加工等许多生产过程中，由于机器中间缓冲区或生产温度的限制，使得工件加工完成后被阻塞在当前机器上，这就是所谓的阻塞流水车间调度问题(Blocking Flowshop Scheduling Problem,BFSP) _o譬如，在化学制造过程中，由于温度的要求，当药品在上游机器上完成后，为了保持此时的高温，应立即离开当前的机器并转向下游机器。但是如果下游机器处于忙的状态，此时药品只能被阻塞在上游机器上。又如，在钢铁制造中，有两个关键的阶段：加热和轧制钢板。铸块在煤坑中加热到很高的温度，被送到轧制钢板磨坊轧制。因为加热设备的停止和开启需要很长时间，为了提高效率和节省成本，所以在设备运行时，希望加工过程是连续的。

一般地，BFSP描述为：有n个独立的工件按照相同的工艺路线在m台机器上加工，工序间不存在存放区，即一个工件在前道设备加工完毕后只有等到后道工序设备空闲方能从前道设备被释放到后道设备，这个等待后道工序空闲的时段前道设备无法从事其他工件的加工。最大完工时间最小化的阻塞流水车间调度问题记为：Fm∣blocking∣Cmax

以置换流水车间的三工件，四工序问题为例，如果为阻塞流水车间调度问题，则其甘特图如下，可以看出由于工序间不存在缓存区，工件2在第一台设备加工结束，工件3在第一台设备、第二台设备和第三台设备上加工结束后都会被阻塞在原有设备上一段时间，以等待后道工序设备空闲，甘特图中由斜线填充的区域。可以看出其生产状态同置换流水车间调度问题的状态存在区别。

图2.4  三工件四机器的阻塞流水车间调度甘特图

2.2.6 混合流水车间调度问题HFSP

 

混合流水车间调度问题（Hybrid Flow Shop Scheduling Problem，HFSP）也称为柔性流水车间调度问题（Flexible Flow Shop Scheduling Problem，FFSP），因为该问题是在FSP基础上增加了柔性，即在m道工序中至少有一道工序的机器数量为两台或多台。HFSP的其他特征如下：

（1）   车间要进行n个批次或n个种类产品的生产；

（2）   这些批次或种类的产品的工艺路径都是相同的，都需要经过m道工序，不同的是不同产品在同一道工序上的加工时间可能不同；

（3）    在m到工序中存在至少一道工序的机器数量为两台或多台，且这些机器性能相同。

优化目标设定为：最大完工时间最小。

按照车间调度问题的三元组表示法，HFSP规范标识为： 。

以最快完工时间的四工件四工序，其中工序2和4分别有两台机器的混合流水车间调度问题为例，绘制甘特图如下，各个工件在工序2和工序4将会选择可以最早开工的机器进行生产，从而缩短总的完工时间。

图2.5  四工件四机器的混合流水车间调度甘特图

2.2.7 作业车间调度问题JSP

作业车间调度（Job Shop Scheduling Problem，JSP）是典型的组合优化问题，其目的是实现资源的合理分配，具体来说，为实现规定的生产目标，依据实际需求，将生产资源实现准确地分配和高效地利用，最终可以提高企业的生产效益，缩短供货周期等。

一般而言，JSP 问题的定义可以通过两个集合来表解释，一个可利用机器集合和一个待加工工件集合，其中每个工件集合又是由若干工序构成的集合，JSP 问题的标准的数学描述为：n个工件J = {1,...,n}在m台机器M= {1,...,m}上完成加工，每个工件需要完成具有前后工序关系的m项操作，每项操作所用的机器事先确定并耗费一定工时，每个操作有且仅有一台可以用来加工的机器，当一个工件的所有工序都完成加工时，则代表着该工件完成加工。

JSP问题可以使用如下示例表所示的数据进行描述，表中涉及四个作业四台机器，每个作业有四道工序，不同作业同一工序所用的机器不同，调度优化是获取各个作业在每台机器上的生产排序，该排序能够满足作业的工序前后约束，并达成某些运作目标的优化，例如完工时间最短等。

表2.2   4*4作业车间调度数据示例表

    示例数据两种排产方案甘特图分别如下2.6（a）和（b）所示，图中纵轴为机器编号，横轴为时间，带颜色的矩形表示操作的工时安排，相同颜色表示同一个作业，图中数字串中：第一个数字为作业编号，第二个工序编号，方括号中两个数字分别为开工和完工时间。可以看出不同排产方案下最早完工时间是不同的，其中图（a）的完工时间为272，图（b）的完工时间为287。

（a）

（b）

图2.6 作业车间调度甘特图

2.3 经验规则算法

2.3.1 经验规则算法简介

经验规则算法也称之为启发式调度算法，该类算法利用面向问题的特定知识和经验产生求解方案，能够在较短时间内得到次优解，除非极少数规模特殊问题或规模比较小的问题，一般情况下规则算法获得的解的质量难以保证。车间调度问题中的基本经验规则算法有：

（1）  FCFS（First come first served）最早到达的作业最先安排【到达时间优先】

（2）  EDD（earliest due date）最早交货期的作业最先安排【交货期早优先】

（3）  SPT（shortest processing time）：处理时间最短的作业最先安排【工时短优先】

（4）  LPT（longest processing time）：处理时间最长的作业最先安排【工时长优先】

（5）  Slack（slack time）：松弛时间最短的作业最先安排，松弛时间=交货期之前剩余时间-剩余加工时间【松弛时间短优先】

（6）  FOPR（fewest operation remaining）：剩余工序数最少的作业最先安排【工序少优先】

（7）  MOPR（most operation remaining）：剩余工序数最多的作业最先安排【工序少优先】

（8）  LSP（least slack per operation）：松弛时间与剩余工序数比值最小的作业最先安排【松弛/工序比小优先】

（9）  CR（critical ratio）：松弛时间与剩余工作日比值小的作业优先。

除了上述经验规则算法之外，还有一些稍微复杂和效率较高的经验规则算法，主要有Johnson算法、CDS算法、Palmer算法、Gupta算法等。

2.3.2 Johnson算法

（1） 算法简介

Johnson算法^[9]是一种解决的方法，它可以在O(nlog(n))时间内求得问题的最优解。

（2）算法计算流程

步骤1：分组，将n个工件根据后续条件分为两组P和Q。若，则将工件j放入组P中；否则，将工件j放入组Q中。

步骤2：排序，将组P中的工件按照递增排序得到部分排列S1,将组Q中的工件按照递减排序得到部分排列S2，则S={S1,S2}为最优排列。

（3）算法计算示例

例 考虑一个7工件的调度问题，其工时数据为

JobId j	1	2	3	4	5	6	7
P[j,1]	8	12	6	11	9	4	5
P[j,2]	6	10	11	5	3	9	6

由步骤1可得集合P={3,6,7} ，Q={1,2,4,5}

由步骤2可得集合S1={6,7,3},S2={2,1,4,5}，所以S={6,7,3,2,1,4,5}位最优生产排序，其最大完成时间为58，详细排产如下：

工序	1	1	1	1	1	1	1	2	2	2	2	2	2	2
作业	6	7	3	2	1	4	5	6	7	3	2	1	4	5
开工时间	0	4	9	15	27	35	46	4	13	19	30	40	46	55
完工时间	4	9	15	27	35	46	55	13	19	30	40	46	51	58

 

2.3.3 CDS算法

（1）CDS简介

CDS方法是Campbell-Dudek-Smith 对Johnson算法的扩展，它可用于对多于两个工序的置换流水车间调度问题进行求解，可在O(mnlog(n))时间内得到Fm|prmu|Cmax的次优解。该方法首先将m台机器分组，产生m-1组F2|prmu|Cmax，再由Johnson算法分别求得各F2|prmu|Cmax的最优排列，然后选择目标值最好的排列为所求结果。

（2）算法步骤

step1 ：将Fm|prmu|Cmax分解为m — 1组F2|prmu|Cmax，各组虚拟机器和加工时间如表2. 5所示。

表2.5虚拟机器和加工时间计算公式

step2：由Johnson启发式算法分别对分组后两台虚拟机器进行的F2|prmu|Cmax调度排序。

step3：根据step2中获取的调度排序生成原问题Fm|prmu|Cmax的最大完成时间，选择具有最小Cmax的排序为最终结果。

（3）计算示例

例 考虑一个阶的,其加工数据为

 

 

由CDS算法的步骤1,得到3个模拟问题的加工数据如下表

由CDS算法的步骤2,得到3个排列：｛4-3-1-5-2｝、｛2-4-1-3-5｝和 ｛4-1-3-5-2｝，其对应的最大完成时间分别为79，80和79。

所以，最终输出排列为= (4-3-1-5-2｝ ,Cmax为79，具体工序时间如下表。

工序	作业	开工时间	完工时间
1	4	0	5
1	3	5	15
1	1	15	26
1	5	26	38
1	2	38	46
2	4	5	14
2	3	15	24
2	1	26	33
2	5	38	47
2	2	47	49
3	4	14	24
3	3	24	37
3	1	37	50
3	5	50	63
3	2	63	71
4	4	24	34
4	3	37	48
4	1	50	62
4	5	63	72
4	2	72	79

 

2.3.4 Palmer算法

（1）Palmer算法简介

Palmer算法是根据作业加工时间构造一个斜度指标，因此也称为斜度指标法，然后根据各作业斜度指标进行排序获得Fm|prmu|Cmax问题的一种次优排序结果，正常情况下，该算法的调度结果不是太好，不如CDS方法。

（2）算法步骤

Step1：按照下式计算所有工件的斜度顺序指标，

Step2：按照s_j非增的顺序排列各工件，所得工件排列即为输出结果。

（3）计算示例

例  考虑一个阶的,其加工数据为

(1)  由步骤1得到工件1、2、3、4和5的斜度指标分别为9,3,7,16，-5，斜度指标以作业1为例进行说明：

其中s1=（2*1-4-1）*11+（2*2-4-1）*7+（2*3-4-1）*13+（2*4-4-1）*12

            =-3*11-1*7+1*13+3*12

            =-33-7+13+36=-40+49=9

(2)  按照斜度指标排序得到排列为=(4,1,3,2,5｝，其最大完成时间为80，可以看出排产结果比CDS差【CDS最大完工时间为79】，具体排产方案如下表

工序	作业	开工时间	完工时间
1	4	0	5
1	1	5	16
1	3	16	26
1	2	26	34
1	5	34	46
2	4	5	14
2	1	16	23
2	3	26	35
2	2	35	37
2	5	46	55
3	4	14	24
3	1	24	37
3	3	37	50
3	2	50	58
3	5	58	71
4	4	24	34
4	1	37	49
4	3	50	61
4	2	61	68
4	5	71	80

 

2.3.5 Palmer算法

（1）算法简介

Gupta是一种修正 Palmer算法，即对斜度指标计算公式进行调整，然后具体获取调度结果。

（2）算法步骤

Step1：按照下式计算每个工件的斜度指标

式中

步骤2：按照s,非减的顺序排列各工件，所得工件排列即为输出结果。

感觉这个算法没啥道理，也许在原文献中能够看出设计这个公式的起因吧。

（3）算法示例

例  考虑一个阶的,其加工数据为

(1)        由步骤1得到工件1、2、3、4和5的斜度指标分别为-0.056,0.1，-0.053，-0.071和0.048。

(2)        按照斜度指标排序得到排列为π={4,1,3,5,2}，其最大完成时间为79，具体调度方案如下：

工序	作业	开工时间	完工时间
1	4	0	5
1	1	5	16
1	3	16	26
1	5	26	38
1	2	38	46
2	4	5	14
2	1	16	23
2	3	26	35
2	5	38	47
2	2	47	49
3	4	14	24
3	1	24	37
3	3	37	50
3	5	50	63
3	2	63	71
4	4	24	34
4	1	37	49
4	3	50	61
4	5	63	72
4	2	72	79

 

2.4 智能优化算法

优化问题是指在满足一定条件下，在众多方案或参数值中寻找最优方案或参数值，以使得某个或多个功能指标达到最优， 或使系统的某些性能指标达到最大值或最小值。优化问题广泛地存在于信号处理、图像处理、生产调度、任务分配、模式识别、自动控制 和机械设计等众多领域。优化方法是一种以数学为基础，用于求解各种优化问题的应用技术。各种优化方法在上述领域得到了广泛应用， 并且已经产生了巨大的经济效益和社会效益。实践证明，通过优化方法，能够提高系统效率，降低能耗，合理地利用资源，并且随着处理对象规模的增加， 这种效果也会更加明显。

在电子、通信、计算机、自动化、机器人、经济学和管理学等众多学科中，不断地出现了许多复杂的组合优化问题。 面对这些大型的优化问题，传统的优化方法（如牛顿法、单纯形法等）需要遍历整个搜索空间，无法在短时间内完成搜索，且容易产生搜索的“组合爆炸”。 例如，许多工程优化问题，往往需要在复杂而庞大的搜索空间中寻找最优解或者准最优解。鉴于实际工程问题的复杂性、非线性、约束性以及建模困难等 诸多特点，寻求高效的优化算法已成为相关学科的主要研究内容之一。

受到人类智能、生物群体社会性或自然现象规律的启发，人们发明了很多智能优化算法来解决上述复杂优化问题，主要包括：模仿自然界生物进化机制的遗传算法；通过群体内个体间的合作与竞争来优化搜索的差分进化算法；模拟生物免疫系统学习和认知功能的免疫算法；模拟蚂蚁集体寻径行为的蚁群算法；模拟鸟群和鱼群群体行为的粒子群算法；源于固体物质退火过程的模拟退火算法；模拟人类智力记忆过程的禁忌搜索算法；模拟动物神经网络行为特征的神经网络算法；等等。这些算法有个共同点，即都是通过模拟或揭示某些自然界的现象和过程或生物群体的智能行为而得到发展；在优化领域称它们为智能优化算法，它们具有简单、通用、便于并行处理等特点。

2.4.1模拟退火算法SA简介

（1）算法简介

模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程 与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数 的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能, 目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

（2）算法基本原理

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大， 而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 根据Metropolis准则，粒子在温度T时趋于平衡的概率为e(-ΔE/(kT))，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。

用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法步骤： 由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值， 算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。 退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

（3）算法流程

模拟退火算法计算流程如下：

Step1：初始温度Temp(充分大)，初始解rt1(是算法迭代的起点)，最多迭代外温次数outLoopNum，降温速度a；

Step2：对k=1, …, inLoopNum进行下列运算：

  Step2.1：产生新解rt2；

  Step2.2：计算增量deltF=F(rt2)-F(rt1)，其中F()为评价函数，即优化问题目标函数的值；

  Step2.3：若deltDist<0则接受rt2作为新的当前解，否则以概率exp(-deltF/Temp)接受rt2作为新的当前解；

Step3：利用Temp=a*Temp降低温度，其中a取值范围(0,1)；

Step4：判断是否满足算法终止条件（连续N个温度计算后没能获得更好的解），满足则输出当前解作为最优解，结束程序；不满足继续Step2。

图 模拟退火算法流程图

 

2.4.2遗传算法GA简介

（1）算法简介

遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出, 该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型， 是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物 进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好 的优化结果。1975年, J. Holland等提出了对遗传算法理论研究极为重要的模式理论,出版了专著《自然系统和人工系统的适配》, 在书中系统阐述了遗传算法的基本理论和方法,推动了遗传算法的发展。20世纪80年代后,遗传算法进入兴盛发展时期， 当前，遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

（2）算法基本原理

遗传算法是一种基于自然选择和群体遗传机理的搜索算法,它模拟了自然选择和自然遗传过程中的繁殖、杂交和突变现象. 再利用遗传算法求解问题时,问题的每一个可能解都被编码成一个“染色体”,即个体,若干个个体构成了群体(所有可能解). 在遗传算法开始时,总是随机的产生一些个体(即初始解),根据预定的目标函数对每一个个体进行评估,给出一个适应度值, 基于此适应度值,选择一些个体用来产生下一代,选择操作体现了“适者生存”的原理,“好”的个体被用来产生下一代, “坏”的个体则被淘汰,然后选择出来的个体,经过交叉和变异算子进行再组合生成新的一代,这一代的个体由于继承了上一代的一 些优良性状,因而在性能上要优于上一代,这样逐步朝着最优解的方向进化.因此,遗传算法可以看成是一个由可行解组成的群体初步进化的过程。

（3）算法流程

遗传算法计算流程如下：

Step1：初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

Step2：个体评价：计算群体P(t)中各个个体的适应度。

Step3：选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代 或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。]

Step4：交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

Step5：变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。 群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

Step6：终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

（4）算法要点

编码：由于遗传算法不能直接处理问题空间的参数,因此必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。 这一转换操作就叫做编码，也可以称作（问题的）表示（representation）。针对不同的问题需要选用合适的编码方式，常见的编码方式 有：二进制编码、整数编码、实数编码等。

终止条件：当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时， 或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。

操作算子：遗传操作包括以下三个基本遗传算子(genetic operator):选择(selection)；交叉(crossover)；变异(mutation)。

选择算子：从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(reproduction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过 配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，常用的选择算子有以下几种： 适应度比例方法、随机遍历抽样法、局部选择法。

交叉算子：在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的 是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力 得以飞跃提高。

变异算子：变异算子的基本内容是对群体中的个体串的某些基因位上的基因值作变动。 遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。

 

2.4.3蚁群算法ACO简介

（1）算法简介

蚁群系统(Ant System或Ant Colony System)是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。 他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现， 蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走， 而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。

蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过 相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于 1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法 具有许多优良的性质。

（2）算法基本原理

将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。 路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。 最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

  蚂蚁找到最短路径要归功于信息素和环境，假设有两条路可从蚁窝通向食物，开始时两条路上的蚂蚁数量差不多： 当蚂蚁到达终点之后会立即返回，距离短的路上的蚂蚁往返一次时间短，重复频率快，在单位时间里往返蚂蚁的数目就多，留下的信息素也多， 会吸引更多蚂蚁过来，会留下更多信息素。而距离长的路正相反，因此越来越多的蚂蚁聚集到最短路径上来。

  蚂蚁具有的智能行为得益于其简单行为规则，该规则让其具有多样性和正反馈。在觅食时，多样性使蚂蚁不会走进死胡同而无限循环， 是一种创新能力；正反馈使优良信息保存下来，是一种学习强化能力。两者的巧妙结合使智能行为涌现，如果多样性过剩，系统过于活跃， 会导致过多的随机运动，陷入混沌状态；如果多样性不够，正反馈过强，会导致僵化，当环境变化时蚁群不能相应调整。 退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

（3）算法流程

蚁群算法计算流程【以TSP问题为例】如下：

step1：对相关参数进行初始化，包括蚁群规模、信息素因子、启发函数因子、信息素挥发因子、信息素常数、最大迭代次数等， 以及将数据读入程序，并进行预处理：比如将城市的坐标信息转换为城市间的距离矩阵。

step2：随机将蚂蚁放于不同出发点，对每个蚂蚁计算其下个访问城市，直到有蚂蚁访问完所有城市。

step3：计算各蚂蚁经过的路径长度Lk，记录当前迭代次数最优解，同时对路径上的信息素浓度进行更新。

step4：判断是否达到最大迭代次数，若否，返回步骤2；是，结束程序。

step5：输出结果，并根据需要输出寻优过程中的相关指标，如运行时间、收敛迭代次数等。

（4）算法要点

蚂蚁数量：设n表示城市数量，m表示蚂蚁数量。m的数量很重要，因为m过大时，会导致搜索过的路径上信息素变化趋于平均， 这样就不好找出好的路径了；m过小时，易使未被搜索到的路径信息素减小到0，这样可能会出现早熟，没找到全局最优解。一般上，在时间等资源条件紧迫的情况下，蚂蚁数设定为城市数的1.5倍较稳妥。

信息素因子：信息素因子反映了蚂蚁在移动过程中所积累的信息量在指导蚁群搜索中的相对重要程度，其值过大，蚂蚁选择以前走过的路径概率大， 搜索随机性减弱；值过小，等同于贪婪算法，使搜索过早陷入局部最优。实验发现，信息素因子选择[1,4]区间，性能较好。

启发函数因子：启发函数因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度，其大小反映的是蚁群寻优过程中先验性和确定性因素的作用强度。 过大时，虽然收敛速度会加快，但容易陷入局部最优；过小时，容易陷入随机搜索，找不到最优解。实验研究发现，当启发函数因子为[3,4.5]时，综合求解性能较好。

信息素挥发因子：信息素挥发因子表示信息素的消失水平，它的大小直接关系到蚁群算法的全局搜索能力和收敛速度。实验发现，当属于[0.2，0.5]时,综合性能较好。

信息素常数：这个参数为信息素强度，表示蚂蚁循环一周时释放在路径上的信息素总量，其作用是为了充分利用有向图上的全局信息反馈量， 使算法在正反馈机制作用下以合理的演化速度搜索到全局最优解。值越大，蚂蚁在已遍历路径上的信息素积累越快，有助于快速收敛。 实验发现，当值属于[10,1000]时，综合性能较好。

最大迭代次数：最大迭代次数值过小，可能导致算法还没收敛就已结束；过大则会导致资源浪费。一般最大迭代次数可以取100到500次。 一般来讲，建议先取200，然后根据执行程序查看算法收敛的轨迹来修改取值。。

 

2.4.4粒子群优化PSO简介

（1）算法简介

粒子群优化(Particle Swarm Optimization, PSO)算法是Kennedy和Eberhart受人工智能研究结果的启发、 通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法，自然界中各种生物体均具有一定的群体行为， 而人工智能的主要研究领域之一是探索自然界生物的群体行为，从而在计算机上构建其群体模型。自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣， 生物学家Craig Reynolds在1987年提出了一个非常有影响的鸟群聚集模型，在他的仿真中，每一个个体遵循： （i）避免与邻域个体相冲撞； （ii）匹配邻域个体的速度； （iii）飞向鸟群中心，且整个群体飞向目标。 仿真中仅利用上面三条简单的规则，就可以非常接近的模拟出鸟群飞行的现象。1995年，美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出了粒子群算法， 其基本思想是受对鸟类群体行为进行建模与仿真的研究结果的启发。他们的模型和仿真算法主要对Frank Heppner的模型进行了修正，以使粒子飞向解空间并在最好解处降落。

（2）算法基本原理

PSO从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。 所有的粒子都有一个由被优化的函数决定的适值( fitness value) ，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO初始化随机初始化一群随机粒子，每个粒子表示问题的一个解，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己： （1）粒子本身所找到的最好解，即个体极值(pbest) （2）整个粒子群中所有粒子在历代搜索过程中所达到的最优解(gbest)即全局极值。 找到这两个最好解后，接下来是PSO中最重要的“加速”过程，每个粒子不断地改变其在解空间中的速度，以尽可能地朝pbest和gbest所指向的区域“飞”去。

（3）算法流程

粒子群算法的计算流程如下：

Step1：根据变量个数N和粒子数量pop，利用rand函数生成二维数组X[pop, N]和速度数组V[pop, N]

Step2：利用适应度函数求得各个X的解fit[pop]，记录每个粒子的最好解particleBest[pop]和群体的最好解groupBest，并记录对应的解集particleBestX[pop,N]

Step3：运用迭代公式更新X和V，再继续Step2，直至结束。

  参数有动能惯性系数、个体学习系数、群体学习系数、种群规模、最大迭代代数、无更新终止代数。

 

2.4.5教学算法TLBO简介

（1）算法简介

Rao2016开发了一种使用简单，不需要任何算法参数调试的教学算法Teaching Learning Based Optimization（TLBO）。TLBO算法描述了两种基本的学习模式：（i）通过教师学习，（ii）通过与其他学生交互的学习，这两个模式分别命名为教师阶段和学习者阶段。此算法包含一群学生，并给每个学生安排了不同的课程，这些课程为优化问题的设计变量，学生的成绩类似于优化问题的适应度。学生群体的最好学习结果被视为教师。 设计变量其实是优化问题目标函数中包含的参数，最优结果是目标函数的最优结果。

（2）算法基本原理

基于教学的优化（TLBO）是一种模拟课堂教学过程的基于群体的优化方法。TLBO分为两部分。第一部分是“教师阶段”，即向教师学习； 第二部分是“学习者阶段”，即通过学习者之间的互动进行学习。在TLBO中，种群被视为一类学习者。每个学习者代表优化问题的一个可能的解决方案， 分数代表适应度值。老师被认为是迄今为止得到的最好的解决办法。

（3）算法流程

教学算法的计算流程如下：

Step1：数据初始化

Step2：种群初始化-也就是班级的学生初始化，类似于遗传算法中的染色体种群初始化

  这里采用实数编码的形式进行编码，实数数量=sum(作业工序数)，有多少作业工序就有多少个实数变量。加入有作业A1、A2、B1、B2、B3， 即有两个作业A和B，分别有2个和三个工序，则编码长度为5，由5个实数组成，实数取值范围限定在[0,b]之间，通常将其限定在[0,1]之间， 当然b也可以设定一个比较大的正整数，例如10，如果形成了一个如下的编码：

   8.6434 1.6972 0.8544 2.0878 1.1762

  则根据数字的大小进行解码，最小的为A1、次之A2、……、最大的代表B3，则上述实数编码转换为作业编码如下：

   B3 B1 A1 B2 A2

Step3：循环运算

  Step3.1：识别群体中最好的学生和计算班级各科平均成绩

  Step3.2：根据公式(1)、(2)、(3)更新全部学生的全部科目成绩；

  Step3.3：随机选择两个学生，然后利用公式(6)和(7)进行一个学生的成绩更新；

  Step3.4：算法终止条件成立否，如成立，则执行Step4；否则执行Step3.1，继续循环

Step4：算法结束，进行统计和给出结果。

    注：其中的公式请参考Rao2016年出版的书籍《Teaching Learning Based Optimization Algorithm And Its Engineering Applications》。

 

 

 

 

第三章  easyopt.chart包中类和方法的使用

3.1 easyopt.chart包结构

easyopt.chart包中主要包含了车间智能调度优化计算中所涉及的图形展示类和方法。easyopt.chart包中的类及其功能如下表。

 

3.2 GantChart类及其使用

GantChart类主要封装了根据调度数据绘制甘特图的方法，其构造函数如下：

例（1）：假设车间有调度方案如下表所示，使用GantChart类绘制对应的甘特图。

jobId	machId	procId	startTime	endTime
1	1	1	0	13
2	2	1	0	27
3	3	1	0	16
4	1	1	13	36
1	2	2	27	41
2	3	2	27	46
3	1	2	36	49
4	2	2	41	46
1	3	3	46	58
2	1	3	49	59
1	2	4	58	75

代码设计如下：

执行结果如下图所示：

    在上述甘特图中，如果鼠标进入对应的色块，将采取比较具体的方式显示该色块详细调度信息，鼠标离开该色块，则使用简要方式显示该色块的详细调度信息。

3.3 OptSeriesChart类及其使用

OptSeriesChart类主要封装了用于绘制优化算法寻优进化曲线的方法，其构造函数如下：

public OptSeriesChart(double[][] optSeriesArr) 参数:  optSeriesArr - row is the quantity of samples[points], column is the quantity of series

例（1）：假设采用特定优化算法对某个完工时间最小的车间调度问题优化求解，在进化前20代记录的当前代最优解如下表，

generation	1	2	3	4	5	6	7	8	9	10
fitVal	809	760	728	581	669	521	618	586	545	551
generation	11	12	13	14	15	16	17	18	19	20
fitVal	497	493	480	528	450	323	386	396	324	387

    程序设计如下：

package easyopt.example; import easyopt.chart.OptSeriesChart; public class Example_Chart_OptSeriesChart {     public static void main(String[] args) {        double[][] optData= {{809},{660},{728},{581},{669},{521},{618},{586},{545},{551},{497},{493},{480},{528},{450},{323},{386},{396},{324},{387}};        OptSeriesChart optChart=new OptSeriesChart(optData);        optChart.drawLine();     } }

执行结果如下图所示：

在上述收敛曲线中，绿色线条为截止当前代数的最优解，红色为当前代计算的最优解，如果鼠标进入对应代数的纵轴范围，将显示进化到该代数时对应的当前代数最优解和截止当前代数的全局最优解。

例（2）：假设当前有两种优化算法对同一问题进行优化求解，这两种算法前20步算法的最优结果如下表所示，试利用OptSeriesChart绘制进化曲线图。

generation	1	2	3	4	5	6	7	8	9	10
fitVal1	852	764	641	674	703	715	674	719	662	683
fitVal2	925	898	666	639	586	584	538	544	599	577
generation	11	12	13	14	15	16	17	18	19	20
fitVal1	718	659	654	584	559	549	475	486	505	521
fitVal2	501	533	612	544	591	598	559	505	453	436

    程序设计如下：

package easyopt.example; import easyopt.chart.OptSeriesChart; public class Example_Chart_OptSeriesChart {     public static void main(String[] args) {        double[][] optData= {{852,925},{764,898},{641,666},{674,639},{703,586},{715,584},{674,538},{719,544},{662,599},{683,577},{718,501},{659,533},{654,612},{584,544},{559,591},{549,598},{475,559},{486,505},{505,453},{521,436},{503,453}};        OptSeriesChart optChart=new OptSeriesChart(optData);        optChart.drawLine();         } }

程序执行结果如下：