On Interactive Sequencing Situations with Exponential Cost Functions

Alejandro Saavedra-Nieves, Jop Schouten, Peter Borm

Research output: Working paperDiscussion paperOther research output

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.
LanguageEnglish
Place of PublicationTilburg
PublisherCentER, Center for Economic Research
Number of pages23
Volume2018-020
StatePublished - 9 Jul 2018

Publication series

NameCentER Discussion Paper
Volume2018-020

Fingerprint

Exponential functions
Cost functions
Switches
Processing
Costs

Keywords

  • interactive sequencing situation
  • initial order
  • exponential cost function
  • sequencing games
  • convexity

Cite this

Saavedra-Nieves, A., Schouten, J., & Borm, P. (2018). On Interactive Sequencing Situations with Exponential Cost Functions. (CentER Discussion Paper; Vol. 2018-020). Tilburg: CentER, Center for Economic Research.
Saavedra-Nieves, Alejandro ; Schouten, Jop ; Borm, Peter. / On Interactive Sequencing Situations with Exponential Cost Functions. Tilburg : CentER, Center for Economic Research, 2018. (CentER Discussion Paper).
@techreport{79c2d10cd6b14c2a921241fa3767a032,
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-dependentneighbor 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, initial order, exponential cost function, sequencing games, convexity",
author = "Alejandro Saavedra-Nieves and Jop Schouten and Peter Borm",
note = "CentER Discussion Paper Nr. 2018-020",
year = "2018",
month = "7",
day = "9",
language = "English",
volume = "2018-020",
series = "CentER Discussion Paper",
publisher = "CentER, Center for Economic Research",
type = "WorkingPaper",
institution = "CentER, Center for Economic Research",

}

Saavedra-Nieves, A, Schouten, J & Borm, P 2018 'On Interactive Sequencing Situations with Exponential Cost Functions' CentER Discussion Paper, vol. 2018-020, CentER, Center for Economic Research, Tilburg.

On Interactive Sequencing Situations with Exponential Cost Functions. / Saavedra-Nieves, Alejandro; Schouten, Jop; Borm, Peter.

Tilburg : CentER, Center for Economic Research, 2018. (CentER Discussion Paper; Vol. 2018-020).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - On Interactive Sequencing Situations with Exponential Cost Functions

AU - Saavedra-Nieves,Alejandro

AU - Schouten,Jop

AU - Borm,Peter

N1 - CentER Discussion Paper Nr. 2018-020

PY - 2018/7/9

Y1 - 2018/7/9

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-dependentneighbor 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-dependentneighbor 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 - initial order

KW - exponential cost function

KW - sequencing games

KW - convexity

M3 - Discussion paper

VL - 2018-020

T3 - CentER Discussion Paper

BT - On Interactive Sequencing Situations with Exponential Cost Functions

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

Saavedra-Nieves A, Schouten J, Borm P. On Interactive Sequencing Situations with Exponential Cost Functions. Tilburg: CentER, Center for Economic Research. 2018 Jul 9, (CentER Discussion Paper).