运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2006年
2期
37-45
,共9页
运筹学%排序%时间区间%额外加工费%NP-hard%算法
運籌學%排序%時間區間%額外加工費%NP-hard%算法
운주학%배서%시간구간%액외가공비%NP-hard%산법
Operation research%scheduling%time window%extra operation cost%NP-hard%algorithm
考虑一个单机排序问题:一批工件在零时刻到达可加工,加工时不可中断,在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时,要求确定一个最优加工序,当时间区间为决策变量时,要求找到一个最优序及最优区间位置,由此来最小化总额外加工成本.文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法,NP-hardness的证明及伪多项式时间算法.
攷慮一箇單機排序問題:一批工件在零時刻到達可加工,加工時不可中斷,在某箇給定時間區間外的加工工時將招緻額外的加工成本;噹時間區間為給定參數時,要求確定一箇最優加工序,噹時間區間為決策變量時,要求找到一箇最優序及最優區間位置,由此來最小化總額外加工成本.文中對各種區間外單位加工工時之額外成本的情況給齣瞭多項式算法,NP-hardness的證明及偽多項式時間算法.
고필일개단궤배서문제:일비공건재령시각도체가가공,가공시불가중단,재모개급정시간구간외적가공공시장초치액외적가공성본;당시간구간위급정삼수시,요구학정일개최우가공서,당시간구간위결책변량시,요구조도일개최우서급최우구간위치,유차래최소화총액외가공성본.문중대각충구간외단위가공공시지액외성본적정황급출료다항식산법,NP-hardness적증명급위다항식시간산법.
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.
