Sequencing grey games

Ergün Serap; Palanci Osman; Alparslan Gök Sirma Zeynep; Nizamoğlu Şule; Weber Gerhard Wilhelm

doi:10.3934/jdg.2020002

Article Contents

2020, Volume 7, Issue 1: 21-35. Doi: 10.3934/jdg.2020002

This issue Previous Article Mean-field games and swarms dynamics in Gaussian and non-Gaussian environments Next Article Game theoretical modelling of a dynamically evolving network Ⅱ: Target sequences of score 1

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
^* Corresponding author: zeynepalparslan@yahoo.com

Received: November 30, 2018

Published: January 2020

Abstract Full Text(HTML) Figure(4) / Table(6) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 91A12.

Citation:

Full Text(HTML)

Figure 1. An illustration of our application

Download: Full-size image PowerPoint slide

Figure 2. Gantt charts of D1

Download: Full-size image PowerPoint slide

Figure 3. Gantt charts of D2

Download: Full-size image PowerPoint slide

Figure 4. Gantt charts of D3

Download: Full-size image PowerPoint slide

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] $

| Show Table

DownLoad: CSV

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] $

| Show Table

DownLoad: CSV

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] $

| Show Table

DownLoad: CSV

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] $

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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] $

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.