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