# GeneticAlgorithm-JSP

**Repository Path**: noodles-zgh/GeneticAlgorithm-JSP

## Basic Information

- **Project Name**: GeneticAlgorithm-JSP
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2020-11-12
- **Last Updated**: 2024-09-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 排程生产任务

## 项目介绍：

### 实现的排程算法：遗传算法

### 实现的排程策略：

1. 超交货期越少越好，分两种情况：

    * 按超过的天数越小，加权越小，即结果越好。

    * 按超期的任务数量越少越好。

2. 设备利用率越高越好。

### 实现的排程规则：

* 正排

* 倒排

## 项目思路：

以“任务信息.csv”中第15-25行为例，任务可按318->319->320->321->322->323->324->325->326->226779顺序执行，也可按327->226779顺序执行。
两条任务链在226779时交汇，即开始任务226779之前需要先完成326和327两个任务。
我将这两条任务链分为318->319->320->321->322->323->324->325->326、327、226779三条任务链，用JobRelationship类存储这三条任务链的关系。

在进行遗传算法时，每一次生成一个新的染色体，会先检查它是否符合上述的前后关系。
染色体是一个整型数组，数字代表任务链的序号，相同数字代表它们属于同一任务链，所以先后关系并不是指一条任务链之间的任务的先后关系（如318和319），而是指不同任务链之间的可能的先后关系（如318和226779）。
在“变异”阶段，如果被选出准备交换的两个基因位有先后关系，会重新选；
在“交叉”阶段，如果被选出的一段准备交叉的基因片段中含有一对基因有先后关系（前驱基因、后继基因），会检查基因片段之后的基因，找出其中的最末尾的属于与前驱基因是同一任务链的基因，将它与后继基因互换位置，以保持基因的先后关系。

计算计划开始、结束时间（即遗传算法中的适应度）时，按照以下规定：

1. 将一个任务的耗时分为准备时间和总运行时间，总运行时间为该任务数量*单次运行时间。
后继任务在前驱任务开始前可以先进行准备，当前驱任务结束并且准备完成时，后继任务开始运行。表中的计划开始时间指任务开始准备的时间。

2. 虚拟设备组（58、59）内有无限个设备可用。

#### 遗传算法过程：

1. **初始化**一定数量的染色体（基因）。

2. 分别对每个基因**计算适应度**。

3. 按变异概率，**变异**其中的随机某个基因：
交换染色体中两个随机位置上的值，得到新解。

4. 按交叉概率，随机选择两条基因，**交叉**产生新基因：
从已有的两条染色体中，其中一条取出一部分，组合进另一条的相同位置。

5. 找出所有基因中的**适应度最高**的那个作为结果。

## 排程参数：

```
public static int POSITIVE_ORDER=1, REVERSE_ORDER=2;    // 正序为1，倒序为2
private final int planedTime = 15000;   // 所有任务预完成时间
private int strategy, order;  // 排程策略及排程规则

private final int hourPerDay = 16;  // 一天工作多少小时
private final int finalMissionLen = 2*hourPerDay*60; // 六位数任务的时间，单位：分钟。此处为两天
private final String paichengTime = "2020.8.2"; // 排程时间

private final int populationNumber = 10;    // 遗传算法初始染色体个数
private final double mutationProbability = 0.05;    // 变异概率
private int mutateTime=2;  // 变异次数
private int selectNumber=3; // 选择时的选择个数
```

## 输入及输出：

### 输入：

1. 任务信息.csv

2. 设备信息.csv

### 输出：

* 任务结果.csv：填充了“任务信息.csv”中“设备”、“计划开始时间”、“计划结束时间”、“排程时间”四列。
其中“计划开始时间”、“计划结束时间”都为该子任务开始时间距离总开始时间的分钟数。
“排程时间”预设为2020年8月2日，可在程序中修改`paichengTime`的值来更改。

前四行：

|任务|预完成时间|运行时间|设备组|任务数量|后继任务|准备时间|设备|计划开始时间|计划结束时间|排程时间|
|:-----|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|
|226750|26880|0.0|-1|2|-1|0|0|0.00|1920.00|2020.8.2|
|226735|26880|0.0|-1|2|-1|0|0|0.00|1920.00|2020.8.2|
|308| |0.44|46|6|309|90|145|0.00|92.64|2020.8.2|
|309| |2.0|43|6|310|90|198|364.65|466.65|2020.8.2|

* 设备结果.csv：填充了“设备信息.csv”中“占用时间”列。

前四行：

|设备|设备组|占用时间|
|:-----|-----:|-----:|
|11|2|2234.70|
|25|2|540.00|
|72|2|340.44|
|68|2|338.52|

* gantt.jpg：各个任务链的甘特图。一条横线代表一条任务链中所有任务。

在生成甘特图时，由于无法自定义一天工作多少小时，我按照`任务时长/16*24`把甘特图中的任务转换成一天工作24小时，避免显示错误。
这个设置不会影响csv中的结果。

## 使用方法：

* 在main()中可修改：输入输出文件名。

```
String missionFilename = "F:/任务信息.csv";
String machineFilename = "F:/设备信息.csv";
String missionOutput = "任务结果.csv";
String machineOutput = "设备结果.csv";
```

* 生成的甘特图的名字：这里用的是生成图片时的时间。示例：在5点50分生成的图片文件名为`gantt-5-50.jpg`

```
Calendar c=Calendar.getInstance();
String ganttFilename = "F:/gantt-"+c.get(Calendar.HOUR) + "-" + c.get(Calendar.MINUTE)+".jpg";
```

* 然后运行main()。

* 依赖库：lib中的`SwiftGantt`，用于生成甘特图。

## 遇到的问题：

1. 有一条任务链不论怎么排都会超时，所以排程策略1（超过的天数），由于超过的天数固定了，无法看出其余任务是否是最优解。任务链中的任务为：`1478->1479->1480->1481->1482->1483->1484->1485->1486->1487->226592`。
而按照排程策略2（超时任务个数），由于只有上面这一条任务链超时，别的都在预定时间内完成，也无法看出是否是最优解，我修改预订时间后，才可以看出。

2. 倒排结果的各任务时长会比正序长，截止提交时还未弄清原因。