In this paper, we develop branch-and-bound algorithms for several hard, two-agent scheduling problems, i.e., problems in which each agent has an objective function which depends on the completion times of its jobs only. Our bounding approach is based on the fact that, for all problems considered, the Lagrangian dual gives a good bound and can be solved exactly in strongly polynomial time. The problems addressed here consist in minimizing the total weighted completion time of the jobs of agent A, subject to a bound on the cost function of agent B, which may be: (i) total weighted completion time, (ii) maximum lateness, (iii) maximum completion time. An extensive computational experience shows the effectiveness of the approach.

Agnetis, A., G., D.P., & D., P. (2009). A Lagrangian approach to single-machine scheduling problems with two competing agents. JOURNAL OF SCHEDULING, 12, 401-415.

A Lagrangian approach to single-machine scheduling problems with two competing agents

AGNETIS, ALESSANDRO;
2009

Abstract

In this paper, we develop branch-and-bound algorithms for several hard, two-agent scheduling problems, i.e., problems in which each agent has an objective function which depends on the completion times of its jobs only. Our bounding approach is based on the fact that, for all problems considered, the Lagrangian dual gives a good bound and can be solved exactly in strongly polynomial time. The problems addressed here consist in minimizing the total weighted completion time of the jobs of agent A, subject to a bound on the cost function of agent B, which may be: (i) total weighted completion time, (ii) maximum lateness, (iii) maximum completion time. An extensive computational experience shows the effectiveness of the approach.
File in questo prodotto:
File Dimensione Formato  
a lagrangian approach to single-machine scheduling problems with two competing agents.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 642.23 kB
Formato Adobe PDF
642.23 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/23316
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo