Given a sequencing situation without an initial order, this function returns the characteristic function of the associated tail game.
tailgame(p, alpha, binary = FALSE)The characteristic function of the tail game (interpreted as a cost 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.
A logical value. By default, binary=FALSE.
Given \(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 without initial order is a triple \((N,p,\alpha)\) in which there is no information about an initial order.
An order that minimizes the aggregate completion cost of coalition \(N\) is called an optimal order and denoted by \(\hat{\pi}\). Defining the urgency index of each \(i\in N\) as \(u_i=\frac{\alpha_i}{p_i}\), an optimal order can be obtained by arranging jobs in such a way that the corresponding arrangement of their urgency indices is non-increasing. Given a sequencing situation \((N,p,\alpha)\), \(\Omega(N,p,\alpha)\) denotes the set of those optimal orders that also satisfy the following condition: if two jobs share the same urgency index but not the same processing, the one with shortest processing time goes first.
The characteristic function of the tail game associated to a sequencing situation \((N,p,\alpha)\) is defined, for each \(S\in 2^N\), by
$$c_{tail}(S)=C(S,(\pi_{N\backslash S},\hat{\pi}_S)),$$
where \(\pi_{N\backslash S}\in\Pi(N\backslash S)\) and \(\hat{\pi}_S\in \Omega(S,p_S,\alpha_S)\).
Having no information about an initial order, coalitions assume they will be processed at the tail of some "artificial" initial order.
Klijn, F. & Sánchez, E. (2006). Sequencing games without initial order. Mathematical Methods of Operations Research, 63, 53-62.
sequencinggame
p <- c(1,2,3,4)
alpha <- c(4,5,1,2)
tailgame(p,alpha)
Run the code above in your browser using DataLab