重庆师范大学学报（自然科学版）
重慶師範大學學報（自然科學版）
중경사범대학학보（자연과학판）
JOURNAL OF CHONGQING NORMAL UNIVERSITY（NATURAL SCIENCE EDITION）
2013年
6期
17-21
,共5页
排序%单机%交货期窗口%拒绝工件%接受工件
排序%單機%交貨期窗口%拒絕工件%接受工件
배서%단궤%교화기창구%거절공건%접수공건
scheduling%single machine%due-window%rejected job%accepted job
讨论了带有交货期窗口和工件可拒绝的单机排序问题,这一问题是将所有的工件分成两个集合,一个是被接受的工件集,一个是被拒绝的工件集.假设被接受的每个工件都有一个待定的交货期窗口,且所有工件的交货期窗口的大小是相同的,如果工件在窗口中完工,则不产生任何费用;否则工件提前或延误,会产生相应的提前或延误的费用.而对于拒绝工件而言,它的费用只与工件有关.这类问题的总费用是2个工件集的费用之和.目标函数是确定被接受工件的最优排序,极小化总费用,给出了一个动态规划算法,并证明了这个问题是多项式时间可解的.
討論瞭帶有交貨期窗口和工件可拒絕的單機排序問題,這一問題是將所有的工件分成兩箇集閤,一箇是被接受的工件集,一箇是被拒絕的工件集.假設被接受的每箇工件都有一箇待定的交貨期窗口,且所有工件的交貨期窗口的大小是相同的,如果工件在窗口中完工,則不產生任何費用;否則工件提前或延誤,會產生相應的提前或延誤的費用.而對于拒絕工件而言,它的費用隻與工件有關.這類問題的總費用是2箇工件集的費用之和.目標函數是確定被接受工件的最優排序,極小化總費用,給齣瞭一箇動態規劃算法,併證明瞭這箇問題是多項式時間可解的.
토론료대유교화기창구화공건가거절적단궤배서문제,저일문제시장소유적공건분성량개집합,일개시피접수적공건집,일개시피거절적공건집.가설피접수적매개공건도유일개대정적교화기창구,차소유공건적교화기창구적대소시상동적,여과공건재창구중완공,칙불산생임하비용;부칙공건제전혹연오,회산생상응적제전혹연오적비용.이대우거절공건이언,타적비용지여공건유관.저류문제적총비용시2개공건집적비용지화.목표함수시학정피접수공건적최우배서,겁소화총비용,급출료일개동태규화산법,병증명료저개문제시다항식시간가해적.
