Two-Agent Scheduling on a Bounded Parallel-Batching Machine with Makespan and Maximum Lateness Objectives
- PDF / 237,959 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 9 Downloads / 187 Views
Two-Agent Scheduling on a Bounded Parallel-Batching Machine with Makespan and Maximum Lateness Objectives Qi Feng1 · Wei-Ping Shang2 · Cheng-Wen Jiao1 · Wen-Jie Li3 Received: 18 May 2018 / Revised: 22 January 2019 / Accepted: 5 June 2019 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract This paper studies the two-agent scheduling on a bounded parallel-batching machine. In the problem, there are two agents A and B each having their own job sets with the restriction that the processing times of jobs of agent B are equal. The jobs of different agents can be processed in a common batch. Moreover, each agent has its own objective function to be minimized. The objective function of agent A is the makespan of its jobs, and the objective function of agent B is the maximum lateness of its jobs. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem. Keywords Two-agent scheduling · Parallel-batching · Maximum lateness · Pareto optimal points Mathematics Subject Classification 90B36
This research was supported in part by the National Natural Science Foundation of China (Nos. 11401604, 11571323, 11701595, 11501279) and also supported by Program for Interdisciplinary Direction Team in Zhongyuan University of Technology, China.
B
Qi Feng [email protected] Wei-Ping Shang [email protected] Cheng-Wen Jiao [email protected] Wen-Jie Li [email protected]
1
College of Science, Zhongyuan University of Technology, Zhengzhou 450007, China
2
School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
3
School of Mathematical Sciences, Luoyang Normal University, Luoyang 471022, China
123
Q. Feng et al.
1 Introduction and Problem Formulation Multi-agent scheduling was first introduced by Baker and Smith [1] and Agnetis et al. [2]. In a multi-agent scheduling problem, there are several agents and each agent is associated with a subset of jobs. Each agent has its own objective function which depends on the completion times of its jobs only. However, all the jobs have to share common resources. The objective is to find a schedule of the jobs of all agents, which constitutes a good compromise solution. Today, multi-agent scheduling (especially two-agent scheduling) has developed into a hot topic in scheduling research. According to the current data from web of science, there are more than 3660 articles which studied “multi-agent scheduling”. For a more detailed models and results on multiagent scheduling, we refer the reader to the survey paper by Perez-Gonzalez and Framinan [3] and the book by Agnetis et al. [4]. Moreover, Feng et al. [5], Yuan [6], Li et al. [7], Li and Lu [8] researched other new multi-agent scheduling models. The parallel-batching scheduling problems have been widely discussed in the literature over the last decade. The fundamental model of the parallel-batching scheduling problem was
Data Loading...
