مقایسه کارایی مدل‌های برنامه‌ریزی عدد صحیح برای حل مساله زمان‌بندی کارگاه مرحله‌ای

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

نویسنده

دانشگاه تهران

چکیده

توسعه و تعمیم مدل‌های کلاسیک برای نزدیک شدن به شرایط دنیای واقعی همواره مورد توجه محققان قرار دارد. به همین جهت، تا کنون تلاش‌های زیادی برای توسعه مساله کار کارگاهی صورت گرفته است. مساله کارگاه مرحله‌ای به عنوان تعمیمی از کارگاه مخلوط و حالت خاصی از کارگاه عمومی تعریف می‌شود. در یک کارگاه مرحله‌ای، هر کار دارای چندین مرحله و هر مرحله شامل یک یا چند عمل است. یک مرحله، زیر مجموعه‌ای از عمل‌های یک کار است که می‌تواند به هر ترتیب دلخواهی انجام شود، در حالی که مراحل باید به ترتیب از پیش تعیین شده مورد پردازش قرار گیرند. به عبارت دیگر تا تمامی عمل‌های یک مرحله انجام نشوند، هیچ یک از عمل‌های مرحله بعدی نمی‌تواند شروع شود. در این مقاله، برای هر یک از دو مساله «زمان‌بندی کارگاه مرحله‌ای با معیار طول مدت ساخت» و «زمان‌بندی کارگاه مرحله‌ای با معیار مجموع وزن‌دار دیرکردها»، دو مدل برنامه‌ریزی عدد صحیح مخلوط (در مجموع چهار مدل) ارائه شده و سپس این دو مدل از نظر کارایی حل مساله مورد مقایسه قرار گرفته‌اند. برای ارزیابی کارایی مدل‌های ارائه شده (با الگوگیری از مسائل استاندارد کار کارگاهی)، مسائل نمونه‌ای تولید شده است. نتایج محاسباتی نشان می‌دهد که مدل دوم از کارایی بیشتری برخوردار است.

کلیدواژه‌ها


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

The Comparison of the Integer Programming Models for Solving the Stage Shop Scheduling Problem

نویسنده [English]

  • Mohammad Mahdi Nasiri
چکیده [English]

The development and extending the classic models for approaching the real world conditions are always in consideration of researchers. For this reason, many efforts are made for generalization of the job shop scheduling problem. The stage shop scheduling problem is defined as a generalization of the mixed shop and a special case of the general shop. In a stage shop, each job includes several stages and each stage contains one or more operations. A stage is a subset of the set of the operations of a job so that these operations can be processed in any arbitrary order. In other words, the process of the operations of a stage cannot be initiated unless all the operations of the previous stage are completed. In this paper, two mixed integer programming models are presented for each of the problems "the stage shop scheduling with total weighted tardiness criterion" and "the stage shop scheduling with makespan criterion" (totally four models) and then the models are compared. For the comparison of the efficiency of the proposed models, some problem instances are generated. The computational results show that the second model is more efficient.

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

  • stage shop
  • scheduling
  • total weighted tardiness
  • job shop problem
1.         Nasiri, M.M., F. Kianfar. (2012). “A guided tabu search/path relinking algorithm for the job shop problem”. The International Journal of Advanced Manufacturing Technology, Vol.58, pp. 1105-1113.

2.         Nasiri, M.M., F. Kianfar. (2012). “A GES/TS algorithm for the job shop scheduling”. Computers & Industrial Engineering, Vol.62, pp. 946-952.

3.         Beck, J.C., T. Feng, J.-P. Watson. (2011). “Combining constraint programming and local search for job-shop scheduling”. INFORMS Journal on Computing, Vol.23, pp. 1-14.

4.         Amin-Naseri, M.R., M.A. Beheshti-Nia. (2009). “Hybrid flow shop scheduling with parallel batching”. International Journal of Production Economics, Vol.117, pp. 185-196.

5.         Shakhlevich, N.V., Y.N. Sotskov, F. Werner. (2000). “Complexity of mixed shop scheduling problems: A survey”. European Journal of Operational Research, Vol.120, pp. 343-351.

6.         Nasiri, M.M., F. Kianfar. (2011). “A GA/TS algorithm for the stage shop scheduling problem”. Computers & Industrial Engineering, Vol.61, pp. 161-170.

7.         Carlier, J., E. Pinson. (1989). “An algorithm for solving the job-shop problem”. Management science, Vol.35, pp. 164-176.

8.         Lawrence, S. (1984). “Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement)”. Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania,

9.         Essafi, I., Y. Mati, S. Dauzère-Pérès. (2008). “A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem”. Computers & Operations Research, Vol.35, pp. 2599-2616.