CAJ | 학술논문

探讨退化工件两台机器自由作业环境下的最小化加权误工工件的排序问题，其中所有工件具有相同的公共交货期。首先证明了最小化误工工件数问题是 NP 困难的；然后对最小化加权误工工件数问题给出了一个拟多项式时间算法；最后对几种特殊情形给出了多项式时间算法。
탐토퇴화공건량태궤기자유작업배경하적최소화가권오공공건적배서문제，기중소유공건구유상동적공공교화기。수선증명료최소화오공공건수문제시 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.