返回
类型 基础研究 预答辩日期 2018-01-12
开始(开题)日期 2015-09-08 论文结束日期 2017-11-28
地点 东南院305 论文选题来源 国家自然科学基金项目     论文字数 6 (万字)
题目 时间可控的生产调度模型与优化算法研究
主题词 生产调度,可控时间,优化算法,指派问题,维护活动
摘要 对任务安排、服务提供和零件加工等过程进行排序优化的调度理论,在管理决策领域存在着大量的应用,能产生巨大的社会经济效益。经典调度理论中总是假设工件参数是固定不变的,而且机器在整个调度周期内的运行状态也不会发生改变。但管理决策者目前面临的复杂生产过程和客户多样化的需求,使得调度优化问题的研究对象也相应的发生变化。工件的时间参量可以发生改变,机器运行也可能需要中断一段时间来进行诸如保养维护、工具更换、效率调整等活动。而此时工件/机器参数往往是可控的,针对这一新的变化,本文主要研究含可控时间参量的生产调度问题及相应的优化算法。 首先,本文研究了带资源依赖的释放时间的单机调度问题。每一工件一旦释放即开始进行加工,其释放时间与假定的初始释放时间存在偏差即会产生释放成本。需要确定工件序列和所有工件的释放时间,使得释放成本、时间表长和总完工时间的加权和总成本目标函数最小。考虑了两种情形:情形一是初始释放时间是限制性的,它是$\mathcal{NP}$难问题;另一情形是初始释放时间为非限制性的,它是多项式时间可解问题,时间复杂度为$O(n\log n)$。 其次,基于实际应用中出现的涉及可控且可变加工时间的调度问题,本文研究了含资源依赖和位置依赖的工件加工时间的单机问题。在资源指派导致的压缩加工时间基础上,在实际加工时间中综合考虑了一般位置依赖的学习/老化效应。资源消费函数是线性函数或是凸函数,在每一种情况中,讨论了两个目标函数。其中之一包含时间表长、流水时间、总完工时间偏差和总压缩成本,另外一个包含提前、延后、提交时间和总压缩成本。分析表明:它们都能在时间复杂度$O(n^3)$内求解,而对于凸目标函数情形中的一种特殊情况,有时间复杂度$O(n\log n)$的算法。 再次,具有资源分配或机器可得性约束的调度是非常重要的,最近受到了广泛的关注。本文考虑了工作可控性与机器可得性这两种现象同时存在时,它们之间的协调关系。假定安排凸资源依赖的工件在含一个不可得区间的单机上加工。涉及了时间表长和总资源消费两个目标函数。目标是寻找最优工件调度和资源指派,使得在一个目标不超过给定上界的约束下,最小化另一目标函数。分析表明,每一问题都是 $\mathcal{NP}$难问题。 提供了启发式算法,并分析了它们的最坏情况性能比。 接着,本文研究了含特殊线性可压缩加工时长的同型机情境下的时间表长问题。每一工件通过消费额外的资源,其加工时间都是可压缩的,且总压缩量有限制。在资源消费量足够时,工件的加工时间甚至可以减少至零。给出了所考虑问题的复杂度和MIP模型。在经典平行机时间表长问题的简单调度规则基础上,提供了两个启发式算法:LS-压缩方法和LNPT-压缩方法。并提供了依赖于工件参数的最坏情况误差界。 然后,本文研究了含凸资源依赖加工时间的平行机调度问题,涉及一般位置依赖的工作负荷。由于含资源指派调度问题与许多实际生产情况相适应,因而越来越受到调度研究者的关注。考虑平行机环境及其特殊情况的单机环境,以及两个目标函数:总调度成本和资源消费成本。根据机器环境、资源消费函数和目标函数的不同,共讨论了八类问题。结论显示,每一问题的最优解都可以通过有效的多项式时间算法获得。 之后,本文研究了带机器维护且维护时长是退化且可控的单机问题。假设维护时长是依赖于其开始时间和消费的额外资源量。目标是确定工件序列、维护活动位置和它的额外资源消费量,使得与绩效指标和资源消费成本有关的总成本最小。考虑的绩效指标分别为:时间表长、流水时间、最大延误和提前、延误及提交时间的组合。分析结论表明,所有四个问题都是多项式时间可解的,并提供了对应的优化算法。 最后,本文研究了共同提交时间窗指派的单机调度问题,同时考虑一般位置依赖的加工时间和退化且可压缩的维护活动。讨论了与效率调整维护活动有关的两个模型,即维护长度假定为依赖于开始时间和可压缩的或依赖于位置和可压缩的两种情形。目的是找寻工件提交时间窗的位置和大小、维护位置以及指派给它的资源量和工件序列,使得含提前、延误、提交时间窗位置和大小及资源成本的总成本函数最小。结果表明,两个模型对应的问题都可以归结为多项式时间可解的指派问题。 总之,工件特征/机器环境的改变使得工件/机器参数不仅可变,且是可控的。与之相适应的生产调度模型与优化算法研究,进一步丰富了调度决策理论,拓展了它的应用领域。
英文题目 Research on production scheduling models and optimization algorithms with controllable time
英文主题词 production scheduling,controllable time, optimization algorithm,assignment problem,maintenance activity
英文摘要 The scheduling theory for the procession sequencing optimization of tasks arrangement, service provision and parts processing has a large number of applications in the field of management decision making, which can produce huge social and economic benefits. In the classical scheduling theory, it is assumed that the job parameters are fixed constants and performance of the machine will not change during the whole scheduling horizon. However, the complex production process and customers’ diversified demand faced by management decision maker make the object of study in scheduling field change correspondingly. The time parameters of the jobs can be changed, and the machine may also need to be interrupted for a period of time for maintenance, tool change, rate-modifying and other activities. At the same time, the parameters of the jobs/machine are always controllable. In view of this new change, this paper mainly studies the production scheduling problem with controllable time parameters and the corresponding optimization algorithm. Firstly, single machine scheduling problems with resource-dependent release times is studied. Each job starts as soon as it is released and release cost will be generated if its actual release time deviates from the supposed initial release time. The objective is determining a sequence of jobs in addition to their release times concurrently, in order that weighted release cost, makespan and total completion times of jobs are minimized. Two cases are considered, in which the problem with restricted initial release time is N P-hard and the problem with unrestricted initial release time is polynomially solvable in O(n log n) time by efficient algorithm with the analysis of optimality properties. Secondly, single machine scheduling problems with resource- and position-dependent job precessing times is studied, since such scheduling problems involving controllable but variable processing times can be found in many real-life applications. Based on the compressed processing times resulting from resource allocation, general position-dependent learning/aging effects are integrated in the actual processing times. The resource consumption function is either linear or convex and in each case two objective functions are considered. One is to minimize a cost function containing makespan, flow time, total absolute differences in completion times and total compression cost, another is to minimize a cost function containing earliness, tardiness, due-date and total compression cost. We present that each problem can be optimally solved in O(n 3 ) time. We also present that a special case of the problem in convex model can be solved in O(n log n) time. Thirdly, scheduling problems with either resource allocation or machine availability constraint is important and has received much attention recently. The coordination between job controllability and machine availability is considered when these two phenomena exist simultaneously. It is assumed that convex resource-dependent jobs are scheduled on a single machine with an given unavailable time-window. Two objectives, namely the makespan and the total resource consumption, are concerned. The goal is to find an optimal job schedule and resource allocation for each job such that one objective is minimized under the constraint that another objective does not exceed a given upper bound. It is shown that each problem under consideration is N P-hard. Heuristics are developed and their worst-case performance ratios are analyzed. Next, the makespan problem on identical parallel machines with special linearly compressible processing times is studied. The processing time of a job is compressible by using additional resource and the total compression amount is limited. It is assumed that each job processing time is reducible even to zero with enough resource consumption. Complexity and a MIP model for the considered problem are presented. Based on the analysis of simple scheduling rules about the classic makespan problem on aprallel machines, two heuristics, namely LS-Compression and LNPT-Compression, are proposed. Moreover, the worst-case error-bounds are shown to evaluate the performances of the two heuristics. Then, Scheduling problems with convex resource-dependent processing times involving position-dependent workloads are studied. More and more attention is paid to the scheduling problems with resource allocation, since it is in line with many real situations of production. Two machine settings, namely parallel machines and single machine, and two objective functions, namely the total scheduling cost and resource consumption cost, are concerned. Eight variants of problem are discussed, which differ in either the machine setting, the resource consumption function, or the objective function. It is shown that the optimal solution of each problem under consideration can be obtained by polynomial time algorithm. And then, scheduling problems with a deteriorating and resource-dependent maintenance activity on a single machine is investigated. The duration of the maintenance is assumed to be dependent both on its starting time and on the resource allocated to it. The objective is determining the job sequence, the position to perform a maintenance activity and the amount of additional resource allocated to it such that the total cost of related measure and resource is minimized. The measures considered are the makespan, flowtime, maximum tardiness and combination of earliness, tardiness and due-date. Analysis results show that all the considered problems are polynomially solvable, and the corresponding optimization algorithms are provided. Finally, common due-window assignment and scheduling problems with general position dependent processing times involving deteriorating and compressible maintenance activity on a single-machine are considered. Two models associated with rate-modifying maintenance activity are examined, in which the duration of maintenance is assumed to be either time-dependent and compressible or position-dependent and compressible. The objective is to find jointly the location and size of due-window, position of maintenance as well as resource amount allocated to it and job sequence to minimize a total cost function based on earliness, tardiness, window location, window size and resource cost. It is shown that the problem considered in each of the two models’ setting can be optimally solved with polynomial time algorithm by reducing to assignment problem. In conclusion, the change of the job feature/machine environment makes the job/machine parameters not only variable but controllable. The corresponding study of production scheduling models and optimization algorithms which adapts to it further enrich the scheduling theory of decision making and extend its application areas.
学术讨论
主办单位时间地点报告人报告主题
东南大学经济管理学院 2014年10月22日 纪忠楼Y-111 朱辉 Notes on “Some single-machine scheduling problems with a truncation learning effect”
东南大学经济管理学院 2015年10月26日 纪忠楼-213 朱辉 Single machine scheduling problem with controllable release times
东南大学经济管理学院 2015年11月3日 纪忠楼Y-110 朱辉 Single machine scheduling with deteriorating
东南大学经济管理学院 2015年12月24日 纪忠楼Y-214 朱辉 Minimizing the makespan on parallel machines with compressible
东南大学经济管理学院 2016年4月6日 纪忠楼Y-214 严磊 基于广告定向能力的媒体平台竞争策略研究
东南大学经济管理学院 2016年4月8日 经管楼B201 刘歆 Distributed Optimization Approaches for Big Data Problems
东南大学经济管理学院 2016年5月10日 纪忠楼Y-213 钱萍萍 考虑交货时间差异的双渠道广告与价格策略研究
东南大学经济管理学院 2016年6月6日 经管楼B204 丁超 大数据科学中的矩阵优化
     
学术会议
会议名称时间地点本人报告本人报告题目
江苏省系统工程学会第十四届学术年会 2015年10月30-11月1日 江苏徐州中国矿业大学 Single machine scheduling with deteriorating and controllable maintenance activity
2016年全国排序论和组合最优化学术会议 2016年4月22日-24日 陕西西安西北工业大学 Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity
     
代表作
论文名称
Due-window assignment and scheduling with general position-dependent processing times involving a de
Machine scheduling with deteriorating and resource-dependent maintenance activity
Note on single machine scheduling problems with resource-dependent release times
Single-Machine Scheduling Problems with Variable Processing Times and Delivery Times Involving Doubl
 
答辩委员会组成信息
姓名职称导师类别工作单位是否主席备注
刘洪 正高 教授 博导 南京大学
谢乃明 正高 教授 博导 南京航空航天大学
张玉林 正高 教授 博导 东南大学
李东 正高 教授 博导 东南大学
吕鸿江 正高 教授 博导 东南大学
      
答辩秘书信息
姓名职称工作单位备注
鞠传静 其他 讲师 东南大学