具有学习效应和加工时间可控的平行机排序问题

doi:10.12005/orms.2018.0066

运筹与管理 ›› 2018, Vol. 27 ›› Issue (3): 113-117.DOI: 10.12005/orms.2018.0066

具有学习效应和加工时间可控的平行机排序问题

郭苗苗¹, 刘桓², 王吉波^1,3, 牛玉萍¹

1.沈阳航空航天大学经济与管理学院,辽宁沈阳 110136;
2.辽宁省体育学校教务科,辽宁沈阳 110179;
3.沈阳航空航天大学理学院,辽宁沈阳 110136

收稿日期:2016-08-31 出版日期:2018-03-25
作者简介:郭苗苗,女,河北邢台人,硕士研究生,研究方向:企业运作管理;刘桓,女,辽宁沈阳人,硕士,研究方向:数学教育;王吉波,男,辽宁沈阳人,博士,教授,博导(兼职),主要从事生产计划与排序的研究;牛玉萍,女,山东烟台人,硕士生,研究方向:企业运作管理。
基金资助:
国家自然科学基金资助项目(71471120);辽宁省高等学校创新人才支持计划(LR201617)

Parallel Machines Scheduling with Learning Effect and Controllable Processing Times

GUO Miao-miao¹, LIU Huan², WANG Ji-bo^1,3, NIU Yu-ping¹

1.School of Economics and Management, Shenyang Aerospace University, Shenyang 110136, China;
2.Department of Educational Administration, Liaoning Sports School, Shenyang 110179, China;
3.School of Science, Shenyang Aerospace University, Shenyang 110136, China

Received:2016-08-31 Online:2018-03-25

摘要/Abstract

摘要： 本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(n^m+2),最后也给出了相应的数值例子来阐述该问题。

关键词: 排序, 平行机, 学习效应, 加工时间可控

Abstract: In this paper we consider the unrelated parallel machines scheduling problem, in the problem the job of the processing time is with learning effect and necource controllable, that is to say in the model of this problem the job’s actual processing time is the function of the basic processing time, the location of the job (learning effect) and the controllable of the processing time. The objective function is to minimize the weighted sum of total machine load and total control cost, and minimize the weighted sum of total completion time and total control cost. The article found an optimization algorithm to solve the problem through the analysis of the related nature of the problem, and also proved that in the number of processor is a given condition, the time complexity of the problem is O(n^m+2). Finally the paper also gives corresponding numerical example to illustrate this problem.

Key words: scheduling, parallel machine, learning effect, controllable job processing times

中图分类号:

O223
C934

郭苗苗, 刘桓, 王吉波, 牛玉萍. 具有学习效应和加工时间可控的平行机排序问题[J]. 运筹与管理, 2018, 27(3): 113-117.

GUO Miao-miao, LIU Huan, WANG Ji-bo, NIU Yu-ping. Parallel Machines Scheduling with Learning Effect and Controllable Processing Times[J]. Operations Research and Management Science, 2018, 27(3): 113-117.

参考文献

[1] 唐国春,张峰,罗守成,刘丽丽. 现代排序论[M].上海:上海科学普及出版社,2003.
[2] 徐健腾,柏庆国,张玉忠.带学习效应的二级易变质产品供应链的最优策略研究[J].系统工程理论与实践,2013,33(5):1167-1174.
[3] Biskup D. Single-machines scheduling with learning considerations[J]. European Journal of Operational Research, 1999, 115: 173-178.
[4] Biskup D. A state-of-the-art review on scheduling with learning effects[J]. European Journal Operational Research, 2008, 188: 315-329.
[5] 王吉波,刘璐.带准备时间的任务单机学习效应排序问题[J].大连理工大学学报,2013,53(6):930-936.
[6] 白静,刘璐,王吉波.具有截断学习效应和工件带准备时间的单机排序问题[J].运筹与管理,2014,23(6):152-156.
[7] 孙林辉,王丹,王吉波.具有学习效应的总完工时间流水作业问题[J].系统管理学报,2011,20(1):114-118.
[8] Wang J J, Zhang B H. Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects[J]. Computers & Operations Research, 2015, 58: 24-31.
[9] Wang J B, Xia Z Q. Single machine scheduling problems with controllable processing times and total absolute differences penalties[J]. European Journal of Operational Research, 2007, 177: 638-645.
[10] 周伟刚,高成修,黄凯.加工时间可控和简单线性增长的平行机排序[J].应用数学学报,2010,33(4):741-748.
[11] 周伟刚,冯倩倩,高成修.加工时间可控和恶化的单机最大完工时间排序[J].应用数学学报,2012,35(4):617-625.
[12] Wang J B, Wang M Z. Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time[J]. Computers & Operations Research, 2012, 39: 492-497.
[13] Mor B, Mosheiov G. Batch scheduling of identical jobs with controllable processing times[J]. Computers & Operations Research, 2014, 41: 115-124.
[14] Yang D L, Lai C J, Yang S J. Scheduling problems with multiple due windows assignment and controllable processing times on a single machine[J]. International Journal of Production Economics, 2014, 150: 96-103.
[15] Shabtay D, Steiner G. A survey of scheduling with controllable processing times[J]. Discrete Applied Mathematics, 2007, 155(13): 1643-1666.
[16] Wang D, Wang M Z, Wang J B. Single machine scheduling with learning effect and resource dependent processing times[J]. Computers & Industrial Engineering, 2010, 59: 458-462.
[17] Zhu Z, Sun L, Chu F, Liu M. Single-machine group scheduling with resource allocation and learning effect[J]. Computers & Industrial Engineering, 2011, 60: 148-157.
[18] Yin N, Wang X Y. Single machine scheduling with controllable processing times and learning effect[J]. International Journal of Advanced Manufacturing Technology, 2011, 54: 743-748.
[19] 王吉波,汪佳,牛玉萍.具有学习效应的单机可控加工时间排序问题研究[J].沈阳航空航天大学学报,2014,31(5):82-86.
[20] Li G, Luo M L, Zhang W J, Wang X Y. Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation[J]. International Journal of Production Research, 2015, 53(4): 1228-1241.
[21] Wang J B, Wang J J. Research on scheduling with job-dependent learning effect and convex resource dependent processing times[J]. International Journal of Production Research, 2015, 53: 5826-5836.
[22] Mosheiov G. Parallel machine scheduling with a learning effect[J]. Journal of the Operational Society, 2001, 52: 1156-1169.
[23] Liu M. Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect[J]. Applied Mathematical Modelling, 2013, 37: 9630-9633.
[24] Wang X Y, Wang J J. Scheduling deteriorating jobs with a learning effect on unrelated parallel-machines[J]. Applied Mathematical Modelling, 2014, 38: 5231-5238.
[25] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5: 287-326.

具有学习效应和加工时间可控的平行机排序问题

Parallel Machines Scheduling with Learning Effect and Controllable Processing Times

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	金苗苗, 吴蒙洁, 罗文昌. 具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案[J]. 运筹与管理, 2021, 30(8): 87-92.
[2]	刘春来, 王建军. 具有老化效应的单机共同工期安排和工件可拒绝排序问题[J]. 运筹与管理, 2021, 30(7): 66-70.
[3]	王磊, 柏庆国, 任建峰. 具有两种运输方式选择的物流排序问题[J]. 运筹与管理, 2021, 30(6): 1-5.
[4]	易平涛, 董乾坤, 李伟伟. 残缺数据下动态随机算法及应用[J]. 运筹与管理, 2021, 30(6): 6-11.
[5]	李勇军, 蔡华权. 基于Shephard距离函数的DEA TOPSIS方法研究[J]. 运筹与管理, 2021, 30(5): 116-121.
[6]	陶玲玲, 尤天慧. 基于在线评价且考虑消费者类型的酒店排序方法[J]. 运筹与管理, 2021, 30(5): 122-128.
[7]	朱运霞, 昂胜, 杨锋. 基于SMAA和公共权重的决策单元效率评价与排序[J]. 运筹与管理, 2021, 30(4): 184-189.
[8]	董君, 叶春明. 具有学习效应的半导体晶圆制造绿色车间调度问题研究[J]. 运筹与管理, 2021, 30(4): 217-223.
[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.