返回
类型 基础研究 预答辩日期 2017-11-28
开始(开题)日期 2015-06-12 论文结束日期 2017-08-28
地点 计算机楼313 论文选题来源 973、863项目     论文字数 9 (万字)
题目 带有学习与恶化效应的任务调度优化方法
主题词 成组任务调度,多机任务调度,学习效应,恶化效应,非周期性维护
摘要 加工时间不确定性广泛存在于制造系统,也是影响调度性能和生产效率的关键因素之一。在冶炼、机械加工、食品加工等行业,学习效应和恶化效应是两种重要的主观不确定性因素,缩短或增长任务加工时间,降低调度结果的鲁棒性。通常大部分具有学习与恶化效应的单机调度是$P$问题,可证明其多项式时间可解性;由于具有学习与恶化效应的部分单机和绝大部分多机调度为$NP$难问题,任务位置或者累积加工时间产生动态变化的任务加工时间,导致传统的精确算法、启发式或元启发式调度算法不能有效求解。考虑几种典型方法学习与恶化效应的任务调度问题,研究其加工时间规律,提出适合的调度算法,论文的主要创新点如下: (1)带有学习和恶化效应的单机任务调度:分析现有的任务变化函数,构造出符合实际应用场景具有学习效应的任务变化函数和具有学习和恶化效应的抽象任务变化函数;交换同一序列中两个相邻任务顺序得到两个不同任务序列,构造出两个序列的目标函数表达式,分析并推导相应的变化函数性质,证明了目标函数分别为最小化最大完工时间、最小化完工时间和及最小化完工平方和的单机任务调度问题多项式时间可解;证明了目标函数分别为最小化加权完工时间和、最小化最大延迟时间、最小化最大滞后时间、最小化滞后时间和的单机任务调度问题在一定条件下多项式时间可解。 (2)最小化最大完工时间带有恶化效应的单机成组任务调度优化:分析具有恶化效应的单机成组任务调度的特性,基于时间序列分析方法构造了基于开工时间的恶化效应函数;考虑加工过程中任务可中断条件,通过增加维护时间以减少恶化时间,推导了具有恶化效应的目标函数最优解性质,提出两种启发式求解算法。实验表明两种算法求解小规模实例效果较好,但对于大规模问题性能较差。分析并推导最小化最大完工时间的目标最优解性质,构建快速计算算子,提出快速迭代局部搜索算法:分别基于两个启发式算法和一个随机算法产生初始解,提出基于插入邻域结构的局部搜索方法,当集中性达到一定程度时对选择出的候选解进行扰动,是否接受扰动产生的新解由接受准则确定;算法满足停止条件时停止,返回最优解。采用方差分析方法分别测定恶化因子、扰动算子等最优算法参数和算法组件,通过标准实例集验证所提出算法的性能。 (3)带有学习效应的流水任务调度优化:分析具有学习效应流水任务调度的特征,构造更符合实际情况的学习效应随任务变化的函数,采用交换邻域算子生成新序列,推导生成序列的目标函数表达式,分析函数性质。提出两种特殊流水任务调度问题不同优化目标的算法。理论上证明了以最小化最大完工时间、最小化完工时间和、最小化完工平方和等为优化目标的特殊流水调度问题多项式时间可解;而以最小化加权完工时间和、最小化最大延迟时间、最小化最大滞后时间、最小化滞后时间和等为优化目标的特殊流水调度问题在一定条件下多项式时间可解。
英文题目 OPTIMIZATION METHODS FOR TASK SCHEDULING WITH LEARNING AND DETERIORATING EFFECTS
英文主题词 Group task scheduling, Machine scheduling, Learning effects, Deteriorating effects, Non-periodical maintenance
英文摘要 Nondeterministic of processing times is widespread in manufacturing systems which is one of the key factors on scheduling performance and production efficiency. Learning and deteriorating effects are two important nondeterministic factors in many industries, especially in metallurgical processing, manufacturing and food industries. The robustness of scheduling algorithms are heavily deteriorated by decreased or increased processing times. Generally single machine scheduling problems with learning and/or deteriorating effects could be optimally solved with polynomial time complexities. Because some single machine and majority of multiple machine scheduling problems are $NP$ hard, processing times are dynamic depending on task positions or sum of processing times which result in traditional exact methods, heuristics or metaheuristics are unsuitable for these problems. Some task scheduling problems with learning and deteriorating effects are considered in this dissertation. The major contributions are shown below. (1)Single machine task scheduling with learning and deteriorating effects. Functions between normal processing times and the actual ones are analyzed. A more practical function with learning effects and a general function with learning and deteriorating effects are constructed. Two adjacent tasks in a sequence are exchanged to generate two new sequences. Objective variation functions of the two sequences are constructed. Properties are analyzed and derived. The single-machine problems with learning effects to minimize makespan, total completion time and total square completion time are proved to be polynomial solvable respectively. In addition, optimal solutions could be found single-machine problems with learning and deteriorating effects to minimize the sum of weighted completion times, the maximum lateness, the maximum tardiness and the total tardiness under agreeable situations. (2) Single machine group task scheduling with deteriorating effects to minimize makespan. The problem is described and modeled as a function with time-dependent deteriorating effects by the time series analysis technique. Tasks are assumed to be interruptible. The increasing of maintenance times could lead to the decrease of deteriorating effects. The incremental properties for objective functions with deteriorating effect are derived. Two efficient heuristics are proposed for small size problems. Moreover, an iterated algorithm is presented for large size problems which includes for components: initial solution generation, local search, perturbation and the acceptance criterion. Initial solutions are constructed by the two heuristics and a random sequence construction method respectively. Initial solutions are improved by an insertion-based local search method. When intensification is strong enough, the current solutions are perturbed and the new current solution is selected from the generated candidate solutions. Whether the current solution is replaced by the newly selected or not is decided by the acceptance criterion. The algorithm stips when the terminal criterion is satisfied and the best solution is returned. The analysis of variance technique is adopted to calibrate the involved parameters and algorithm components and to evaluate results among the compared methods. (3) Special multiple stage job scheduling with learning effects. Characteristics of the considered problem are analyzed. The processing time function of a task between its normal processing time and its actual time is developed which is more practical. The function is affected by learning and deteriorating effects as well as task stage. A pair of adjacent jobs in a sequence are exchanged and two different sequences are constructed. Properties of the variation function are analyzed and derived. The special multiple stage job problems with learning and deteriorating effects to minimize makespan, total completion time and total square completion time are proved to be polynomial solvable respectively. In addition, optimal solutions could be found for special multiple stage job problems with special learning and deteriorating effects to minimize the sum of weighted completion times, the maximum lateness, the maximum tardiness and the total tardiness under agreeable situations.
学术讨论
主办单位时间地点报告人报告主题
东南大学 2015年6月2日 计算机楼350 徐海燕 An Iterated Greedy Algorithm for Group scheduling with time-dependent deteriorating effect
东南大学 2014年12月24日 计算机楼350 徐海燕 Group scheduling for complex products with time-dependent deteriorating effect
东南大学 2015年6月12日 计算机楼301 徐海燕 带有学习和恶化效应的任务调度优化方法
东南大学 2016年10月18日 计算机楼350 徐海燕 Group scheduling with non-periodical maintenances and deteriorating effects
东南大学 2013年3月25日 计算机楼301 Prof.Sam Kwong Adaptive operator selection with bandits for multi-objective evolutionary algorithm based on decomposition
东南大学 2016年4月20日 计算机楼350 陈龙 Workflow scheduling with spot instances
东南大学 2016年11月8日 计算机楼350 王爽 Performance analysis of heterogeneous servers in cloud centers
东南大学 2017年3月8日 计算机楼350 王雅娣 Gene Selection with Overlapping Group lasso
     
学术会议
会议名称时间地点本人报告本人报告题目
IEEE International Conference on Computer Supported Cooperative Work in Design. 2015年5月6日 Calabria, Italy An Iterated Greedy Algorithm for Group scheduling with time-dependent deteriorating effect
第10届全国计算机支持的协同工作学术会议 2015年8月29日 山西太原 Optimal methods for virtual machine scheduling with uncertain execution times in cloud
     
代表作
论文名称
A memory-based complete local search method with variable neighborhood structures for no-wait job s
基于学习和恶化效应模型的单机调度
Group Scheduling for Complex Products with Time-dependent Deteriorating Effect
 
答辩委员会组成信息
姓名职称导师类别工作单位是否主席备注
周晓峰 正高 教授 博导 河海大学
蒋嶷川 正高 教授 博导 东南大学
曹玖新 正高 教授 博导 东南大学
秦小麟 正高 教授 博导 南京航空航天大学
张宏 正高 教授 博导 南京理工大学
      
答辩秘书信息
姓名职称工作单位备注
朱夏 副高 副教授 东南大学