sequencinggame {TUGLab} | R Documentation |
Sequencing game
Description
Given a sequencing situation with an initial order, this function returns the characteristic function of the associated sequencing game.
Usage
sequencinggame(p, alpha, pi0, binary = FALSE)
Arguments
p |
A vector containing the processing time of each job. |
alpha |
A vector containing the cost per unit of time that each job generates while unfinished. |
pi0 |
An initial order, as a vector. |
binary |
A logical value. By default, |
Details
Given a coalition S\in 2^N
, \Pi(S)
is the set of orders of S
, that is, the set of all bijective functions from S
to \{1,\ldots, s\}
. A generic order of S
is denoted by \pi_S\in \Pi(S)
.
Given i\in S
and \pi_S\in \Pi(S)
, let Pre^{\pi}(i) =\{j\in S : \pi_S(j) < \pi_S(i)\}
be the set of predecessors of i
according to order \pi_S
.
A sequencing situation is a triple (N,p,\alpha)
and, possibly, some (information on the) initial order, where N=\{1,\ldots,n\}
is a finite set of agents, each one having one job that has to be processed on a machine. To simplify, agent i
's job is identified with i
. The processing times
of the jobs are given by p=(p_i)_{i\in N}
with p_i> 0
for all i\in N
. For each agent i\in N
there is a cost function c_i:(0,\infty)\rightarrow \mathbb{R}
, so that c_i(t)
represents the cost incurred when job i
is completed exactly at time t
. Assuming that c_i
is linear for all i\in N
, there exist \alpha_i,\beta_i\geq 0
such that c_i(t)=\beta_i + \alpha_i t
for all i\in N
, where \beta_i
is a fixed service cost and \alpha_i t
is the completion cost.
For any \pi\in \Pi(N)
, C(S,\pi)
is the aggregate completion cost of coalition S
in the order \pi
, formally defined as
C(S,\pi)=\sum_{i\in S}\alpha_i\Big(p_i+\sum_{j\in Pre^{\pi}(i)}p_j\Big).
A sequencing situation with initial order is a quadruple (N,p,\alpha,\pi_0)
where \pi_0\in\Pi(N)
is the initial order of the jobs.
A coalition S\in 2^N
is said to be connected in order \pi
if, for all i, j\in S
and k\in N
, \pi(i) < \pi(k)< \pi(j)
implies k\in S
. We say that a coalition S'
is a component of S
if S'\subset S
, S'
is connected, and for every i\in S\backslash S'
, S'\cup i
is not connected. The components of S
form a partition of S
that is denoted by S/\pi_0
. Curiel et al. (1989) define the gain of swapping i
and j
as g_{ij}=\max\{0,\alpha_jp_i-\alpha_ip_j\}
.
The sequencing game (N,v_{\pi_0})
is defined, for all S\in 2^N
, by
v_{\pi_0}(S)=\sum_{S'\in S/\pi_0} \left(\sum_{i,j\in S':\pi_0(i)<\pi_0(j)}g_{ij} \right).
Value
The characteristic function of the sequencing game (interpreted as a savings game), as a vector in binary order if binary=TRUE
and in lexicographic order otherwise.
References
Curiel, I., Pederzoli, G., & Tijs, S. (1989). Sequencing games. European Journal of Operational Research, 40(3), 344-351.
See Also
Examples
p <- c(1,2,3,4)
alpha <- c(4,5,1,2)
pi0 <- c(2,3,1,4)
sequencinggame(p, alpha, pi0)