Minimizing a Genera l Penalty Funct ion on a Single Machine Via Develo ping Approxima tion Al gorithm s and FP TASs

  • سال انتشار: 1396
  • محل انتشار: فصلنامه بین المللی مهندسی صنایع و تحقیقات تولید، دوره: 28، شماره: 3
  • کد COI اختصاصی: JR_IJIEPR-28-3_001
  • زبان مقاله: انگلیسی
  • تعداد مشاهده: 301
دانلود فایل این مقاله

نویسندگان

Kamran kianfar

Faculty of Enginee ring, Universi ty of Isfahan

gasem moslehi

Depart ment of Indus rial and Syst ems Engineering, Isfahan niversity of echnology

چکیده

This paper addresses the Tardy/Lost pen alty minimization on a single ma chine. According to this penalty criterion, if the tardiness of a job exceeds a predefined value, the job will be lost and penalized by a fixed value. Besides its application in real world problems, Tardy/Lo st measure is a general form of popular objective functions such as w eighted tardiness, lat e work and tardiness with rejec tion; hence, the res ults of thi s study are applicabl to them. Initially, we present two approximation algorithms. Then, t wo special cases of the main p roblem are considere d. In the first case, all jobs have the sam e tardiness weights here a fully polyno mial time approxima ion scheme(FPTAS) is developed using the techniq ue of str ucturing the execution of an algo r ithm . The second special case occurs when none of t he jobs can be early. For this c ase, a 2-approximation and a dyn amic prog ramming a gorithms are develop ed, were the latter is c onverted to an FPTAS.

کلیدواژه ها

Single mac hine scheduling, Tardy/Lost penalty, Dynamic programming, Approxima tion algorith m, FPTAS

مقالات مرتبط جدید

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

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

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