Treffer: A Pareto optimal scheduling algorithm for two agents with compatible non-disjoint jobs on an unlimited serial-batch processor.

This paper studies a scheduling problem involving two agents E and F with n 1 and n 2 jobs respectively on a serial-batch processor. The aim is to Pareto optimize the criteria of agent E's maximum completion time (makespan) and agent F's maximum cost. The two agents are compatible (meaning that their jobs can be batched together) and non-disjoint (meaning that their job sets may overlap). The unlimited serial-batch processor can handle an unlimited number of jobs jointly and sequentially in a batch, with the batch's processing time being the sum of the individual jobs contained within it. Additionally, initiating each new batch necessitates a predetermined amount of setup time before the processing begins. An O (n 1 + n 2 3) -time Pareto optimal algorithm is presented which is the first polynomial time algorithm for this problem. For the special case with maximum lateness instead of maximum cost, the obtained algorithm has a better time complexity of O (n 1 + n 2 2 log n 2 ). [ABSTRACT FROM AUTHOR]

Copyright of Central European Journal of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Volltext ist im Gastzugang nicht verfügbar. Login für vollen Zugriff.