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, binary=FALSE.

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

tailgame

Examples

p <- c(1,2,3,4)
alpha <- c(4,5,1,2)
pi0 <- c(2,3,1,4)
sequencinggame(p, alpha, pi0)

[Package TUGLab version 0.0.1 Index]