一个不同时刻加工成本有差异的单机排序问题

摘要

This paper addresses a scheduling problem of n jobs available at time zero on a single machine, in which any preemption is prohibited and any processing time unit out of a time window with given length incurs some extra operation payment for each job. The aim is to minimize the total extra processing expenditure of these n jobs. Two scenarios of this problem are investigated: one where the position of that time window is a specified parameter and the other where it is also a decision variable. For all types of extra cost,polynomial and pseudopolynomial algorithms are developed respectively. Moreover the NP-hardness on a complicated case is proved.%考虑一个单机排序问题:一批工件在零时刻到达可加工,加工时不可中断,在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时,要求确定一个最优加工序,当时间区间为决策变量时,要求找到一个最优序及最优区间位置,由此来最小化总额外加工成本.文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法,NP-hardness的证明及伪多项式时间算法.