带固定工件的单机排序问题1|FB,r_j,pmtn|Σ_jU_j的多项式算法(英文)  

Single Machine Preemptive Scheduling with Fixed Jobs and Release Dates to Minimize the Total Number of Tardy Jobs

作　　者：万国华[1,2] 孙磊[2] 

机构地区：[1]上海交通大学安泰经济与管理学院,上海200052 [2]深圳大学管理学院,深圳518060

出　　处：《运筹学学报》2009年第2期11-17,共7页Operations Research Transactions

基　　金：Supported in part by NSF of China(70372058);Guangdong NSF Grant(031808)

摘　　要：研究具有若干固定工件和自由工件,其中固定工件必须在指定时间窗内加工,而自由工件具有不同交工的时间,并且其加工可以中断的单机排序问题,其目标是极小化工件的误工数.该问题可以表示为1|FB,r_j,pmtn|∑_jU_j.首先讨论了问题的几个重要性质,以此为基础建立了求解该问题的动态规划算法,其时间复杂度为O(n^4+mlog m),其中m和n分别是固定工件数和自由工件数.A single machine scheduling problem with fixed jobs is considered, where the fixed jobs have to be scheduled in pre-specified time windows while the other jobs, called free jobs, have distinct release dates and are allowed to be preempted. The objective of the problem is to minimize the total number of tardy jobs. This problem can be denoted as 1｜FB, rj,pmtn｜∑j Uj. Several important properties of optimal solutions are discussed. Based on these properties, a dynamic program algorithm with time complexity O（n^4 ＋ mlog m） is developed to solve the problem, where rn and n are the numbers of fixed and free jobs, respectively.

关 键 词：运筹学 排序 单机 延误工件数 交工时间 固定工件 中断抢先 多项式算法 

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