Just-in-time scheduling with two competing agents on unrelated parallel machines

Yunqiang Yin, Shuenn Ren Cheng, Edwin Tai Chiu Cheng, Du Juan Wang, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

44 Citations (Scopus)

Abstract

The objective of agent A is to maximize the weighted number of its just-in-time jobs that are completed exactly on their due dates, while the objective of agent B is either to maximize its maximum gain (income) from its just-in-time jobs or to maximize the weighted number of its just-in-time jobs. We provide a bicriterion analysis of the problem, which seek to find the Pareto-optimal solutions for each combination of the two agents׳ criteria. When the number of machines is part of the problem instance, both the addressed problems are NP-hard in the strong sense. When the number of machines is fixed, we show that the problem of maximizing agent A׳s weighted number of just-in-time jobs while maximizing agent B׳s maximum gain can be solved in polynomial time, whereas the problem of maximizing both agents׳ weighted numbers of just-in-time jobs is NP-hard. For the latter problem, we also provide a pseudo-polynomial-time solution algorithm, establishing that it is NP-hard in the ordinary sense, and show that it admits a fully polynomial-time approximation scheme (FPTAS) for finding an approximate Pareto solution.
Original languageEnglish
Pages (from-to)41-47
Number of pages7
JournalOmega (United Kingdom)
Volume63
DOIs
Publication statusPublished - 1 Jan 2016

Keywords

  • FPTAS
  • Just-in-time scheduling
  • Scheduling
  • Two agents
  • Unrelated parallel machines

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Information Systems and Management

Cite this