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

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

Abstract

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

CLC Number:

O223
TP29

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	CHEN Feng. Research and application of operations research on intelligent scheduling decision support system for automotive outbound logistics [J]. Operations Research Transactions, 2021, 25(3): 37-73.
[2]	YU Shanshan, JIN Miaomiao, LUO Wenchang. Approximation scheme for rescheduling on a single machine with job delay and rejection [J]. Operations Research Transactions, 2021, 25(2): 104-114.
[3]	SHEN Yindong, QIAN Zhuang, LI Yuanyuan. A survey on driver scheduling in public transportation [J]. Operations Research Transactions, 2021, 25(1): 1-16.
[4]	HUANG Jidan, ZHENG Feifeng, XU Yingfeng, LIU Ming. Parallel machine scheduling with deteriorating installation times in the MapReduce system [J]. Operations Research Transactions, 2020, 24(4): 93-106.
[5]	ZHANG Yuzhong, LI Shuguang. Scheduling with tree-hierarchical processing set restrictions [J]. Operations Research Transactions, 2020, 24(4): 107-112.
[6]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[7]	LU Shuxiang, Lü Changhong, QIN Tao. An algorithm based on makespan lower bound for quay crane schedule problem in container terminals [J]. Operations Research Transactions, 2020, 24(3): 67-76.
[8]	ZHONG Weiya, SHI Yimei. Robust optimization of rehearsal scheduling under uncertain duration [J]. Operations Research Transactions, 2020, 24(3): 77-86.
[9]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[10]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[11]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[12]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[13]	LI Ganggang, LU Xiwen. An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time [J]. Operations Research Transactions, 2019, 23(4): 95-104.
[14]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[15]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.