سامانه پشتیبانی خدمات اطلاعات

  اخبار و اعلانات

 آمار

تعداد نشریات161
تعداد شماره‌ها6,573
تعداد مقالات71,037
تعداد مشاهده مقاله125,518,029
تعداد دریافت فایل اصل مقاله98,777,910
Daneshamoz, Fatemeh, Behnamian, Javad. (1397). A lower bound for job shop scheduling problem with a parallel assembly stage by graph coloring approach. , 52(3), 367-378. doi: 10.22059/jieng.2019.219236.1250
Fatemeh Daneshamoz; Javad Behnamian. "A lower bound for job shop scheduling problem with a parallel assembly stage by graph coloring approach". , 52, 3, 1397, 367-378. doi: 10.22059/jieng.2019.219236.1250
Daneshamoz, Fatemeh, Behnamian, Javad. (1397). 'A lower bound for job shop scheduling problem with a parallel assembly stage by graph coloring approach', , 52(3), pp. 367-378. doi: 10.22059/jieng.2019.219236.1250
Daneshamoz, Fatemeh, Behnamian, Javad. A lower bound for job shop scheduling problem with a parallel assembly stage by graph coloring approach. , 1397; 52(3): 367-378. doi: 10.22059/jieng.2019.219236.1250

A lower bound for job shop scheduling problem with a parallel assembly stage by graph coloring approach

Advances in Industrial Engineering
مقاله 5، دوره 52، شماره 3، دی 2018، صفحه 367-378    اصل مقاله (968.02 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jieng.2019.219236.1250
نویسندگان
Fatemeh Daneshamoz؛ Javad Behnamian*
چکیده
Abstract: Scheduling is one of the most applicable problems in industry that is considerably studied by researchers in the recent years. It is necessary to extend the models that can be applied in real situations. To this end researchers have tried to consider assembly and processing stages simultaneously. In this research according to the importance of different production stages in industry, and also to consider problem in real situation, job shop scheduling problem by considering a parallel assembly stage is studied to minimize completion time for all products. At first, this problem is reduced to graph coloring. Because this problem and graph coloring problem are NP-hard, a hybrid Genetic-Particle swarm optimization algorithm for medium and large size problems used. So in this research a lower bound for this problem based on graph coloring problem is proposed to evaluate the efficiency and effectiveness of the proposed algorithm.

Keywords: Scheduling, Job shop, Parallel Assembly, Graph Coloring
کلیدواژه‌ها
Scheduling؛ Job shop؛ Parallel Assembly؛ Graph Coloring
عنوان مقاله [English]
ارائۀ حد پایین برای مسئلۀ زمان‌بندی خط تولید کارگاهی همراه با یک مرحله مونتاژ موازی با استفاده از رویکرد رنگ‌آمیزی گراف
نویسندگان [English]
فاطمه دانش‌آموز؛ جواد بهنامیان
چکیده [English]
 زمان‌بندی یکی از مسائل پرکاربرد در صنعت است که پژوهشگران در سال‌های اخیر توجهی ویژه‌ به آن داشته‌اند. تلاش برای کاهش شکاف میان روش‌های تئوری و کاربردی در مسائل زمان‌بندی، از ضرورت‌های دنیای امروز محسوب می‌شود. یکی از اقدامات صورت‌گرفته در این زمینه، توجه هم‌زمان دو مرحلة مونتاژ و پردازش است. در این پژوهش با توجه به اهمیت توجه هم‌زمان به مراحل مختلف تولید در صنعت و همچنین به‌منظور کاربردی‌ترکردن مسئله، به بررسی مسئلة زمان‌بندی تولید کارگاهی با درنظرگرفتن یک مرحله مونتاژ موازی با هدف حداقل‌کردن زمان تکمیل محصولات پرداخته‌ایم. بدین‌منظور ابتدا مسئلة مدنظر به مسئلة رنگ‌آمیزی گراف تقلیل داده شد. با توجه به اینکه مسئلة مدنظر و رنگ‌آمیزی گراف مربوط از نوع NP-hard هستند، برای حل آن‌ها در ابعاد متوسط و بزرگ از الگوریتم ترکیبی ژنتیک و بهینه‌سازی انبوه ذرات استفاده شد. همچنین به‌منظور بررسی صحت عملکرد و میزان کارایی الگوریتم در این پژوهش، حدود بالا و پایینی با استفاده از مسئلة رنگ‌آمیزی گراف ارائه شد.
کلیدواژه‌ها [English]
تولید کارگاهی, رنگ‌آمیزی گراف, زمان‌بندی, مونتاژ موازی
مراجع
  1. Lee, C. Y., Cheng, T. C. E. and Lin, B. M. T. (1993). “Minimizing the Makespan in the-Machine Assembly-Type Flowshop Scheduling Problem”, Management Science, Vol. 39, No. 5, PP. 616-625.
  2. Al Anzi, F. S., and Allahverdi, A. (2013). “An Artificial Immune System Heuristic for Two-Stage Multi-Machine Assembly Scheduling Problem to Minimize Total Completion Time”, Journal of Manufacturing Systems, Vol. 32, No. 4, PP. 825– 830.
  3. Allahverdi, A., and Al Anzi, F. S. (2006). “A Branch and Bound Algorithm for Three-Machine Flowshop Scheduling Problem to Minimize Total Completion Time with Separate Setup Times”, European Journal of Operational Research, Vol. 169, No. 3, PP. 767-780.
  4. Seyedi, I., Maleki Daronkolaei, A., and Kalashi, F. (2012). “Tabu Search and Simulated Annealing for New Three-Stage Assembly Flow Shop Scheduling with Blocking”, Interdisciplinary Journal of Contemporary Research in usiness, Vol. 4, No. 8, PP. 394-402.
  5. Navaei, J. et al. (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 and Operations Research, Vol. 44, No. 4, PP. 52–65.
  6. Hariri, A. M. A., and Potts, C. N. (1997). “A Branch and Bound Algorithm for the Two-Stage Assembly Scheduling Problem”, European Journal of Operational Research, Vol. 103. No. 3, PP. 547-556.
  7. Yokoyama, M. (2001). “Hybrid Flow Shop Scheduling with Assembly Operations”, International Journal of Production Economics,Vol. 73, PP. 103-116.
  8. Sung, Ch.S., and Juhn, J. (2009). “Makespan Minimization for a 2-Stage Assembly Scheduling Problem Subject to Component Available Time Constraint”, International Journal of Production Economics,Vol. 119, No. 2, PP. 392-401.
  9. Sung, C. S., and Kim, H. Ah. (2008). “A Two-Stage Multiple-Machine Assembly Scheduling Problem for Minimizing Sum of Completion Times”, International Journal of Production Economics,Vol. 113, No. 2, PP. 1038-1048.
  10. Fattahi, P., Hosseini, S. M. H., and Jolai, F. (2012). “A Mathematical Model and Extension Algorithm for Assembly Flexible Flow Shop Scheduling Problem”, International Journal of Advance Manufacture Technology, Vol. 65, No. 5-8, PP. 787-802.
  11. Garey, M. R., and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, LA: Freeman.
  12. Sotskov, Y. N., and Tanaev, V. S. (1976). “Chromatic Polynomial of a Mixed Graph”, Vestsi Akademii Navuk BSSR, Seryya Fizika-Matematychnykh Navuk, Minsk. Vol. 140, No. 6, PP. 20–23. Russian.
  13. Sotskov, Y. N., Dolgui, A., and Werner, F. (2001). “Mixed graph coloring for unit-time job-shop scheduling”, International Journal of Mathematical Algorithms, Vol. 2, No. 4, PP. 289–‌323.
  14. Al Anzi, F. S. et al. (2006). “Using Mixed Graph Coloring to Minimize Total Completion Time in Job Shop Scheduling”, applied Mathematics and omputation, Vol. 182, No. 2, PP. 1137–1148.
  15. Kouider, A. et al. (2015). “Mixed Integer Linear Programs and Tabu Search Approach to Solvemixed Graph Coloring for Unit-Time Job Shop Scheduling”, In IEEE International Conference on Automation Science and Engineering (CASE), August 24–28, Gothenburg, Sweden, 1177–1181.
  16. Kouider, A. et al. (2017). “Mixed Graph Colouring For Unit-Time Scheduling”, International Journal of Production Research,Vol. 55, No. 6, PP. 1720-1729.
  17. Shen, J. W. (2003). “Solving the Graph Coloring Problem Using Genetic Programming”, In Genetic Algorithms and Genetic Programming at Stanford 2003: 187-196, Stanford Bookstore.
  18. Daneshamooz, F., Jabbari, M., and Fattahi, P. (2013). “A Model for Jobshop Scheduling with a Parallel Assembly Stage to Minimize Makespan”, Journal of Industrial Engineering Research in Production Systems,Vol. 2, No. 4, PP. 39-53.
  19. Setak, M. et al. (2014). “Capacitated Multi-Depot Vehicle Routing Problem with Inter-Depot Routes”, Journal of Industrial Engineering, University of Tehran, Special Issue, Vol. 48, PP. 11-18.
  20. Kao, Y. T., and Zahara, E. (2008). “A Hybrid Genetic Algorithm and Particle Swarm Optimization for Multimodal Functions”, Applied Soft Computing, Vol. 8, No. 2, PP. 849-857.
  21. Eberhart, R., and Kennedy, J. (1995). “A New Optimizer Using Particle Swarm Theory”, 6th Int. Symposium on Micro Machine and Human Science, Nagoya, Japan, PP. 4-39.
  22. Kiani, M. et al. (2015). “An Efficient Genetic Algorithm for a Vehicle Routing Problem Considering the Competency of Working Teams”, Journal of Industrial Engineering, University of Tehran, Vol. 49, No. 2, PP. 257-271.
آمار
تعداد مشاهده مقاله: 1,064
تعداد دریافت فایل اصل مقاله: 434





سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب