期刊文献+

一个不同时刻加工成本有差异的单机排序问题(英文) 被引量:2

A Single Machine Scheduling Problem with Different Processing Costs
下载PDF
导出
摘要 考虑一个单机排序问题:一批工件在零时刻到达可加工,加工时不可中断,在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时,要求确定一个最优加工序,当时间区间为决策变量时,要求找到一个最优序及最优区间位置, 由此来最小化总额外加工成本.文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法, 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.
出处 《运筹学学报》 CSCD 北大核心 2006年第2期37-45,共9页 Operations Research Transactions
基金 This work is partially supported by NSFC 70571059 SZU R/D Fund(Project 200552).
关键词 运筹学 排序 时间区间 额外加工费 NP-HARD 算法 Operation research, scheduling, time window, extra operation cost, NP-hard, algorithm
  • 相关文献

参考文献16

  • 1F.D.Anger,C.-Y.Lee and L.A.Martin-Vega.Single Machine Scheduling with Tight Windows.Research Reprot 86-16,Department of Industrial and Systems Engineering,University of Floria,Gainesville,Florida,1986.
  • 2F.-J.Kramer and C.-Y.Lee.Common Due Window Scheduling.Production and Operations Management,1993,2:262~275.
  • 3C.-Y.Lee.Earliness-Tardiness Scheduling Problems with Constant Size of Due Date Window.Research Report 91-17,Department of Industrial and System Engineering,University of Florida,Gainesville,Florida,1991.
  • 4S.D.Liman,S.Ramaswamy.Earliness-Tardiness Scheduling Problems with a Common Delivery Window.Operations Research Letters,1994,15:195~203.
  • 5S.D.Liman,S.S.Panwlker,S.Thongmee.Determination of Common Due Window Location in a Singer Machine Scheduling Problem.European Journal of Operational Research,1996,93:68~74.
  • 6C.Koulamas.Single-Machine Scheduling with Time Window and Earliness/Tardiness Penalties.European Journal of Operational Research,1996,91:190~202.
  • 7J.A.Ventura,M.X.Weng.Single Machine Scheduling with a Common Delivery Window.Journal of the Operational Research Society,1996,47:424~434.
  • 8C.Koulamas.Maximizing the Weighted Number of On-Time Jobs in Single Machine Scheduling with Time Windows.Math.Comput.Modelling,1997,25(10),57~62.
  • 9S.D.Liman,S.S.Panwalkar,S.Thongmee.Common Due Window Size and Location Determination in a Single Machine Scheduling Problem.Journal of the Operational Research Society,1998,49:1007~-1010.
  • 10S.D.Liman,S.S.Panwalkar,S.Thongmee.Scheduling Common Due Window Problems with Controllable Processing Times.Annals of Operations Research,1997,70:145~154.

同被引文献10

  • 1张树霞,唐国春,张玉忠.关于延误问题改进的Emmons条件[J].曲阜师范大学学报(自然科学版),2006,32(2):6-8. 被引量:2
  • 2LimanSD RamaswamyS.具有共同宽容交货期的超前延误调度问题[J].运筹学简报,1994,15(4):195-203.
  • 3LimanSD PanwalkerSS ThongmeeS.单机调度问题中共同宽容交货期位置的确定[J].欧洲运筹学学报,1996,93(1):68-74.
  • 4KoulamasC.具有时间窗口及超前延误惩罚的单机调度[J].欧洲运筹学学报,1996,(91):190-202.
  • 5KoulamasC.具有时间窗口的单机调度中最大化准时加权工件数[J].数学计算模型,1997,25(10):57-62.
  • 6Anger F D,Lee C Y,Martin-Vega L A.具有紧窗口的单机调度,研究报告86-16[R].佛罗里达州:佛罗里达大学,1986 (英文版).
  • 7ChenZL LeeCY.具有宽容交货期的平行机调度[J].欧洲运筹学学报:英文版,2002,136(3):512-527.
  • 8YeungWK OguzC EdwinChengTC.具有宽容交货期的单机调度问题[J].计算运筹学报:英文版,2001,28(2):157-175.
  • 9Kellerer H,Pferschy U,Pisinger D.背包问题[M].柏林:Springer-Verlag出版社,2004(英文版).
  • 10陈全乐,孙世杰.一个宽容交货超前延误单机排序问题[J].高校应用数学学报(A辑),2000,15A(4):440-448. 被引量:4

引证文献2

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部