摘要
探讨退化工件两台机器自由作业环境下的最小化加权误工工件的排序问题,其中所有工件具有相同的公共交货期。首先证明了最小化误工工件数问题是NP困难的;然后对最小化加权误工工件数问题给出了一个拟多项式时间算法;最后对几种特殊情形给出了多项式时间算法。
This paper studies the problem of scheduling proportionally deteriorating jobs in two-machine open shop to minimize the number of tardy jobs, in which all jobs have the common due date. We first show that the unweighted problem is NP-hard, then we present a pseudo-polynomial-time algorithm for the weighed problem, and finally we develop polynomial algorithms to solve several special cases.
出处
《佛山科学技术学院学报（自然科学版）》
CAS
2014年第6期7-11,共5页
Journal of Foshan University(Natural Science Edition)
基金
国家自然科学基金数学天元基金项目(11326191)
国家自然科学基金项目(11401604
11401605)
河南省基础与前沿技术研究计划项目(132300410392)
河南省教育厅自然科学研究计划项目(14A110027)
关键词
排序
自由作业
退化工件
NP-
困难性
scheduling
open shop
deteriorating jobs
NP-hardness
scheduling
open shop
deteriorating jobs
NP-hardness
