CAJ | 학술논문

研究了一类单台机上带有库存约束的排序问题，目标函数是极小化加权完工时间总和。针对问题，首先证明了问题是NP－困难的，接着给出贪婪算法，证明了该算法的最坏情况界是无穷大，但随机试验表明算法的平均性能是令人满意的。
연구료일류단태궤상대유고존약속적배서문제，목표함수시겁소화가권완공시간총화。침대문제，수선증명료문제시NP－곤난적，접착급출탐람산법，증명료해산법적최배정황계시무궁대，단수궤시험표명산법적평균성능시령인만의적。
This paper considers a single-machine scheduling problem subject to inventory constraints, the objective is to minimize the total weighted completion time.For this problem, both an NP-hardness proof and a greedy algorithm are provided.It's proved that the algorithm is unbounded in the sense of worst case, but computational experiments show that it performances good in the average sense.