带有学习效应和加工时间可控的排序问题  

Scheduling problems with controllable processing times and learning effects

作　　者：范雁鹏[1] 赵传立[1] 

机构地区：[1]沈阳师范大学数学与系统科学学院,沈阳110034

出　　处：《沈阳师范大学学报（自然科学版）》2014年第2期192-196,共5页Journal of Shenyang Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(61070242)

摘　　要：考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。The authors consider single-machine due-window assignment and scheduling with learning effect and controllable job processing times.The processing time of a job is either a linear or a convex function about the amount of resource that allocated to the job in a sequence.We assume each job has a due window and the size of due-window is identical to all the jobs in a sequence.Jobs completed prior to the starting time of the due-window or after its completion time are penalized and jobs completed within the due-window are not penalized.The objective is to minimize a total penalty function including earliness,the number of tardy jobs,due-window and resource consumption costs and determine the optimal sequence,the optimal processing time and the optimal resource allocation.For the case that processing time is a linear resource function,the author reduce the problem to a set of assignment problems and give a polynomial time algorithm; For the case that processing time is a convex resource function,we provide a dynamic program algorithm and show that the algorithm can be solved in polynomial time.

关 键 词：排序 学习效应 加工时间可控 交货期窗口 动态规划算法排序 

分 类 号：O223[理学—运筹学与控制论]