توسعه یک الگوریتم شاخه و کران برای حل مساله زمانبندی در سیستم تولید جریان کارگاهی مونتاژی

نوع مقاله : پژوهشی

نویسندگان

دانشگاه شاهرود

چکیده

سیستم تولید جریان کارگاهی مونتاژی شامل دو مرحله است. در مرحله اول پردازش قطعات صورت می‌گیرد و معمولا به صورت یک ایستگاه با ماشین‌های موازی درنظر گرفته می‌شود. مرحله دوم نیز یک ایستگاه یا خط مونتاژ می‌باشد که قطعات پردازش شده، در آن مونتاژ و محصولات نهایی کامل می‌شود. در این تحقیق فرض می‌شود قرار است تعدادی محصول از انواع مختلف تولید شود و هر محصول جهت کامل شدن، نیازمند قطعاتی مشخص است. بعضی از قطعات محصولات مشترک و مشابه بوده و بعضی قطعات هم مختص یک محصول می‌باشد لذا باتوجه به تولید قطعات مشابه، موضوع زمان آماده‌سازی (setup time) و تولید دسته ای قطعات مشابه نیز نیازمند بررسی است. هدف عبارتست از زمانبندی پردازش قطعات در ایستگاه اول و مونتاژ محصولات در ایستگاه دوم بطوری که زمان تکمیل کل محصولات حداقل شود. طبق بررسی پیشینه تحقیق، این مساله جزء مسائل  NP-hard محسوب می‌گردد. ابتدا پارامترها و ویژگیهای مساله تعریف و پس از ارائه مدل ریاضی مساله، یک الگوریتم شاخه و کران برای حل مساله مورد نظر در ابعاد کوچک و متوسط ارائه می‌شود. همچنین به منظور افزایش کارایی الگوریتم پیشنهادی، دو حد پایین و دو حد بالا برای جواب مسائل توسعه داده می‌شود. در نهایت، چندین مساله تست با شرایط متنوع طراحی و عملکرد الگوریتم پیشنهادی در حل این مسائل ارزیابی شده است.

کلیدواژه‌ها


عنوان مقاله [English]

Proposed a branch and bound algorithm for Assembly flow shop scheduling problem

نویسندگان [English]

  • seyed mohammad hassan hosseini
  • ali akbar hassani
چکیده [English]

Assembly flow shop production system includes two stages. In the first stage that is usually assumed one station with some parallel machines, the parts are processed. The second stage is an assembly station (or line) to assemble the parts and complete the products. Suppose that a number of products of different kinds are ordered to be produced and each product needs a set of several parts to complete. Some of the parts are common and some others are unique for each product. Therefore it is important to study the setup times and batch production. The aim is to schedule the parts for process and the products for assembly with the minimum complete time objective. Literature review shows that the considered problem is a NP-Hard problem, so the problem characteristics and its parameters are defined and then a branch and bound algorithm is introduced to solve the small and mediocre problems. Some lower bounds and upper bounds are improved to increase the algorithm efficiency. Finally, a variety of problem is designed and performance of the proposed algorithm is evaluated in solving this problems.

کلیدواژه‌ها [English]

  • scheduling
  • Assembly flow shop. Branch &
  • amp
  • Bound algorithm
  • Makespan
 
[1] Jolai, F.,Moattar Hosseini, S.M., Hosseini, S.M.H., (2004). Flow Shop Scheduling Problem withMinimizing Earliness/Tardiness Criteria, Amirkabir Journal of Science & Technology, 15:452-461.
[2] Yokoyama, M., Santos, D.L. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times, European Journal of Operational Research, 161: 754-770.
[3] Lee, C.Y., Cheng, T.C.E., Lin, B.M.T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Management Science, 39: 616-625.
[4] Potts, C.N., Sevast'Janov, S.V., Strusevich, V. A., Van Wassenhove, L.N., Zwaneveld, C.M. (1995). The two-stage assembly scheduling problem: Complexity and approximation,  Operations Research, 43: 346-355.
[5] Hariri, A.M.A, Potts, C.N. (1997). A branch and bound algorithm for the two-stage assembly scheduling problem, European Journal of Operational Research 103:547-556.
[6] Haouari, M., Daouas, T. (1999). Optimal scheduling of the 3-machine assembly-type flow shop, RAIRO Recherche Operationnelle, 33: 439–450.
[7] Allahverdi, A., Al-Anzi, F. S. (2009). The two-stage assembly scheduling problem to minimize total completion time with setup times, Computers & Operations Research, 36:2740-2747.
[8] Al-Anzi, F.S., Allahverdi, A., (2007). A self-adaptive differential evolution heuristic for two stage assembly scheduling problem to minimize maximum lateness with setup time, European Journal of Operational Research, 182: 80-94.
[9] Torabzadeh, E., Zandieh M., (2010). Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop, Advances in Engineering Software, 41: 1238-1243.
[10] Fattahi, P., Hosseini, S.M.H., Jolai, F. (2012). A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem, International Journal of Advance Manufacture Technology, DOI 10.1007/s00170-012-4217-x.
[11] Navaei, J., Fatemi Ghomi, S.M.T., Jolai, F., Mozdgir, A., (2014). Heuristics for an assembly flow-shop with non-identical assembly machines and sequence dependent setup times to minimize sum of holding and delay costs, Computers & Operations Research, 44: 52-65.
[12] ] Fatahi, P., Hosseini, S.M.H., Jolai, F., Tavakkoli-Moghaddam, R., (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations, Applied Mathematical Modelling, 38: 119:134.
[13] Yokoyama, M., Santos, D.L. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times. European Journal of Operational Research, 161:754-770.
[14] Karimi Haghighi, A. (1389). Solving the flow shop scheduling problem in order to minimize the mean job completion time in the 3-stage assembly line by using the meta-heuristic approach, Payam-e-Noor University, Department of Industrial Engineering, MSc thesis.
[15] Hatami, S., Ebrahimnejad, S., Tavakoli-Moghadam, R., Maboudian, Y., (2010). Two meta-heuristics for three-stage assembly flowshop scheduling with sequence-dependent setup time, International Journal of Advanced Manufacturing Technology, 50: 1153-1164.
[16] Maleki-Darounkolaei, A., Modiri, M., Tavakoli-Moghadam, R., Seyyedi, I., (2012). A three-stage assembly flow shop scheduling problem with blocking and sequence-dependent set up times, Journal of Industrial Engineering-International, 1: 8-26.
[17] Brah S. A., and Hunsuchker, J. L., 1991. Branch and bound algorithm for the flow shop with multiple processors. European Journal of Operational Research, 51, 88–o99.
[18] S.O. Shim, Y.D. Kim, A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property, Computers & Operations Research 35 (2008) 863 – 875.
[19] S.O. Shim, Generating sub problems in branch and bound algorithms for parallel machines scheduling problem, Computers & Industrial Engineering 57 (2009) 1150–1153.