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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 פבר׳ 2012

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.2200.2200???
  • ???subjectarea.asjc.1700.1702???
  • ???subjectarea.asjc.1800.1803???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי