Concurrent open shop scheduling to minimize the weighted number of tardy jobs

Research output: Journal article publicationJournal articleAcademic researchpeer-review

30 Citations (Scopus)

Abstract

We consider a relaxed version of the open shop scheduling problem - the "concurrent open shop" scheduling problem, in which any two operations of the same job on distinct machines are allowed to be processed concurrently. The completion time of a job is the maximum completion time of its operations. The objective is to schedule the jobs so as to minimize the weighted number of tardy jobs, with 0-1 operation processing times and a common due date d. We show that, even when the weights are identical, the problem has no (1-ε)ln m-approximation algorithm for any ε > 0 if NP is not a subset of DTIME(nloglogn), and has no c > ln m-approximation algorithm for some constant c > 0 if P≠NP, where m is the number of machines. This also implies that the problem is strongly NP-hard. We also give a (1+d)-approximation algorithm for the problem.
Original languageEnglish
Pages (from-to)405-412
Number of pages8
JournalJournal of Scheduling
Volume6
Issue number4
DOIs
Publication statusPublished - 1 Jul 2003

Keywords

  • Concurrent open shop
  • Due date
  • In-approximability
  • Scheduling

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Management Science and Operations Research

Cite this