ADME-JSP: AN EFFECTIVE MEMETIC ALGORITHM FOR JOB SHOP SCHEDULING PROBLEM

  • سال انتشار: 1392
  • محل انتشار: همایش ملی پژوهش های کاربردی در علوم و مهندسی
  • کد COI اختصاصی: TIAU01_792
  • زبان مقاله: انگلیسی
  • تعداد مشاهده: 932
دانلود فایل این مقاله

نویسندگان

SOMAYEH KALANTARI

Department of Electrical, computer, and Biomedical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

MOHAMAD SANIEE ABADEH

Department of Electrical and Computer Engineering, Tarbiat Modares University, Tehran, Iran

چکیده

The Job Shop Scheduling Problem (JSP) is one of the most well known planning problems. We have considered the JSP with an objective of minimizing makespan. In this paper, an effective Memetic algorithm isdeveloped to find the minimal schedule. We called this algorithm ADME-JSP. In ADME-JSP, using the ShuffledFrog Leaping Algorithm the population is divided in several groups. Then each group uses the presented Memeticalgorithm to solve the Job Shop Scheduling Problem. Two local searches have been used to balance the exploration and exploitation. One of the local searches is based on the Simulated Annealing Algorithm and another one is based on the Pair Wise interchange heuristic. The best solution (schedule) to the whole population is chosen among thebest results of all groups. The proposed approach, ADME-JSP, have been compared with other algorithms for JobShop Scheduling and evaluated with satisfactory results on a set of JSPs derived from classical Job Shop Schedulingbenchmarks. We have solved 15 benchmark problems (LA01 - LA15) from Lawrence and compared results found with a number of algorithms established in the literature. The results indicate that in all cases ADME-JSP can find the Best Known Solution (BKS).

کلیدواژه ها

Job Shop Schedulig, Memetic Algorithm, Simulated Annealing, Pair Wise Selection

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.