具有恶化效应和凸资源分配关系的单机排序问题

doi:10.12005/orms.2017.0143

运筹与管理 ›› 2017, Vol. 26 ›› Issue (6): 102-106.DOI: 10.12005/orms.2017.0143

具有恶化效应和凸资源分配关系的单机排序问题

郭苗苗¹, 闫萍¹, 汪佳¹, 王吉波^{1, 2}

1.沈阳航空航天大学经济与管理学院,辽宁沈阳 110136;
2.沈阳航空航天大学理学院,辽宁沈阳 110136

收稿日期:2016-03-19 出版日期:2017-06-25
作者简介:郭苗苗,女,河北邢台人,硕士研究生,研究方向:企业运作管理;闫萍,女,辽宁沈阳人,博士,讲师,主要从事优化调度研究;汪佳,女,辽宁锦州人,硕士研究生,研究方向:企业运作管理;王吉波,男,辽宁沈阳人,博士,教授,大连理工大学博士生导师(兼职),主要从事生产计划与排序的研究。
基金资助:
国家自然科学基金资助项目(71471120);国家自然科学基金资助项目(U1433124);辽宁省教育厅人文社会科学研究项目(W2015316);辽宁省社会科学规划基金资助项目(L16DFL007)

Single Machine Scheduling with Deterioration Effectand Convex Resource Allocation

GUO Miao-miao¹, YAN Ping¹, WANG Jia¹, WANG Ji-bo^1,2

1.School of Economics and Management, Shenyang Aerospace University, Shenyang 110136, China;
2.School of Science, Shenyang Aerospace University, Shenyang 110136, China

Received:2016-03-19 Online:2017-06-25

摘要/Abstract

摘要： 研究工件加工时间具有恶化效应和凸资源关系的单机排序问题,其中工件的实际加工时间是其正常的加工时间,工件开工时间(具有恶化效应)及消耗资源量的函数。目标为在最大完工时间(总完工时间、总等待时间、完工时间总绝对差与等待时间总绝对差)小于或等于给定常数的条件下找到工件的最优排序和最优的资源分配使工件的总资源消耗量最少。在单机状态下,证明了此问题是多项式时间可解的,并给出了求解该问题的算法和数值实例。

关键词: 排序, 单机, 恶化效应, 资源分配

Abstract: In this paper we consider the single machine scheduling problem with deterioration effect and convex resource allocation, in which the actual processing time of a job is the function of its normal processing time, its starting time(deterioration effect)and resource quantities. The objective is to find the optimal schedule and the resource allocation of jobs so as to minimize total resource quantities consumed when the makespan(total completion time, total waiting time, total absolute differences in completion times, total absolute differences in waiting times) is up bounded by a given parameter. In the single machine case, we prove that this problem can be solved in polynomial time. Also, we give an algorithm and a numerical example to show how to solve an example problem.

Key words: scheduling, single machine, deterioration effect, resource allocation

中图分类号:

0223

郭苗苗, 闫萍, 汪佳, 王吉波. 具有恶化效应和凸资源分配关系的单机排序问题[J]. 运筹与管理, 2017, 26(6): 102-106.

GUO Miao-miao, YAN Ping, WANG Jia, WANG Ji-bo. Single Machine Scheduling with Deterioration Effectand Convex Resource Allocation[J]. Operations Research and Management Science, 2017, 26(6): 102-106.

参考文献

[1] Johnson S M. Optimal two-and three-stage production scheduling with setup times included[J]. Naval research logistics quarterly, 1954,1(1): 61-68.
[2] Browne S, Yechiali U. Scheduling deteriorating jobs on a single processor[J]. Operations Research, 1990, 38(3): 495-498.
[3] Bachman A, Janiak A. Minimizing maximum lateness under linear deterioration[J]. European Journal of Operational Research, 2000, 126(3): 557-566.
[4] Cheng T C E, Kang L, Ng C T. Due-date assignment and single machine scheduling with deteriorating jobs[J]. Journal of Operational Research Society, 2004, 55(2): 198-203.
[5] Wu C C, Shiau Y R, Lee W C. Single-machine group scheduling problems with deterioration consideration[J]. Computers and Operations Research, 2008, 35(5): 1652-1659.
[6] Wang J B, Wang M Z. Minimizing makespan in three-machine flow shops with deteriorating jobs[J]. Computers and Operations Research, 2013, 40(2): 547-557.
[7] Gawiejnowicz S. Time-dependent scheduling[M]. Springer, 2008.
[8] Shabtay D, Steiner G. A survey of scheduling with controllable processing times[J]. Discrete Applied Mathematics, 2007, 155: 1643-1666.
[9] Lu Y Y, Li G, Wu Y B, Ji P. Optimal due-date assignment problem with learning effect and resource-dependent processing times[J]. Optimization Letters, 2014, 8: 113-127.
[10] Wei C M, Wang J B, Ji P. Single-machine scheduling with time-and-resource-dependent processing times[J]. Applied Mathematical Modeling, 2012, 36: 792-798.
[11] Shabtay D, Kaspi M. Minimizing the total weighted flow time in a single machine with controllable processing times[J]. Computers and Operations Research, 2004, 31: 2279-2289.
[12] Wang X R, Wang J J. Single-machine scheduling with convex resource dependent processing times and deteriorating jobs[J]. Applied Mathematical Modelling, 2013, 37: 2388-2393.
[13] Wang X Y, Wang J J. Single-machine due date assignment problem with deteriorating jobs and resource-dependent processing times[J]. International Journal of Advanced Manufacturing Technology, 2013, 67: 255-260.
[14] Zhao C, Hsu C J, Wu W H, Cheng S R, Wu C C. Note on a unified approach to the single-machine scheduling problem with a deterioration effect and convex resource allocation[J]. Journal of Manufacturing Systems, 2016, 38: 134-140.
[15] Kanet J J. Minimizing variation of flow time in single machine systems[J]. Management Science, 1981, 27(12): 1453-1459.
[16] Bagchi U B. Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems[J]. Operations Research, 1989, 37: 118-125.
[17] Hardy G H, Littlewood J E, Polya G. Inequalities[M]. Cambridge: Cambridge University Press, 1934.

具有恶化效应和凸资源分配关系的单机排序问题

Single Machine Scheduling with Deterioration Effectand Convex Resource Allocation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	庞南生, 叶博童. 项目鲁棒调度的资源分配启发式算法研究[J]. 运筹与管理, 2021, 30(8): 21-27.
[2]	金苗苗, 吴蒙洁, 罗文昌. 具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案[J]. 运筹与管理, 2021, 30(8): 87-92.
[3]	刘春来, 王建军. 具有老化效应的单机共同工期安排和工件可拒绝排序问题[J]. 运筹与管理, 2021, 30(7): 66-70.
[4]	王磊, 柏庆国, 任建峰. 具有两种运输方式选择的物流排序问题[J]. 运筹与管理, 2021, 30(6): 1-5.
[5]	易平涛, 董乾坤, 李伟伟. 残缺数据下动态随机算法及应用[J]. 运筹与管理, 2021, 30(6): 6-11.
[6]	李勇军, 蔡华权. 基于Shephard距离函数的DEA TOPSIS方法研究[J]. 运筹与管理, 2021, 30(5): 116-121.
[7]	陶玲玲, 尤天慧. 基于在线评价且考虑消费者类型的酒店排序方法[J]. 运筹与管理, 2021, 30(5): 122-128.
[8]	朱运霞, 昂胜, 杨锋. 基于SMAA和公共权重的决策单元效率评价与排序[J]. 运筹与管理, 2021, 30(4): 184-189.
[9]	周丽, 杨江龙. 基于遗传算法的多通道密集式移动货架订单拣选研究[J]. 运筹与管理, 2021, 30(2): 84-90.
[10]	杨兴雨, 林虹, 何锦安, 张永. 基于排序预测的带交易费用在线投资组合策略[J]. 运筹与管理, 2021, 30(2): 168-175.
[11]	郑斐峰, 宋沁睿, 徐寅峰, 刘明. 考虑加工速率相互干扰的平行机调度最优策略研究[J]. 运筹与管理, 2021, 30(12): 1-5.
[12]	陶希闻, 江文奇. 面向直觉模糊集排序能力提升的记分函数设计研究[J]. 运筹与管理, 2021, 30(11): 34-39.
[13]	朱佳玮, 王尔大, 孙文章. 基于蒙特卡洛模拟的滨海旅游环境承载力影响因素重要性排序研究——以大连滨海景区为例[J]. 运筹与管理, 2021, 30(10): 47-52.
[14]	董晓芳, 张良勇. 产品可靠寿命的最优排序集挑选设计[J]. 运筹与管理, 2021, 30(10): 53-56.
[15]	张琳彦, 陈鸣, 徐倩, 张健. 考虑非期望因素的决策单元排序:两阶段综合效率法[J]. 运筹与管理, 2021, 30(10): 57-63.