Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)

Abstract

We consider the scheduling problem in which two agents (agents A and B), each having its own job set (containing the A-jobs and B-jobs, respectively), compete to process their own jobs in a two-machine flowshop. Each agent wants to maximize a certain criterion depending on the completion times of its jobs only. Specifically, agent A desires to maximize either the weighted number of just-in-time (JIT) A-jobs that are completed exactly on their due dates or the maximum weight of the JIT A-jobs, while agent B wishes to maximize the weighted number of JIT B-jobs. Evidently four optimization problems can be formulated by treating the two agents’ criteria as objectives and constraints of the corresponding optimization problems. We focus on the problem of finding the Pareto-optimal schedules and present a bicriterion analysis of the problem. Solving this problem also solves the other three problems of bicriterion scheduling as a by-product. We show that the problems under consideration are either polynomially or pseudo-polynomially solvable. In addition, for each pseudo-polynomial-time solution algorithm, we show how to convert it into a two-dimensional fully polynomial-time approximation scheme for determining an approximate Pareto-optimal schedule. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.
Original languageEnglish
Pages (from-to)313-335
Number of pages23
JournalJournal of Scheduling
Volume20
Issue number4
DOIs
Publication statusPublished - 1 Aug 2017

Keywords

  • Bicriterion analysis
  • Flowshop
  • Two-agent scheduling
  • Two-dimensional FPTAS

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Cite this