论文部分内容阅读
考虑一个单机排序问题：一批工件在零时刻到达可加工，加工时不可中断，在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时，要求确定一个最优加工序，当时间区间为决策变量时，要求找到一个最优序及最优区间位置。由此来最小化总额外加工成本．文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法。NP—hardness的证明及伪多项式时间算法。