On interactive sequencing situations with exponential cost functions

Alejandro Saavedra-Nieves, Jop Schouten, Peter Borm

Research output: Contribution to journalArticleScientificpeer-review

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.
Original languageEnglish
Pages (from-to)78-89
JournalEuropean Journal of Operational Research
Volume280
Issue number1
DOIs
Publication statusPublished - Jan 2020

Fingerprint

Exponential functions
Cost functions
Sequencing
Cost Function
Cooperative Game
Switches
Completion Time
Queue
Convexity
Switch
Processing
Non-negative
Costs
Path
Optimization
Cost function

Keywords

  • Interactive sequencing situation
  • Exponential cost function
  • Time-dependent neighbor switching gains
  • Sequencing games
  • Convexity

Cite this

@article{3a86cc67aaad4c39865b67f369809177,
title = "On interactive sequencing situations with exponential cost functions",
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.",
keywords = "Interactive sequencing situation, Exponential cost function, Time-dependent neighbor switching gains, Sequencing games, Convexity",
author = "Alejandro Saavedra-Nieves and Jop Schouten and Peter Borm",
year = "2020",
month = "1",
doi = "10.1016/j.ejor.2019.06.044",
language = "English",
volume = "280",
pages = "78--89",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science BV",
number = "1",

}

On interactive sequencing situations with exponential cost functions. / Saavedra-Nieves, Alejandro; Schouten, Jop; Borm, Peter.

In: European Journal of Operational Research, Vol. 280, No. 1, 01.2020, p. 78-89.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - On interactive sequencing situations with exponential cost functions

AU - Saavedra-Nieves, Alejandro

AU - Schouten, Jop

AU - Borm, Peter

PY - 2020/1

Y1 - 2020/1

N2 - 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.

AB - 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.

KW - Interactive sequencing situation

KW - Exponential cost function

KW - Time-dependent neighbor switching gains

KW - Sequencing games

KW - Convexity

U2 - 10.1016/j.ejor.2019.06.044

DO - 10.1016/j.ejor.2019.06.044

M3 - Article

VL - 280

SP - 78

EP - 89

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -