带学习效应和恶化效应的单机排序问题

作     者：韩春梅 

作者单位：苏州大学 

学位级别：硕士

导师姓名：闻振卫

授予年度：2020年

学科分类：07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：排序 单机 学习效应 恶化效应 截断参数 

摘      要：排序理论是组合优化的一个重要分支.现代排序问题已经广泛运用到如生产调度、运输管理、医疗手术安排等许多领域中.现代排序问题中,工件的加工时间常常是随工件的开工时刻、加工位置以及所分配的资源量等因素影响的变数,另外,机器可以带有维护活动.在C.C.Wu,H.Y.He,L.Liu等人研究的加工时间带有学习效应并含截断参数的单机排序问题的基础上,进行拓展,本文研究更具一般形式的带有学习效应并含截断参数或者带有恶化效应并含截断参数的排序问题,更加贴近现实.本文主要讨论以下三类带截断参数的单机排序问题:(1)第二章探究一种新的更具一般化的带学习效应并含截断参数的单机排序问题,其中工件的加工时间与工件所排的加工位置有关.讨论目标函数分别为极小化时间表长、总和完工时间、加权总和完工时间以及最大延迟等四个排序问题.通过精心构造相应的辅助函数成功地得出了按照pj不减的顺序排列可以得到目标函数为极小化时间表长的排序问题的最优排序的结论,并分别给出了这些排序问题的多项式时间算法.(2)第三章提出了一种工件带有两道工序的新的单机排序问题,其中工件两道工序的加工时间都带有截断参数并与所分配的资源量呈凸函数关系.研究在三种不同工期窗口类型(common window、slack window、different window)下的目标函数分别为极小化三种不同加权和形式的排序问题.通过深入地分析和一系列地理论推导,成功地将排序问题的核心子问题转化为指派问题,从而分别给出了这些排序问题的多项式算法.(3)第四章,在第三章中部分加工时间模型的基础上增加与开工时刻有关的恶化效应,得到的一种新的加工时间模型,研究带有一次机器维护活动的排序问题.首先,考虑机器维护时长是常数的排序问题,排序的目的是分别求在三种新的不同加权和形式的目标函数下的最优维护位置和最优排序.其次,考虑机器维护时长是与位置有关的变数的排序问题,排序的目的是,在资源约束的条件下,求最优工期、最优维护位置和最优排序,使加权和形式的目标函数最小.通过将排序问题的核心子问题转化为指派问题,从而给出了排序问题的多项式算法.