重入排序问题综述

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.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2015.02.004

https://www.ort.shu.edu.cn/EN/Y2015/V19/I2/37

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]	XU Ke, JI Lanping, GONG Hua, LIU Peng, SUN Wenjuan. A coordinated multi-agent production and transportation scheduling on parallel machines based on auction algorithm [J]. Operations Research Transactions, 2026, 30(1): 121-136.
[2]	CHEN Rongjun, LIU Yongcai, HUANG He, TANG Guochun. Dynamic programming algorithms for single machine supply chain scheduling [J]. Operations Research Transactions, 2026, 30(1): 171-178.
[3]	MENG Lanmeng, MA Ran, ZHANG Yuzhong. Single-machine online scheduling with NDP constraint and deterioration [J]. Operations Research Transactions, 2026, 30(1): 179-187.
[4]	WU Hongyi, WANG Dong, WAN Long, LUO Wenchang. Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions [J]. Operations Research Transactions, 2026, 30(1): 188-196.
[5]	Dawei LI, Ganggang LI. Single-machine scheduling with operator non-availability periods and deteriorating jobs [J]. Operations Research Transactions, 2025, 29(4): 14-26.
[6]	Kaiyuan JIN, Feifeng ZHENG, Ming LIU. Online scheduling model of batch processing machine considering order types and setup time [J]. Operations Research Transactions, 2025, 29(4): 231-240.
[7]	Ruiqing SUN, Rui ZHANG, Yan LAN, Weidong LI. LPT algorithm for early work maximization problem [J]. Operations Research Transactions, 2025, 29(4): 249-254.
[8]	Guohua WAN, Shan WANG, Tengfang HUANG. Appointment scheduling in service systems: A survey and extension [J]. Operations Research Transactions, 2025, 29(3): 61-76.
[9]	Wei LU, Xingyu LU, Ding ZOU, Boxiao CHEN, Yihan ZHOU, Guochuan ZHANG. Research on computing power scheduling problem and technology in green computing [J]. Operations Research Transactions, 2025, 29(3): 179-201.
[10]	Siqi GUO, Ping ZHOU, Yiwei JIANG, Min JI. Single-machine scheduling with carbon emission cost and piece-rate maintenance [J]. Operations Research Transactions, 2025, 29(2): 68-79.
[11]	Di ZHAO, Jin YU, Xiwen LU. Approximation algorithms for two-agent serial batching scheduling problems [J]. Operations Research Transactions, 2025, 29(2): 184-193.
[12]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[13]	Na LI, Ran MA, Long LI, Yuzhong ZHANG. Study on the production scheduling of prefabricated components with learning effect [J]. Operations Research Transactions, 2025, 29(1): 19-30.
[14]	Tongxin CUI, Qian XIA, Xingong ZHANG. Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness [J]. Operations Research Transactions, 2025, 29(1): 31-40.
[15]	Shipian DU, Manzhan GU. Stochastic scheduling to minimize the expected total number of tardy jobs with machine maintenance activities [J]. Operations Research Transactions, 2025, 29(1): 142-158.

A review of re-entrant scheduling problems

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments