多工作日历下流水作业调度遗传优化方法
|
摘要
针对多工作日历下的流水作业调度问题,提出了一种遗传优化方法。首先,提出了基于多工作日历的时间推算方法,解决了多工作日历下流水作业调度的关键问题:以Excel为平台设计了"工作制"工作表和"设备"工作表,在"设备"工作表中为每台设备指定工作制并设定工作时段;在此基础上,以Excel VBA为平台设计了5个基于工作日历的时间推算函数。其次,以Excel VBA为平台设计了遗传算法用于求解问题:个体采用整数编码方式,交叉操作采用"交换交叉"方式,变异操作采用"交换变异"方式,解码过程采用基于多工作日历的时间推算方法准确计算各工序开工和完工时刻。最后,通过案例分析验证了所提方法的有效性。
For the Flow Shop Scheduling Problem(FSP)under multiple work calendars, this paper proposes an optimization scheduling method based on Genetic Algorithm(GA). Firstly, a time reckoning method based on multiple work calendars is given as a critical technology to solve the researched problem:Worksheets"work system"and"machine"are designed by Excel. The work system and work time periods are specified to each machine in the worksheet"machine". On above basis, five time reckoning functions based on the machine's work calendar are designed by Excel VBA. Secondly, a genetic algorithm is developed to solve the problem by Excel VBA. In the algorithm, an integer coding method is used to code the individuals, a swapping method is used in the crossover and mutation operation, and the above time reckoning method based on multiple work calendars is used to calculate start time and end time of each operation accurately. Finally, the effectiveness of the proposed method is validated by case study.
For the Flow Shop Scheduling Problem(FSP)under multiple work calendars, this paper proposes an optimization scheduling method based on Genetic Algorithm(GA). Firstly, a time reckoning method based on multiple work calendars is given as a critical technology to solve the researched problem:Worksheets"work system"and"machine"are designed by Excel. The work system and work time periods are specified to each machine in the worksheet"machine". On above basis, five time reckoning functions based on the machine's work calendar are designed by Excel VBA. Secondly, a genetic algorithm is developed to solve the problem by Excel VBA. In the algorithm, an integer coding method is used to code the individuals, a swapping method is used in the crossover and mutation operation, and the above time reckoning method based on multiple work calendars is used to calculate start time and end time of each operation accurately. Finally, the effectiveness of the proposed method is validated by case study.
引文
[1]金锋,宋士吉,吴澄.基于大规模FSP问题Block性质的SA算法[J].系统工程与电工技术,2007,29(1):49-52.
[2]陈荣秋.求同顺序m×n排序问题近优解的一个新算法--关键工件法[J].管理现代化,1983(1):14-16.
[3]叶飞帆,李国富,周昌乐.一种基于Hopfield模型的流水作业排序方法[J].中国管理科学,1998,6(3):39-43.
[4]陈玉旺,杨根科.混合FlowShop的调度仿真系统及其算法分析[J].系统仿真学报,2004,16(10):2161-2164.
[5]王大志,刘士新,郭希旺.求解总拖期时间最小化流水车间调度问题的多智能体进化算法[J].自动化学报,2014,40(3):548-555.
[6]金锋,宋士吉,吴澄.一类基于FSP问题Block性质的快速TS算法[J].控制与决策,2007,22(3):247-251.
[7]张晓霞,吕云虹.一种求解混合零空闲置换流水车间调度禁忌分布估计算法[J].计算机应用与软件,2017,34(1):270-274.
[8]Wang Chuyang,Li Xiaoping,Wang Qian.Tabu search for no-wait flow shop scheduling problem to minimize maximum lateness[J].Journal of Southeast University,2010,26(1):26-30.
[9]梅宏标,王坚.变异蚁群优化算法在流水作业排序中的应用[J].计算机工程与应用,2007,43(24):216-219.
[10]梁德赛,吴兆福.求解流水车间调度问题改进的蚁群算法研究[J].华中师范大学学报(自然科学版),2014,48(3):330-334.
[11]潘逢山,叶春明.生产调度干扰管理模型构建及智能算法研究[J].工业工程与管理,2012,17(3):85-89.
[12]亓祥波,朱云龙,南琳,等.面向铝挤压的作业排产优化[J].信息与控制,2016,45(5):621-626.
[13]刘兰兰,张曦煌,陈志国.确定型流水车间调度的遗传算法研究[J].计算机工程与应用,2016,52(12):227-230.
[14]轩华,秦莹莹,王薛苑,等.带恶化工件的PFS调度的混合遗传算法[J].工业工程与管理,2017,22(3):1-6.
[15]周鑫,马跃,胡毅.求解车间作业调度问题的混合遗传模拟退火算法[J].小型微型计算机系统,2015,36(2):370-374.
[16]丁勇,姜枫,武玉艳.遗传算法在公交调度中的应用[J].计算机科学,2016,43(11A):601-603.
[2]陈荣秋.求同顺序m×n排序问题近优解的一个新算法--关键工件法[J].管理现代化,1983(1):14-16.
[3]叶飞帆,李国富,周昌乐.一种基于Hopfield模型的流水作业排序方法[J].中国管理科学,1998,6(3):39-43.
[4]陈玉旺,杨根科.混合FlowShop的调度仿真系统及其算法分析[J].系统仿真学报,2004,16(10):2161-2164.
[5]王大志,刘士新,郭希旺.求解总拖期时间最小化流水车间调度问题的多智能体进化算法[J].自动化学报,2014,40(3):548-555.
[6]金锋,宋士吉,吴澄.一类基于FSP问题Block性质的快速TS算法[J].控制与决策,2007,22(3):247-251.
[7]张晓霞,吕云虹.一种求解混合零空闲置换流水车间调度禁忌分布估计算法[J].计算机应用与软件,2017,34(1):270-274.
[8]Wang Chuyang,Li Xiaoping,Wang Qian.Tabu search for no-wait flow shop scheduling problem to minimize maximum lateness[J].Journal of Southeast University,2010,26(1):26-30.
[9]梅宏标,王坚.变异蚁群优化算法在流水作业排序中的应用[J].计算机工程与应用,2007,43(24):216-219.
[10]梁德赛,吴兆福.求解流水车间调度问题改进的蚁群算法研究[J].华中师范大学学报(自然科学版),2014,48(3):330-334.
[11]潘逢山,叶春明.生产调度干扰管理模型构建及智能算法研究[J].工业工程与管理,2012,17(3):85-89.
[12]亓祥波,朱云龙,南琳,等.面向铝挤压的作业排产优化[J].信息与控制,2016,45(5):621-626.
[13]刘兰兰,张曦煌,陈志国.确定型流水车间调度的遗传算法研究[J].计算机工程与应用,2016,52(12):227-230.
[14]轩华,秦莹莹,王薛苑,等.带恶化工件的PFS调度的混合遗传算法[J].工业工程与管理,2017,22(3):1-6.
[15]周鑫,马跃,胡毅.求解车间作业调度问题的混合遗传模拟退火算法[J].小型微型计算机系统,2015,36(2):370-374.
[16]丁勇,姜枫,武玉艳.遗传算法在公交调度中的应用[J].计算机科学,2016,43(11A):601-603.