Facultade de Fisioterapia

On interactive sequencing situations with exponential cost functions

Saavedra Nieves, Alejandro; Schouten, Jop; Borm, Peter
Abstract:
This paper addresses interactive one-machine sequencing situations in which the costs of processing a job are given by an exponential function of its completion time. The main difference with the standard linear case is that the gain of switching two neighbors in a queue is time-dependent and depends on their exact position. We illustrate that finding an optimal order is complicated in general and we identify specific subclasses, which are tractable from an optimization perspective. More specifically, we show that in these subclasses, all neighbor switches in any path from the initial order to an optimal order lead to a non-negative gain. Moreover, we derive conditions on the time-dependent neighbor switching gains in a general interactive sequencing situation to guarantee convexity of the corresponding cooperative game. These conditions are satisfied within our specific subclasses of exponential interactive sequencing situations. © 2019
Year:
2020
Type of Publication:
Article
Keywords:
Convexity; Exponential cost function; Interactive sequencing situation; Sequencing games; Time-dependent neighbor switching gains
Journal:
European Journal of Operational Research
Volume:
280
Number:
1
Pages:
78-89
Month:
January
Note:
Q1 13/84 h-index 3.806 (JCR2018)
Comments:
A. Saavedra-Nieves acknowledges the financial support of Ministerio de Economía y Competitividad of the Spanish government under grants MTM2014-53395-C3-3-P and MTM2017-87197-C3-2-P , the financial support of Xunta de Galicia through the ERDF ( Grupos de Referencia Competitiva ) ED431C 2016–040 and of Universidade de Vigo through the Convocatoria 2017 de Axudas á investigación, Estadías en centros de investigación .
DOI:
10.1016/j.ejor.2019.06.044
Hits: 372