Group Scheduling with Two Competing Agents on a Single Machine

Shi-Sheng Li () and Ren-Xia Chen ()
Additional contact information
Shi-Sheng Li: College of Science, Zhongyuan University of Technology, Zhengzhou 450007, P. R. China
Ren-Xia Chen: College of Science, Zhongyuan University of Technology, Zhengzhou 450007, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2014, vol. 31, issue 06, 1-13

Abstract: We consider the scheduling problem in which two agents, each with a set of jobs, compete to perform their respective jobs on a single machine under a group technology (GT) environment. The jobs of agents are classified into groups according to their production similarities in advance, all jobs of the same group are required to be processed contiguously on the machine. A sequence-independent setup time precedes the processing of each group. We propose a polynomial time solution for the problem of minimizing the maximum regular cost of one agent, subject to an upper bound on the maximum regular cost of the second agent. We also show that the problem of minimizing the total completion time of the first agent, subject to an upper bound on the maximum lateness of the second agent is strongly $\mathcal {NP}$-hard. The case where all groups of the first agent have the same number of jobs is shown to be polynomially solvable.

Keywords: Single-machine; agent scheduling; group technology (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595914500432
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:31:y:2014:i:06:n:s0217595914500432

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595914500432

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().