Given a sequencing situation with an initial order, this function returns the characteristic function of the associated sequencing game.
sequencinggame(p, alpha, pi0, binary = FALSE)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.
A vector containing the processing time of each job.
A vector containing the cost per unit of time that each job generates while unfinished.
An initial order, as a vector.
A logical value. By default, binary=FALSE.
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).$$
Curiel, I., Pederzoli, G., & Tijs, S. (1989). Sequencing games. European Journal of Operational Research, 40(3), 344-351.
tailgame
p <- c(1,2,3,4)
alpha <- c(4,5,1,2)
pi0 <- c(2,3,1,4)
sequencinggame(p, alpha, pi0)
Run the code above in your browser using DataLab