Abstract




 
   

IJE TRANSACTIONS C: Aspects Vol. 28, No. 6 (June 2015) 903-912    Article in Press

downloaded Downloaded: 206   viewed Viewed: 2276

  SOLVING RE-ENTRANT NO-WAIT FLOW SHOP SCHEDULING PROBLEM
 
S. Tasouji Hassanpour, M.R. Amin Naseri and N. Nahavandi
 
( Received: December 29, 2014 – Accepted: June 11, 2015 )
 
 

Abstract    In this study, we consider the production environment of no-wait reentrant flow shop with the objective of minimizing makespan of the jobs. In a reentrant flow shop, at least one job should visit at least one of the machines more than once. In a no-wait flowshop scheduling problem, when the process of a specific job begins on the first machine, it should constantly be processed without waiting in the line of any machine until its processing is completed on the last one. Integration of the properties of both of these environments, which is applied in many industries such as robotic industries, is not investigated separately. First, we develop a mathematical model for the problem and then we present three methods to solve it. Therefore, we construct simulated annealing (SA), genetic algorithm (GA) and a bottleneck based heuristic (BB) algorithms that solve the problem. Finally, the efficiency of the proposed methods is numerically analyzed.

 

Keywords    No-wait flowshop, Re-entrant flowshop, Simulated Annealing , Genetic Algorithm, Bottleneck

 

چکیده    در این مقاله زمانبندی مساله جریان کارگاهی با در نظر گرفتن خصوصیات برگشت­پذیر و بدون وقفه بودن محیط با هدف کمینه­سازی حداکثر زمان تکمیل کارها بررسی می­شود. ویژگی اصلی محیط برگشت­پذیر این است که در آن حداقل یک کار می­بایست یک یا چند مرحله را بیش از یکبار ملاقات کند. در مسایل جريان کارگاهي بدون وقفه، وقتی پردازش کاری بر روی ماشین اول شروع می­شود، می بایست بدون اینکه وقفه­ای در آن بوجود آید مسیر پردازشی خود را تا اتمام عملیات روی ماشین آخر طی نماید. ادغام هردوی این خصوصیات در بسیاری از صنایع مانند صنایع رباتیک کاربرد دارد که در ادبیات بصورت مجزا مورد بررسی قرار نگرفته است. . ابتدا برای مساله مدنظر یک مدل ریاضی ارایه شده و سپس به حل آن با استفاده از سه روش پیشنهادی پرداخته شده­است. الگوریتم­های پیشنهادی شامل شبیه سازی تبرید، الگوریتم ژنتیک و یک الگوریتم مبتنی بر گلوگاه می­باشد. در نهایت، کارآیی روش­های ارایه شده ارزیابی و مورد بررسی قرار گرفته است.

References   

1.        Aldowaisan, T., & Allahverdi, A., "New heuristics for no-wait flowshops to minimize makespan", Computers & Operations Research, Vol.30, No.8 , (2003), 1219-1231.

2.        Attar, S., Mohammadi, M., & Tavakkoli-Moghaddam, R., "A novel imperialist competitive algorithm to solve flexible flow shop scheduling problem in order to minimize maximum completion time", International Journal of Computer Applications, Vol.28, No,10, (2011), 27-32.

3.        Chen, C.-L., & Chen, C.-L., "A bottleneck-based heuristic for minimizing makespan in a flexible flow line with unrelated parallel machines", Computers & Operations Research, Vol.36, No.11, (2009), 3073-3081.

4.        Chen, J.-S., "A branch and bound procedure for the reentrant permutation flow-shop scheduling problem", The International Journal of Advanced Manufacturing Technology, Vol.29, No.11, (2006), 1186-1193.

5.        Dugardin, F., Yalaoui, F., & Amodeo, L., "New multi-objective method to solve reentrant hybrid flow shop scheduling problem", European Journal of Operational Research, Vol.203, No.1, (2010), 22-31.

6.        Emmons, H., & Vairaktarakis, G., "Flow shop scheduling: theoretical results, algorithms, and applications", Springer Science & Business Media, Vol. 182, (2012).

7.        Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R., "Optimization and approximation in deterministic sequencing and scheduling: a survey", Annals of Discrete Mathematics, Vol.5, (1979), 287-326.

8.        Gupta, J. N., Strusevich, V. A., & Zwaneveld, C. M., "Two-stage no-wait scheduling models with setup and removal times separated", Computers & Operations Research, Vol.24, No.11, (1997), 1025-31.

9.        Hall, N. G., & Sriskandarajah, C., "A survey of machine scheduling problems with blocking and no-wait in process", Operations Research, Vol.44, No.3, (1996), 510-525.

10.     Hsieh, B.-W., Chen, C.-H., & Chang, S.-C., "Efficient simulation-based composition of scheduling policies by integrating ordinal optimization with design of experiment", Automation Science and Engineering, IEEE Transactions on, Vol.4, No.4, (2007), 553-568.

11.     Huang, R.-H., Yu, S.-C., & Kuo, C.-W., "Reentrant two-stage multiprocessor flow shop scheduling with due windows", The International Journal of Advanced Manufacturing Technology, Vol.71, (2014), 1263-1276.

12.     Jing, C., Huang, W., & Tang, G., "Minimizing total completion time for re-entrant flow shop scheduling problems", Theoretical Computer Science, Vol.412, No.48, (2011), 6712-6719.

13.     McCormick, S. T., & Rao, U. S., "Some complexity results in cyclic scheduling". Mathematical and Computer Modelling, Vol. 20, No. 2, (1994), 107-122.

14.     Pan, J. C.-H., & Chen, J.-S., "Mixed binary integer programming formulations for the reentrant job shop scheduling problem", Computers & Operations Research, Vol.32, No.5, (2005), 1197-1212.

15.     Qian, B., Wan, J., Liu, B., Hu, R., & Che, G.-L., "A DE-based algorithm for reentrant permutation flow-shop scheduling with different job reentrant times", Paper presented at the Computational Intelligence in Scheduling (SCIS), (2013).

16.     Shafaei, R., Rabiee, M., & Mirzaeyan, M., "An adaptive neuro fuzzy inference system for makespan estimation in multiprocessor no-wait two stage flow shop", International Journal of Computer Integrated Manufacturing, Vol.24, No.10, (2011), 888-899.

Yang, D.-L., Kuo, W.-H., & Chern, M.-S., "Multi-family scheduling in a two-machine reentrant flow shop with setups". European Journal of Operational Research, Vol.187, No.3, (2008), 1160-1170





International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir