交货期窗口待定情况下的平行机排序问题  

A scheduling problem on parallel machines with an undetermined due window

作　　者：赵洪銮[1] 韩国勇[2] 

机构地区：[1]山东大学数学与系统科学学院,山东济南250100 [2]济南铁道职业技术学院信息工程系,山东济南250013

出　　处：《山东大学学报（工学版）》2006年第5期99-101,共3页Journal of Shandong University（Engineering Science）

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

摘　　要：考虑多个工件在平行机上加工的生产调度问题,这些工件相互独立且有相同的交货期窗口,但交货期窗口的位置待定,其目标是最小化提前和延误的赋权工件数及交货期窗口定位费用的和.本文给出了这个强NP-困难问题的一个多项式时间近似序列(PTAS).The scheduling problem of several independent jobs is considered to be processed on some parallel machines with a due window. But the window location is undetermined. The strongly NP-hard and polynomial time approximation scheme （PTAS） was proposed to minimize the weighted number of early and tardy jobs together with the window location penalty.

关 键 词：平行机 交货期窗口 提前 延误 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O157[自动化与计算机技术—计算机科学与技术]