重入排序问题综述

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

Abstract

Abstract:

In contrast to the classical scheduling assumption that each job visits each machine once at most, jobs with reentrant style are of a new type of scheduling problems. The basic characteristic of a re-entrant problem is that a job visits certain machines more than once. Re-entrance is usually found in semiconductor manufacturing, and also many other fields. Recently many papers have dealt with the re-entrant scheduling problems. Results and contributions of these references are presented and analyzed in this paper. The contents and methods are classified and introduced according to the machine environments, including single machine, flow shop, flexible flow shop and others. Research directions and trends of re-entrant scheduling problems in the future are presented at last.

Key words: scheduling, re-entrant, flow shop, makespan, review

JING Caixia, ZHAO Congli, YUAN Erming. A review of re-entrant scheduling problems[J]. Operations Research Transactions, 2015, 19(2): 37-44.

References

Kumar P R. Re-entrant lines [J]. Queueing Systems, 1993, 13: 87-110.

Wang M Y, Sethi S P, Van De Velde S L. Minimizing makespan in a class of reentrant shops [J]. Oper Res, 1997, 45: 702-712.

Yang D L, Kuo W H, Chern M S. Multi-family scheduling in a two-machine re-entrant flow shop with setups [J]. European Journal of Operational Research, 2008, 187(3): 1160-1170.

张启忠. 基于 EM-Plant 可重入钢管生产线的仿真与调度 [D]. 重庆: 重庆大学, 2009.

Baker K R. Introduction to Sequencing and Scheduling [M]. New York: Wiley, 1974.

井彩霞, 钱省三, 唐国春. 重入单机排序问题 [J]. 运筹学学报, 2008,12(2): 84-87.

Lev V, Adiri I. V-Shop scheduling [J]. European Journal of Operational Research, 1984, 18: 51-56.

Drobouchevitch I G, Strusevich V A. A heuristic algorithm for two-machine re-entrant shop scheduling [J]. Annals of Operations Research, 1999, 86: 417-439.

Choi S W, Kim Y D. Minimizing makespan on an m-machine re-entrant flow shop [J]. Computers and Operations Research, 2008, 35(5): 1684-1696.

Chen J S, Pan J C H, Lin C M. A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem [J]. Expert Systems with Applications, 2008, 34(1): 570-577.

Xu J, Yin Y, Cheng T C E, et al. A memetic algorithm for the re-entrant permutation flowshop scheduling problem to minimize the makespan [J]. Applied Soft Computing, 2014, 24: 277-283.

Pan J C H, Chen J S. Minimizing makespan in reentrant permutation flow-shops [J]. Journal of Operational Research Society, 2003, 57: 642-653.

Li Z C, Qian B, Hu R, et al. A hybrid population-based incremental learning algorithm for m-machine reentrant permutation flow-shop scheduling [J]. Advanced Materials Research, 2013, 655: 1636-1641.

Chen J S, Pan J C H, Wu C K. Hybrid tabu search for re-entrant permutation flow-shop scheduling problem [J]. Expert Systems with Applications, 2008, 34(3): 1924-1930.

Lin D, Lee C K M, Ho W. Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop [J]. Engineering Applications of Artificial Intelligence, 2013, 26: 1282-1290.

Jing C X, Qian X S, Tang G C. Two-machine flow shop scheduling with re-entrance [C]//Proceedings of the International Conference on Information Management, Innovation Management and Industrial Engineering. Los Alamitos: IEEE Computer Society, 2008, 2: 528-531.

Jing C X, Tang G C, Qian X S. Heuristic algorithms for two machine re-entrant flow shop [J]. Theoretical Computer Science, 2008, 400(1-3): 137-143.

Choi S W, Kim Y D. Minimizing makespan on a two-machine re-entrant flowshop [J]. Journal of the Operational Research Society, 2007, 58: 972-981.

Ahmad B S, Gani I M. Clustered absolute bottleneck adjacent matching heuristic for re-entrant flow shop [J]. Applied Mechanics and Materials, 2014, 465: 1138-1143.

Choi S W, Kim Y D. Minimizing total tardiness on a two-machine re-entrant flowshop [J]. European Journal of Operational Research, 2009, 199: 375-384.

Demirkol E, Uzsoy R. Decomposition methods for reentrant flow shops with sequence dependent setup times [J]. Journal of Scheduling, 2000, 3: 115-177.

Jeong B J, Kim Y D. Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times [J]. Computers Operations Research, 2014, 47: 72-80.

Jing C X, Huang W Z, Tang G C. Minimizing total completion time for re-entrant flow shop scheduling problems [J]. Theoretical Computer Science, 2011, 412(48): 6712-6719.

Hekmatfar M, Fatemi G S M T, Karimi B. Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan [J]. Applied Soft Computing, 2011, 11(8): 4530-4539.

Cho H M, Bae S J, Kim J, et al. Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm [J]. Computers Industrial Engineering, 2011, 61(3): 529-541.

Dugardin F, Yalaoui F, Amodeo L. New multi-objective method to solve reentrant hybrid flow shop scheduling problem [J]. European Journal of Operational Research, 2010, 203(1): 22-31.

Choi H S, Kim J S, Lee D H. Real-time scheduling for reentrant hybrid flow shops: A decision tree based mechanism and its application to a TFT-LCD line [J]. Expert Systems with Applications, 2011, 38(4): 3514-3521.

Yalaoui N, Amodeo L, Yalaoui F, et al. Efficient methods to schedule reentrant flowshop system [J]. Journal of Intelligent and Fuzzy Systems, 2014, 26(3): 1113-1121.

Huang R H, Yu S C, Kuo C W. Reentrant two-stage multiprocessor flow shop scheduling with due windows [J]. The International
Journal of Advanced Manufacturing Technology, 2014, 71(5-8): 1263-1276.

Ying K C, Lin S W, Wan S Y. Bi-objective reentrant hybrid flowshop scheduling: an iterated Pareto greedy algorithm [J]. International Journal of Production Research, 2014, 52(19): 5735-5747.

Sangsawang C, Sethanan K, Fujimoto T, et al. Metaheuristics optimization approaches for two-stage reentrant flexible flow shop with blocking constraint [J]. Expert Systems with Applications, 2015, 42(5): 2395-2410.

Elmi A, Solimanpur M, Topaloglu S, et al. A simulated annealing algorithm for the job shop cell scheduling problem with
intercellular moves and reentrant parts [J]. Computers Industrial Engineering, 2011, 61(1): 171-178.

Chen S F, Qian B, Liu B, et al. Bayesian statistical inference-based estimation of distribution algorithm for the re-entrant job-shop
scheduling problem with sequence-dependent setup times [M]//Intelligent Computing Methodologies. Switzerland: Springer, 2014, 686-696.

Dehghanian N, Homayouni S M. A fuzzy-genetic algorithm for makespan reduction in job shop environments with sequence-dependent setup time and re-entrant work flow [C]//Proceedings of the 4 th European Seminar on Computing: Main Thematic Areas. Czech Republic: University of West Bohemia, 2014, 68.

Chen J C, Wu C C, Chen C W, et al. Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm [J]. Expert Systems with Applications, 2012, 39(11): 10016-10021.

Chen J C, Chen K H, Wu J J, et al. A study of the flexible job shop scheduling problem with parallel machines and reentrant process [J]. Int J Adv Manuf Technol, 2008, 39: 344-354.

Chakhlevitch H, Glass C A. Scheduling reentrant jobs on parallel machines with a remote server [J]. Computers and Operations Research, 2009, 36(9): 2580-2589.

王宏, 李海娟, 赵月,等. 带有远程服务器的重入平行机排序问题的遗传算法 [J]. 天津大学学报，2013,19: 463-469.

Shin H J. A dispatching algorithm considering process quality and due dates: an application for re-entrant production lines [J]. The International Journal of Advanced Manufacturing Technology, 2015, 77(1-4): 249-259.

[1]	ZHAO Congcong, FANG Dandan, LI Rongheng. Optimal algorithms for hybrid flow shop schedule on two machines with learning effect [J]. Operations Research Transactions, 2020, 24(2): 42-60.
[2]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[3]	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.
[4]	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.
[5]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[6]	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.
[7]	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.
[8]	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.
[9]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[10]	ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74.
[11]	CHEN Qiuhong, ZHANG Xingong. Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine [J]. Operations Research Transactions, 2019, 23(1): 61-71.
[12]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[13]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[14]	ZHAO Xiaocheng, LI Dagang. Parallel machine scheduling with machine and human eligibility restrictions [J]. Operations Research Transactions, 2018, 22(3): 99-108.
[15]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.

A review of re-entrant scheduling problems

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments