重入排序问题综述

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

井彩霞, 赵聪俐, 袁二明. 重入排序问题综述[J]. 运筹学学报, 2015, 19(2): 37-44.

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

参考文献

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]	赵聪聪, 方丹丹, 李荣珩. 具有学习效应的两台机上最优混合流水作业算法[J]. 运筹学学报, 2020, 24(2): 42-60.
[2]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[3]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[4]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[5]	苟燕, 戴秦, 张新功. 具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报, 2019, 23(4): 86-94.
[6]	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.
[7]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[8]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[9]	仲维亚, 杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74.
[10]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[11]	赵晓成, 李大刚. 机器和工人都有加工资质约束的平行机排序问题研究[J]. 运筹学学报, 2018, 22(3): 99-108.
[12]	何程, 韩鑫鑫. 同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J]. 运筹学学报, 2018, 22(3): 109-116.
[13]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[14]	酒明珠, 高园, 原晋江. 工件可自由下线最小化总完工时间的平行分批排序问题[J]. 运筹学学报, 2018, 22(1): 32-41.
[15]	张龙, 张玉忠, 柏庆国. 一类博弈排序问题的纳什均衡存在性证明 [J]. 运筹学学报, 2018, 22(1): 87-96.