基于剩余率求解非标准作业车间调度问题逆序算法

摘要/Abstract

摘要： 为了克服现有效率算法、遗传算法和逆序算法等求解非标准作业车间调度问题时存在的不足，提出了一种新的逆序算法。将非标准作业车间调度问题进行数学描述，给出目标函数，针对非标准作业车间调度问题的复杂性，构造了一种基于剩余率函数的逆序调度算法，以确定出最佳的开工日期。与其他算法相比，该算法的复杂性更小，调度结果更优。

关键词: 作业车间调度, 交货期, 目标函数

Abstract: To overcome shortcomings in current efficiency algorithm, genetic algorithm and reverse algorithm existing in non-standard job-shop scheduling problem, a reverse algorithm of solving Nonstandard Job-Shop Scheduling Problem (NJSSP) based on redundancy was put forward, The mathematical description of NJSSP was provided, object function was also given simultaneously. To deal with complexity of NJSSP, a reverse algorithm for solving NJSSP based on redundancy was constructed in order to define optimal staring time of every job. Compared with the other algorithm, the new algorithm has lower complexity and better scheduling result.

Key words: job-shop scheduling, due dates, objective function

中图分类号:

TP278

陈冬雪，王宏欣. 基于剩余率求解非标准作业车间调度问题逆序算法[J]. .

CHEN Dong-xue, WANG Hong-xin. Reverse algorithm for solving nonstandard job-shop scheduling problem based on redundancy[J]. .

参考文献

[1]ZOMAYA A Y. Special issue:part 1 scheduling:theory and applications[J]. International Journal of Foundations of Computer Science, 2001,12(5):559-564.

[2]BRIZUELA C A，NOBUO S. From the classical job shop to a real problem:a genetic algorithm approach[A].Proceedings of the 39th IEEE Conference on Decision and Control［C］. Sydney，Australia,2000.4174-4180.

[3]WANG L, ZHENG D Z. A modified genetic algorithm for job shop scheduling[J]. International Journal Manufacturing Technology,2002, （20）:72-76.

[4]IMED K,SLIM H, PIERRE B. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, and Cybernetics——Part C:Applications and Reviews，2002,32(1):1-13.

[5]WANG Haiying, WANG Fengru, LIU Qifeng. Solving nonstandard job-shop scheduling problem with due dates using bounding genetic algorithm[A]. Proceedings of the 3rd Word Congress on Intelligent Control and Automation［C］.Hefei:Press of University of Science and Technology of China,2000.

[6]WANG Fengru, XU Weiwen, WANG Fenglin. Genetic algorithm based on sequence & value encoding and its application[J]. Electric Machines and Control,2001，5（1）：64-68(in Chinese).[王凤儒，徐蔚文，王凤林．基于序值编码的遗传算法及应用[J]．电机与控制学报，2001，5(1):64-68.]

[7]WANG Fengru, XU Weiwen, XU Hongfu. Solving nonstandard job-shop scheduling problem by efficience scheduling algorithm[J]. Computer Integrated Manufacturing Systems，2001，7（7）：12-15（ in Chinese）.[王凤儒，徐蔚文，徐洪副.用效率调度算法求解非标准作业车间调度问题[J].计算机集成制造系统，2001，7（7）：12-15.]

[8]KANG Ning,WANG Fengru, LIU Pi’e,et al.The reverse algorithm of job-shop scheduling problem with due dates[J]. Systems Engineering—Theory & Practice，1999，19（12）：25-30(in Chinese).[康宁，王凤儒，刘丕娥，等.有交货期的单件车间调度问题的逆序算法[J]．系统工程理论与实践，1999，19（12）：25-30.]

[1]	杨艳华,姚立纲. 基于时间递推建模及交叉熵算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(6): 1703-1713.
[2]	段建国,李豪晨,张青雷. 面向绿色制造的半组合式船用曲轴结构件生产车间多目标调度优化[J]. 计算机集成制造系统, 2021, 27(6): 1714-1727.
[3]	詹欣隆,张超勇,孟磊磊,连裕翔,薛燕社. 面向高效低碳的切削参数与柔性作业车间调度集成建模与优化[J]. 计算机集成制造系统, 2021, 27(12): 3519-3535.
[4]	连裕翔,张超勇,孟磊磊,薛燕社,詹欣隆,吕畅. 基于改进Jaya算法的柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(11): 3172-3184.
[5]	薛玲玲. 作业车间调度的块结构邻域搜索遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2848-2857.
[6]	罗焕,陈浩杰,宋小欣,张剑. 带有缓存约束的作业车间调度求解方法[J]. 计算机集成制造系统, 2021, 27(10): 2880-2888.
[7]	娄航宇,张吉善,赵云博. 基于扩展双资源约束型航空构件制造车间调度方法[J]. 计算机集成制造系统, 2020, 26(12): 3329-3340.
[8]	巴智勇,袁逸萍,戴毅,李晓娟,阿地兰木·斯塔洪,刘金朵. 考虑机器故障的作业车间调度方案鲁棒测度方法[J]. 计算机集成制造系统, 2020, 26(12): 3341-3349.
[9]	孟磊磊,张超勇,肖华军,詹欣隆,罗敏. 面向加工时间可控的柔性作业车间节能调度问题建模[J]. 计算机集成制造系统, 2019, 25(第5): 1062-1074.
[10]	吴秀丽,刘夏晶. 差分进化算法求解分布式柔性作业车间调度问题[J]. 计算机集成制造系统, 2019, 25(第10): 2539-2558.
[11]	肖华军,柴子力,张超勇,孟磊磊,任亚平,梅慧文. 基于混合化学反应算法的柔性作业车间调度[J]. 计算机集成制造系统, 2018, 24(第9): 2234-2245.
[12]	吴秀丽,孙阳君. 机器多转速的柔性作业车间绿色调度问题[J]. 计算机集成制造系统, 2018, 24(第4): 862-875.
[13]	范华丽,熊禾根,蒋国璋,李公法,李梓响. 基于遗传规划的动态作业车间调度规则生成[J]. 计算机集成制造系统, 2018, 24(第4): 876-885.
[14]	李聪波,雷焱绯,肖溱鸽,沈欢. 面向广义能耗的柔性作业车间调度优化模型[J]. 计算机集成制造系统, 2018, 24(第12): 3050-3059.
[15]	赵诗奎. 柔性作业车间调度的改进邻域结构混合算法[J]. 计算机集成制造系统, 2018, 24(第12): 3060-3072.