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(nk+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)nk-1/(k-1)!).
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
.
DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.007
[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.
