离散加工时间单机多准则下可控排序问题  

Multi-rule single machine scheduling with discretely controllable processing times

作　　者：王吉波[1] 郭爱霞[1] 夏尊铨[1] 

机构地区：[1]大连理工大学应用数学系

出　　处：《大连理工大学学报》2007年第3期465-468,共4页Journal of Dalian University of Technology

基　　金：教育部博士学科点专项科研基金资助项目(20020141013);沈阳航空工业学院科研基金资助项目(05YB08)

摘　　要：讨论了工件具有离散可控加工时间的单机多准则下的排序问题.目标函数分别为极小化完工时间和与完工时间偏差和的线性组合,极小化等待时间和与等待时间偏差和的线性组合,极小化提前时间、延误时间、最早交货期及窗口长度的加权和,极小化提前时间、延误时间及公共工期的加权和.用数学规划的方法证明了四类多准则下的单机排序问题可以转化为指派问题,从而这四类问题都多项式时间可解.Multi-rule single machine scheduling problems with discretely controllable processing times are considered. The objectives are to minimize a linear function of total completion time and total variation of completion time, a linear function of total waiting time and total variation of waiting time, a cost function based on earliness, tardiness, window size, window location, and a linear function of the due date, the earliness and tardiness for all jobs. It is shown that these four types of single machine scheduling problems can be modeled as an assignment problem by mathematical programming method, thus these four types of problems can be solved in polynomial time.

关 键 词：排序 单机 离散加工时间 多准则 

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