Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes

Jun Qiang Wang, Guo Qiang Fan, Yingqian Zhang, Cheng Wu Zhang, Joseph Leung

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

We schedule the jobs from two agents on a single parallel-batching machine with equal processing time and non-identical job sizes. The objective is to minimize the makespan of the first agent subject to an upper bound on the makespan of the other agent. We show that there is no polynomial-time approximation algorithm for solving this problem with a finite worst-case ratio, unless P=NP. Then, we propose an effective algorithm LB to obtain a lower bound of the optimal solution, and two algorithms, namely, reserved-space heuristic (RSH) and dynamic-mix heuristic (DMH), to solve the two-agent scheduling problem. Finally, we evaluate the performance of the proposed algorithms with a set of computational experiments. The results show that Algorithm LB works well and tends to perform better with the increase of the number of jobs. Furthermore, our results demonstrate that RSH and DMH work well on different cases. Specifically, when the optimal makespan on the first agent exceeds the upper bound of the makespan of the other agent, RSH outperforms or equals DMH, otherwise DMH is not less favorable than RSH.

Original languageEnglish (US)
Pages (from-to)478-490
Number of pages13
JournalEuropean Journal of Operational Research
Volume258
Issue number2
DOIs
StatePublished - Apr 16 2017

Fingerprint

Batching
Scheduling
Heuristics
Processing
Approximation algorithms
Upper bound
Polynomials
Computational Experiments
Polynomial-time Algorithm
Scheduling Problem
Approximation Algorithms
Exceed
Schedule
Optimal Solution
Tend
Lower bound
Minimise
Makespan
Evaluate

All Science Journal Classification (ASJC) codes

  • Information Systems and Management
  • Modeling and Simulation
  • Management Science and Operations Research

Cite this

Wang, Jun Qiang ; Fan, Guo Qiang ; Zhang, Yingqian ; Zhang, Cheng Wu ; Leung, Joseph. / Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes. In: European Journal of Operational Research. 2017 ; Vol. 258, No. 2. pp. 478-490.
@article{b84fb72629014db68090afa2b8bf77b0,
title = "Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes",
abstract = "We schedule the jobs from two agents on a single parallel-batching machine with equal processing time and non-identical job sizes. The objective is to minimize the makespan of the first agent subject to an upper bound on the makespan of the other agent. We show that there is no polynomial-time approximation algorithm for solving this problem with a finite worst-case ratio, unless P=NP. Then, we propose an effective algorithm LB to obtain a lower bound of the optimal solution, and two algorithms, namely, reserved-space heuristic (RSH) and dynamic-mix heuristic (DMH), to solve the two-agent scheduling problem. Finally, we evaluate the performance of the proposed algorithms with a set of computational experiments. The results show that Algorithm LB works well and tends to perform better with the increase of the number of jobs. Furthermore, our results demonstrate that RSH and DMH work well on different cases. Specifically, when the optimal makespan on the first agent exceeds the upper bound of the makespan of the other agent, RSH outperforms or equals DMH, otherwise DMH is not less favorable than RSH.",
author = "Wang, {Jun Qiang} and Fan, {Guo Qiang} and Yingqian Zhang and Zhang, {Cheng Wu} and Joseph Leung",
year = "2017",
month = "4",
day = "16",
doi = "https://doi.org/10.1016/j.ejor.2016.10.024",
language = "English (US)",
volume = "258",
pages = "478--490",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes. / Wang, Jun Qiang; Fan, Guo Qiang; Zhang, Yingqian; Zhang, Cheng Wu; Leung, Joseph.

In: European Journal of Operational Research, Vol. 258, No. 2, 16.04.2017, p. 478-490.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes

AU - Wang, Jun Qiang

AU - Fan, Guo Qiang

AU - Zhang, Yingqian

AU - Zhang, Cheng Wu

AU - Leung, Joseph

PY - 2017/4/16

Y1 - 2017/4/16

N2 - We schedule the jobs from two agents on a single parallel-batching machine with equal processing time and non-identical job sizes. The objective is to minimize the makespan of the first agent subject to an upper bound on the makespan of the other agent. We show that there is no polynomial-time approximation algorithm for solving this problem with a finite worst-case ratio, unless P=NP. Then, we propose an effective algorithm LB to obtain a lower bound of the optimal solution, and two algorithms, namely, reserved-space heuristic (RSH) and dynamic-mix heuristic (DMH), to solve the two-agent scheduling problem. Finally, we evaluate the performance of the proposed algorithms with a set of computational experiments. The results show that Algorithm LB works well and tends to perform better with the increase of the number of jobs. Furthermore, our results demonstrate that RSH and DMH work well on different cases. Specifically, when the optimal makespan on the first agent exceeds the upper bound of the makespan of the other agent, RSH outperforms or equals DMH, otherwise DMH is not less favorable than RSH.

AB - We schedule the jobs from two agents on a single parallel-batching machine with equal processing time and non-identical job sizes. The objective is to minimize the makespan of the first agent subject to an upper bound on the makespan of the other agent. We show that there is no polynomial-time approximation algorithm for solving this problem with a finite worst-case ratio, unless P=NP. Then, we propose an effective algorithm LB to obtain a lower bound of the optimal solution, and two algorithms, namely, reserved-space heuristic (RSH) and dynamic-mix heuristic (DMH), to solve the two-agent scheduling problem. Finally, we evaluate the performance of the proposed algorithms with a set of computational experiments. The results show that Algorithm LB works well and tends to perform better with the increase of the number of jobs. Furthermore, our results demonstrate that RSH and DMH work well on different cases. Specifically, when the optimal makespan on the first agent exceeds the upper bound of the makespan of the other agent, RSH outperforms or equals DMH, otherwise DMH is not less favorable than RSH.

UR - http://www.scopus.com/inward/record.url?scp=85006173697&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85006173697&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/j.ejor.2016.10.024

DO - https://doi.org/10.1016/j.ejor.2016.10.024

M3 - Article

VL - 258

SP - 478

EP - 490

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -