# American Institute of Mathematical Sciences

January  2020, 7(1): 21-35. doi: 10.3934/jdg.2020002

## Sequencing grey games

 1 Isparta University of Applied Sciences, Faculty of Technology, Department of Computer Engineering, Isparta, Turkey 2 Süleyman Demirel University, Faculty of Economics and Business Administration, Department of Business Administration, Isparta, Turkey 3 Süleyman Demirel University, Faculty of Arts and Sciences, Department of Mathematics, Isparta, Turkey 4 Poznan University of Technology, Chair of Marketing and Economic Engineering, Poznan, Poland

* Corresponding author: zeynepalparslan@yahoo.com

Received  December 2018 Published  December 2019

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.

Citation: Serap Ergün, Osman Palanci, Sirma Zeynep Alparslan Gök, Şule Nizamoğlu, Gerhard Wilhelm Weber. Sequencing grey games. Journal of Dynamics and Games, 2020, 7 (1) : 21-35. doi: 10.3934/jdg.2020002
##### References:
 [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.

show all references

##### References:
 [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.
An illustration of our application
Gantt charts of D1
Gantt charts of D2
Gantt charts of D3
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]$
 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]$
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]$
 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]$
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]$
 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]$
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]$
 $\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]$
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
 $\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
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]$
 $\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] Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics and Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013 [2] İsmail Özcan, Sirma Zeynep Alparslan Gök. On cooperative fuzzy bubbly games. Journal of Dynamics and Games, 2021, 8 (3) : 267-275. doi: 10.3934/jdg.2021010 [3] Mehmet Onur Olgun, Osman Palanci, Sirma Zeynep Alparslan Gök. On the grey Baker-Thompson rule. Journal of Dynamics and Games, 2020, 7 (4) : 303-315. doi: 10.3934/jdg.2020024 [4] Ekaterina Gromova, Ekaterina Marova, Dmitry Gromov. A substitute for the classical Neumann–Morgenstern characteristic function in cooperative differential games. Journal of Dynamics and Games, 2020, 7 (2) : 105-122. doi: 10.3934/jdg.2020007 [5] Zeyang Wang, Ovanes Petrosian. On class of non-transferable utility cooperative differential games with continuous updating. Journal of Dynamics and Games, 2020, 7 (4) : 291-302. doi: 10.3934/jdg.2020020 [6] Deng-Feng Li, Yin-Fang Ye, Wei Fei. Extension of generalized solidarity values to interval-valued cooperative games. Journal of Industrial and Management Optimization, 2020, 16 (2) : 919-931. doi: 10.3934/jimo.2018185 [7] Fabián Crocce, Ernesto Mordecki. A non-iterative algorithm for generalized pig games. Journal of Dynamics and Games, 2018, 5 (4) : 331-341. doi: 10.3934/jdg.2018020 [8] Leon Petrosyan, David Yeung. Shapley value for differential network games: Theory and application. Journal of Dynamics and Games, 2021, 8 (2) : 151-166. doi: 10.3934/jdg.2020021 [9] Serap Ergün, Bariş Bülent Kırlar, Sırma Zeynep Alparslan Gök, Gerhard-Wilhelm Weber. An application of crypto cloud computing in social networks by cooperative game theory. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1927-1941. doi: 10.3934/jimo.2019036 [10] J-F. Clouët, R. Sentis. Milne problem for non-grey radiative transfer. Kinetic and Related Models, 2009, 2 (2) : 345-362. doi: 10.3934/krm.2009.2.345 [11] Kuang Huang, Xuan Di, Qiang Du, Xi Chen. A game-theoretic framework for autonomous vehicles velocity control: Bridging microscopic differential games and macroscopic mean field games. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4869-4903. doi: 10.3934/dcdsb.2020131 [12] Jewaidu Rilwan, Poom Kumam, Onésimo Hernández-Lerma. Stability of international pollution control games: A potential game approach. Journal of Dynamics and Games, 2022, 9 (2) : 191-202. doi: 10.3934/jdg.2022003 [13] Serap Ergün, Sirma Zeynep Alparslan Gök, Tuncay Aydoǧan, Gerhard Wilhelm Weber. Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra's algorithm. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1085-1100. doi: 10.3934/jimo.2018086 [14] Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020 [15] Jiahua Zhang, Shu-Cherng Fang, Yifan Xu, Ziteng Wang. A cooperative game with envy. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2049-2066. doi: 10.3934/jimo.2017031 [16] Yufeng Zhou, Bin Zheng, Jiafu Su, Yufeng Li. The joint location-transportation model based on grey bi-level programming for early post-earthquake relief. Journal of Industrial and Management Optimization, 2022, 18 (1) : 45-73. doi: 10.3934/jimo.2020142 [17] Maolin Cheng, Yun Liu, Jianuo Li, Bin Liu. Nonlinear Grey Bernoulli model NGBM (1, 1)'s parameter optimisation method and model application. Journal of Industrial and Management Optimization, 2022, 18 (3) : 2017-2032. doi: 10.3934/jimo.2021054 [18] Maolin Cheng, Zhun Cheng. A novel simultaneous grey model parameter optimization method and its application to predicting private car ownership and transportation economy. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022081 [19] Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics and Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117 [20] Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics and Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016

Impact Factor: