带有交货期和加工时间可控的单机排序问题  

Single Machine Scheduling with Date of Delivery Assignment and Controllable Processing Times

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

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

出　　处：《重庆师范大学学报（自然科学版）》2013年第3期5-8,共4页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.10471096)

摘　　要：讨论了带有交货期和工件的加工时间可控的单机排序问题。本文首先根据最优排序的性质确定了最优资源的分配方法,并将问题转化为指派问题,通过构造多项式时间算法确定最优排序。然后,本文将学习效应与加工时间可控问题结合,分别讨论了加工时间是线性资源函数和凸资源函数两种情况,证明了该类问题是多项式时间可解的。最后,讨论了一种特殊情况(学习因子是常数,加工时间是凸资源函数),给出了复杂性为O(nl ogn)的算法,通过运行此算法确定最优资源分配量和工件的最优排序。We consider date of delivery assignment and single-machine scheduling problems in which the jobs have controllable pro- cessing times. We determine the optimal resource allocation by using the properties of the optimal sequence, and formulate problem as a set of assignment problem, provide a polynomial time algorithrn. Then, we combine the effects of learning with controllable processing times, processing time is a linear resource function or convex resource function, we show that the problems can be solved in polynomial time. Finally, we consider a special case （learning factor is a constant, processing time is a convex resource function）, we give an algorithm that the time complexity is O（nlog n）, we determine the optimal resource allocation and the optimal sequence by running the algorithm.

关 键 词：排序 单台机器 交货期指派 加工时间可控 资源分配 

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