Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/90693
| Title: | Scheduling with release dates and preemption to minimize multiple max-form objective functions | Authors: | Yuan, J Ng, CT Cheng, TCE |
Issue Date: | 1-Feb-2020 | Source: | European journal of operational research, 1 Feb. 2020, v. 280, no. 3, p. 860-875 | 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: | Machine scheduling Multi-agent Multi-criteria Pareto scheduling |
Publisher: | Elsevier | Journal: | European journal of operational research | ISSN: | 0377-2217 | EISSN: | 1872-6860 | DOI: | 10.1016/j.ejor.2019.07.072 | Rights: | © 2019 Elsevier B.V. All rights reserved. © 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/. The following publication Yuan, J., Ng, C. T., & Cheng, T. C. E. (2020). Scheduling with release dates and preemption to minimize multiple max-form objective functions. European Journal of Operational Research, 280(3), 860-875 is available at https://dx.doi.org/10.1016/j.ejor.2019.07.072. |
| Appears in Collections: | Journal/Magazine Article |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Yuan_Scheduling_Release_Dates.pdf | Pre-Published version | 1.02 MB | Adobe PDF | View/Open |
Access
View full-text via PolyU eLinks 
Page views
64
Last Week
1
1
Last month
Citations as of May 28, 2023
Downloads
5
Citations as of May 28, 2023
SCOPUSTM
Citations
17
Citations as of Jun 2, 2023
WEB OF SCIENCETM
Citations
17
Citations as of Jun 1, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.