中文

Operations Research Transactions >

2015 , Vol. 19 >Issue 2: 37 - 44

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.02.004

A review of re-entrant scheduling problems

Expand
  • 1. College of Management, Tianjin Polytechnic University, Tianjin 300387, China; 2. Department of Common Required Courses, Tianjin University of Traditional Chinese  Medicine，Tianjin 300193, China

Received date: 2014-12-25

  Online published: 2015-06-15

Fold

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

Cite this article

JING Caixia, ZHAO Congli, YUAN Erming . A review of re-entrant scheduling problems[J]. Operations Research Transactions, 2015 , 19(2) : 37 -44 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.02.004

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.

 
Options
Outlines

/

〈 〉