Scheduling with release dates and preemption to minimize multiple max-form objective functions |
| |
| Institution: | 1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, People’s Republic of China;2. Logistics Research Centre, Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong, People’s Republic of China;1. HEC Liège, Management School of the University of Liège, Liège, Belgium;2. School of Business and Economics, Maastricht University, Maastricht, the Netherlands;1. Department of Economics and Business, University of Catania, Corso Italia, 55, 95129, Catania, Italy;2. Portsmouth Business School, Centre for Operational Research and Logistics (CORL), University of Portsmouth, Portsmouth, United Kingdom;1. Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL 32611, USA;2. Department of Industrial Engineering and Management Systems, University of Central Florida, 12800 Pegasus Dr., Orlando, FL 32816, USA;3. Department of Industrial Engineering, University of Pittsburgh, 1048 Benedum Hall, Pittsburgh, PA 15261, USA;1. Department of Mathematics, Technische Universität Kaiserslautern, Kaiserslautern 67663 Germany;2. CEG-IST, Instituto Superior Técnico, Universidade de Lisboa, Lisboa 1049-001, Portugal;1. Adam Smith Business School, University of Glasgow, UK;2. School of Computing Science, University of Glasgow, UK;3. Trinity Business School, Trinity College Dublin, Ireland;4. School of Management, Northwestern Polytechnical University, China;5. School of Computer Science, University of Lincoln, UK |
| |
| Abstract: | In this paper, we study multi-agent scheduling with release dates and preemption on a single machine, where the scheduling objective function of each agent to be minimized is regular and of the maximum form (max-form). The multi-agent aspect has three versions, namely ND-agent (multiple agents with non-disjoint job sets), ID-agent (multiple agents with an identical job set), and CO-agent (multiple competing agents with mutually disjoint job sets). We consider three types of problems: The first type (type-1) is the constrained scheduling problem, in which one objective function is to be minimized, subject to the restriction that the values of the other objective functions are upper bounded. The second type (type-2) is the weighted-sum scheduling problem, in which a positive combination of the objective functions is to be minimized. The third type (type-3) is the Pareto scheduling problem, for which we aim to find all the Pareto-optimal points and their corresponding Pareto-optimal schedules. We show that the type-1 problems are polynomially solvable, and the type-2 and type-3 problems are strongly NP-hard even when all jobs’ release dates are zero and processing times are one. When the number of the scheduling criteria is fixed and they are all lateness-like, such as minimizing Cmax, Fmax, Lmax, Tmax, and WCmax, where WCmax is the maximum weighted completion time of the jobs, the type-2 and type-3 problems are polynomially solvable. To address the type-3 problems, we develop a new solution technique that guesses the Pareto-optimal points through some elaborately constructed schedule-configurations. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
