具有时间与位置相关的两类平行机排序问题

doi:10.15960/j.cnki.issn.1007-6093.2019.04.007

运筹学学报 ›› 2019, Vol. 23 ›› Issue (4): 86-94.doi: 10.15960/j.cnki.issn.1007-6093.2019.04.007

具有时间与位置相关的两类平行机排序问题

苟燕¹, 戴秦², 张新功^3,*

1. 四川省宜宾市筠连县民政局, 四川宜宾 645250;
2. 上海电力大学经济管理系, 上海 200090;
3. 重庆师范大学数学科学学院, 重庆 401331

收稿日期:2017-07-26 发布日期:2019-12-04
通讯作者: 张新功 E-mail:zxg7980@163.com
基金资助:
国家自然科学基金（Nos.11971443，715610007），重庆市科委自然科学基金（No.cstc2018jcyjAX063），重庆市教委研究生教改重点项目（No.yjg182019）

Scheduling problem with time-and-position-dependent effect on two parallel machines environments

GOU Yan¹, DAI Qin², ZHANG Xingong^3,*

1. Bureau of Civil Affairs, Junlian Yibin 645250, Sichuan, China;
2. Department of Economy and Management, Shanghai University of Electric Power, Shanghai 200090, China;
3. College of Mathematics Science, Chongqing Normal University, Chongqing 401331, China

Received:2017-07-26 Published:2019-12-04

摘要/Abstract

摘要： 研究带有维修时间限制的时间和位置效应平行机排序问题，涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响，且机器具有维修限制.目标函数由机器负载，总完工时间与总等待时间组成.非同类机情形下，通过将排序问题转化为指派问题，给出多项式时间算法，其算法的时间复杂度为O（n^k+2/（k-1）!）.同型机情形下通过转化目标函数，使用匹配算法得出排序问题的多项式时间解，其时间复杂度为O（（2n+m+n log n）n^k-1/（k-1）!）.

关键词: 排序, 平行机, 时间与位置效应, 维修活动

Abstract: This paper studies parallel-machine scheduling problems with time-andposition effect and maintenance restrictions, which parallel-machine environments are only involved with the identical parallel machines and unrelated machines. The actual processing time of the job is the function of position and time, and machines need to be maintained. Objective function is consisted of total machine load, total completion time and total waiting time. Under unrelated machines, the proposed problem can be solved by transferring into assignment problem, which its time complexity is O(n^k+2/(k-1)!). Under identical parallel machines, the proposed problem can be solved by matching algorithm, which its time complexity is O((2n+m+n log n)n^k-1/(k-1)!).

Key words: scheduling, parallel machines, time-and-position-dependent effect, maintenance activities

中图分类号:

O223
TP29

苟燕, 戴秦, 张新功. 具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报, 2019, 23(4): 86-94.

GOU Yan, DAI Qin, ZHANG Xingong. Scheduling problem with time-and-position-dependent effect on two parallel machines environments[J]. Operations Research Transactions, 2019, 23(4): 86-94.

参考文献

[1] Rustogi K, Strusevich V A. Single machine scheduling with general position deterioration and rate-modifying maintenance[J]. Omega, 2012, 40:791-804.
[2] Rustogi K, Strusevich V A. Simple matching vs linear assignment in scheduling models with positional effects:a critical review[J]. European Journal of Operational Research, 2012, 222:393-407.
[3] Rustogi K, Strusevich V A. Combining time and position dependent effects on a single machine subject to rate-modifying activities[J]. Omega, 2014, 42:166-178.
[4] Kuo W H, Yang D L. Minimizing the total completion time in a single machine scheduling problem with a cyclic processing of an aging effect[J]. Journal of Operational Research Society, 2008, 59:416-420.
[5] Kuo W H, Yang D L. Minimizing the total completion time in a single machine scheduling problem with a time-dependent learning effect[J]. European Journal of Operational Research, 2006, 174:1184-1190.
[6] Yang S J. Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deterioration maintenance consideration[J]. Applied Mathematics and computation, 2010, 217:3321-3329.
[7] Wang L Y, Huang X, Ji P, Feng E M. Unrelated parallel-machine with deteriorating-maintenance activities to minimize the total completion time[J]. Optimization Letters, 2014, 8(2):129-134.
[8] Yang D L, Cheng T C E, Yang S J, et al. Unrelated parallel-machine with aging effects and multi-maintenance activities[J]. Computer and Operational Research 2012, 39:1458-1464.
[9] Hsu C J., Ji M., Yang D L. Unrelated parallel-machine with aging effects and deteriorating maintenance activities[J]. Information Sciences, 2013, 253:163-169.
[10] Cheng T C E, Yang D L, Hsu C J, et al. Unrelated parallel-machine with deteriorating-maintenance activities[J]. Computer and Industrial Engineering, 2011, 60:602-605.
[11] 苟燕,张新功. 具有时间与位置相关及维修限制的单机排序问题[J]. 运筹学学报, 2016, 20(3):33-44.
[12] 王申重. 基于一般时间相关和位置相关的单机排序问题研究[J]. 重庆师范大学学报(自然科学版), 20172:6-10.
[13] 苗翠霞,邹娟. 带有退化效应和序列相关运输时间的排序问题[J]. 运筹学学报, 2016, 20(4):61-68.
[14] Fiszman S, Mosheiov G. Minimizing total load on a proportionate flowshop with position-dependent processing times and job-rejection[J]. Information Processing Letters, 2018, 132:39-43.
[15] Flajolet P. Analytic combinatics[M]. Cambridge University Press, 2009, 39-46.
[16] Hardy G H, Littlewood J E, Polya G. Inequalities[M]. Cambridge:Cambridge University Press, 1934.

具有时间与位置相关的两类平行机排序问题

Scheduling problem with time-and-position-dependent effect on two parallel machines environments

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	余山杉, 金苗苗, 罗文昌. 工件延误和可拒绝下的单机重新排序问题的近似方案[J]. 运筹学学报, 2021, 25(2): 104-114.
[2]	黄基诞, 郑斐峰, 徐寅峰, 刘明. 安装时间具有退化效应的MapReduce模型下的平行机调度[J]. 运筹学学报, 2020, 24(4): 93-106.
[3]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[4]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[5]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[6]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[7]	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.
[8]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[9]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[10]	仲维亚, 杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74.
[11]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[12]	赵晓成, 李大刚. 机器和工人都有加工资质约束的平行机排序问题研究[J]. 运筹学学报, 2018, 22(3): 99-108.
[13]	何程, 韩鑫鑫. 同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J]. 运筹学学报, 2018, 22(3): 109-116.
[14]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[15]	酒明珠, 高园, 原晋江. 工件可自由下线最小化总完工时间的平行分批排序问题[J]. 运筹学学报, 2018, 22(1): 32-41.