自由作业稠密时间表的性质研究  

Study of Properties of Dense Schedules for Open-shop

作　　者：陈荣军[1,2] 唐国春[2] 

机构地区：[1]常州工学院数学系,江苏常州213022 [2]上海第二工业大学管理工程研究所,上海201209

出　　处：《数学的实践与认识》2009年第5期166-173,共8页Mathematics in Practice and Theory

基　　金：国家自然科学基金重大国际(地区)合作研究项目(70731160015);江苏省教育厅项目(yw06037);江苏省"青蓝"工程资助

摘　　要：稠密时间表作为自由作业问题的近似解,其加工总长与最优值之比具有上界2-1/m(m为机器数),是一个尚未证明的猜想.利用组合方法证明了稠密时间表性能比猜想成立的一个充分条件.利用该条件及有关文献的结果,给出了机器数不超过7的自由作业稠密时间表性能比猜想的证明.Dense schedules can be used as heuristic solutions for open-shop makespan problem. It is conjectured that a dense schedule will result in a makespan no more than （2-1—m） times of the makespan from the optimal schedule where m is the number of machines. By combinatorial method, we provide a sufficent condition that make the conjecture hold and with this condition, give the complete proofs for the conjecture for m≤ 7.

关 键 词：自由作业 加工总长 稠密时间表 性能比 

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