We tackle a single-machine scheduling problem, characterized by two sets of identical jobs contributing to a common objective function, aimed at balancing the average completion times. For solving this problem, that we show it reduces to a particular case of the subset-sum problem, we propose an exact algorithm, pointing out the existence of different optimal solutions. Without considering explicitly the job-position assignment procedure, which necessarily would require at least a linear time, the problem is solvable in constant time. A variant of such a problem is also considered.
A subset-sum type formulation of a two-agent single-machine scheduling problem
AVOLIO, MATTEO;Fuduli, Antonio
2020-01-01
Abstract
We tackle a single-machine scheduling problem, characterized by two sets of identical jobs contributing to a common objective function, aimed at balancing the average completion times. For solving this problem, that we show it reduces to a particular case of the subset-sum problem, we propose an exact algorithm, pointing out the existence of different optimal solutions. Without considering explicitly the job-position assignment procedure, which necessarily would require at least a linear time, the problem is solvable in constant time. A variant of such a problem is also considered.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.