Article Contents
Article Contents

# Sequencing grey games

• The job scheduling problem is a notoriously difficult problem in combinatorial optimization and Operational Research. In this study, we handle the job scheduling problem by using a cooperative game theoretical approach. In the sequel, sequencing situations arising grom grey uncertainty are considered. Cooperative grey game theory is applied to analyze these situations. Further, grey sequencing games are constructed and grey equal gain splitting (GEGS) rule is introduced. It is shown that cooperative grey games are convex. An application is given based on Priority Based Scheduling Algorithm. The paper ends with a conclusion.

Mathematics Subject Classification: Primary: 91A12.

 Citation:

• Figure 1.  An illustration of our application

Figure 2.  Gantt charts of D1

Figure 3.  Gantt charts of D2

Figure 4.  Gantt charts of D3

Table 1.  The properties of each jobs of D1

 Job Arrival Time Execute Time Priority Service Time J1 $\left[ 0, 1\right]$ $\left[ 2, 2\right]$ 1 $\left[ 95, 101\right]$ J2 $\left[ 1, 3\right]$ $\left[ 3, 3\right]$ 2 $\left[ 191, 198\right]$ J3 $\left[ 3, 4\right]$ $\left[ 5, 5\right]$ 3 $\left[ 288, 294\right]$

Table 2.  The properties of each jobs of D2

 Job Arrival Time Execute Time Priority Service Time J1 $\left[ 3, 5\right]$ $\left[ 3, 5\right]$ 2 $\left[ 153, 160\right]$ J2 $\left[ 0, 2\right]$ $\left[ 4, 6\right]$ 1 $\left[ 120, 127\right]$ J3 $\left[ 6, 8\right]$ $\left[ 7, 9\right]$ 3 $\left[ 186, 193\right]$

Table 3.  The properties of each jobs of D3

 Job Arrival Time Execute Time Priority Service Time J1 $\left[ 2, 4\right]$ $\left[ 2, 2\right]$ 2 $\left[ 124, 132\right]$ J2 $\left[ 4, 7\right]$ $\left[ 3, 3\right]$ 3 $\left[ 152, 160\right]$ J3 $\left[ 0, 3\right]$ $\left[ 4, 4\right]$ 1 $\left[ 90, 98\right]$

Table 4.  The wait time t of each jobs of D1, D2 and D3

 $\textbf{Job (Process)}$ $\textbf{Wait Time}$ J1 of D1 $t_{11} = \left[ 95, 100\right]$ J2 of D1 $t_{12} = \left[ 180, 195\right]$ J3 of D1 $t_{13} = \left[ 285, 290\right]$ J1 of D2 $t_{21} = \left[ 150, 155\right]$ J2 of D2 $t_{22} = \left[ 120, 125\right]$ J3 of D2 $t_{23} = \left[ 180, 185\right]$ J1 of D3 $t_{31} = \left[ 120, 125\right]$ J2 of D3 $t_{32} = \left[ 150, 155\right]$ J3 of D3 $t_{33} = \left[ 90, 95\right]$

Table 5.  The weights of c, d, n of J1 for D1, D2, D3

 $\textbf{Property of job}$ $\textbf{Compute Intensity}$ $\textbf{Data parsing}$ $\textbf{Network}$ cost $c$ $d$ $n$ J1D1 3 2 1 J2D1 2 3 1 J3D1 1 2 3 J1D2 3 2 1 J2D2 1 3 2 J3D2 1 2 3 J1D3 3 1 2 J2D3 2 3 1 J3D3 1 1 1

Table 6.  Grey marginal vectors

 $\sigma$ $m_{1}^{\sigma }\left( w^{\prime }\right)$ $m_{2}^{\sigma }\left( w^{\prime }\right)$ $m_{3}^{\sigma }\left( w^{\prime }\right)$ $\sigma _{1} = \left( 1, 2, 3\right)$ $m_{1}^{\sigma _{1}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$ $m_{2}^{\sigma _{1}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$ $m_{3}^{\sigma _{1}}\left( w^{\prime }\right) \in \left[ 68500, 72850\right]$ $\sigma _{2} = \left( 1, 3, 2\right)$ $m_{1}^{\sigma _{2}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$ $m_{2}^{\sigma _{2}}\left( w^{\prime }\right) \in \left[ 68500, 72850\right]$ $m_{3}^{\sigma _{2}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$ $\sigma _{3} = \left( 2, 1, 3\right)$ $m_{1}^{\sigma _{3}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$ $m_{2}^{\sigma _{3}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$ $m_{3}^{\sigma _{3}}\left( w^{\prime }\right) \in \left[ 68500, 72850\right]$ $\sigma _{4} = \left( 2, 3, 1\right)$ $m_{1}^{\sigma _{4}}\left( w^{\prime }\right) \in \left[ 26500, 28050\right]$ $m_{2}^{\sigma _{4}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$ $m_{3}^{\sigma _{4}}\left( w^{\prime }\right) \in \left[ 42000, 44800\right]$ $\sigma _{5} = \left( 3, 1, 2\right)$ $m_{1}^{\sigma _{5}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$ $m_{2}^{\sigma _{5}}\left( w^{\prime }\right) \in \left[ 68500, 72850\right]$ $m_{3}^{\sigma _{5}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$ $\sigma _{6} = \left( 3, 2, 1\right)$ $m_{1}^{\sigma _{6}}\left( w^{\prime }\right) \in \left[ 26500, 28050\right]$ $m_{2}^{\sigma _{6}}\left( w^{\prime }\right) \in \left[ 42000, 44800\right]$ $m_{3}^{\sigma _{6}}\left( w^{\prime }\right) \in \left[ 0, 0\right]$
•  [1] S. Z. Alparslan Gök, R. Branzei, V. Fragnelli and S. Tijs, Sequencing interval situations and related games, CEJOR Cent. Eur. J. Oper. Res., 21 (2013), 225-236.  doi: 10.1007/s10100-011-0226-3. [2] P. Borm, H. Hamers and R. Hendrickx, Operations research games: A survey, Top, 9 (2001), 139-216.  doi: 10.1007/BF02579075. [3] M. E. Bruni, L. D. P. Pugliese, P. Beraldi and F. Guerriero, An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations, Omega, (2016), in press. [4] P. Calleja, M. A. Estevez-Fernandez, P. Borm and H. Hamers, Job scheduling, cooperation, and control, Operations Research Letters, 34 (2006), 22-28.  doi: 10.1016/j.orl.2005.01.007. [5] I. Curiel, G. Pederzoli and S. Tijs, Sequencing games, European Journal of Operational Research, 40 (1989), 344-351.  doi: 10.1016/0377-2217(89)90427-X. [6] I. Curiel, H. Hamers and F. Klijn, Sequencing games: A survey, Chapters in Game Theory, Theory Decis. Lib. Ser. C Game Theory Math. Program. Oper. Res., Kluwer Acad. Publ., Boston, MA, 31 (2002), 27-50.  doi: 10.1007/0-306-47526-X_2. [7] J.-L. Deng, Control problems of grey systems, Systems and Control Letters, 1 (1981/82), 288-294. doi: 10.1016/S0167-6911(82)80025-X. [8] D. G. Feitelson, L. Rudolph, U. Schwiegelshohn, K. C. Sevcik and P. Wong, Theory and practice in parallel job scheduling, Workshop on Job Scheduling Strategies for Parallel Processing, Springer Berlin Heidelberg, (1997), 1–34. [9] E. Köse and J. Y.-L. Forrest, N-person grey game, Kybernetes, 44 (2015), 271-282.  doi: 10.1108/K-04-2014-0073. [10] E. L. Lawler, J. K. Lenstra, A. H. R. Kan and D. B. Shmoys, Sequencing and scheduling: Algorithms and complexity, Handbooks in Operations Research and Management Science, 4 (1993), 445-522. [11] I. S. Lee and S. H. Yoon, Coordinated scheduling of production and delivery stages with stage-dependent inventory holding costs, Omega, 38 (2010), 509-521. [12] R. E. Moore, Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics, 2. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1979. [13] M. O. Olgun, S. Z. Alparslan Gök and G. Özdemir, Cooperative grey games and an application on economic order quantity model, Kybernetes, 45 (2016), 828-838.  doi: 10.1108/K-06-2015-0160. [14] O. Palancı, S. Z. Alparslan Gök, S. Ergün and G.-W. Weber, Cooperative grey games and grey Shapley value, Optimization, 64 (2015), 1657-1668.  doi: 10.1080/02331934.2014.956743. [15] R. Ramasesh, Dynamic job shop scheduling: A survey of simulation research, Omega, 18 (1990), 43-57. [16] S. K. Roy, G. Maity and G.-W. Weber, Multi-objective two-stage grey transportation problem using utility function with goals, CEJOR Cent. Eur. J. Oper. Res., 25 (2017), 417-439.  doi: 10.1007/s10100-016-0464-5. [17] W. E. Smith, Various optimizer for single-stage production, Naval Research Logistics Quarterly, 3 (1956), 59-66.  doi: 10.1002/nav.3800030106. [18] W. Stallings and G. K. Paul, Operating systems: Internals and design principles, Upper Saddle River, NJ: Prentice Hall, 3 (1998). [19] H. Wu and Z. Fang, The graphical solution of zero-sum two-person grey games, Proceedings of 2007 IEEE International Conference on Grey Systems and Intelligent Services, 1/2 (2007), 1617-1620.

Figures(4)

Tables(6)