Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems

Dvir Shabtay, Yaron Bensoussan

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

The problem of maximizing the weighted number of just-in-time jobs in a two-machine flow shop scheduling system is known to be N P-hard (Choi and Yoon in J. Shed. 10:237-243, 2007). However, the question of whether this problem is strongly or ordinarily N P-hard remains an open question. We provide a pseudo-polynomial time algorithm to solve this problem, proving that it is N P-hard in the ordinary sense. Moreover, we show how the pseudo-polynomial algorithm can be converted to a fully polynomial time approximation scheme (FPTAS). In addition, we prove that the same problem is strongly N P-hard for both a two-machine job shop scheduling system and a two-machine open shop scheduling system.

اللغة الأصليةإنجليزيّة أمريكيّة
الصفحات (من إلى)39-47
عدد الصفحات9
دوريةJournal of Scheduling
مستوى الصوت15
رقم الإصدار1
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 فبراير 2012

All Science Journal Classification (ASJC) codes

  • !!Software
  • !!General Engineering
  • !!Artificial Intelligence
  • !!Management Science and Operations Research

بصمة

أدرس بدقة موضوعات البحث “Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا