
-
Previous Article
Game theoretical modelling of a dynamically evolving network Ⅱ: Target sequences of score 1
- JDG Home
- This Issue
-
Next Article
Mean-field games and swarms dynamics in Gaussian and non-Gaussian environments
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 |
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.
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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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). Google Scholar |
[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. Google Scholar |
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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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). Google Scholar |
[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. Google Scholar |




Job | Arrival Time | Execute Time | Priority | Service Time |
J1 | 1 | |||
J2 | 2 | |||
J3 | 3 |
Job | Arrival Time | Execute Time | Priority | Service Time |
J1 | 1 | |||
J2 | 2 | |||
J3 | 3 |
Job | Arrival Time | Execute Time | Priority | Service Time |
J1 | 2 | |||
J2 | 1 | |||
J3 | 3 |
Job | Arrival Time | Execute Time | Priority | Service Time |
J1 | 2 | |||
J2 | 1 | |||
J3 | 3 |
Job | Arrival Time | Execute Time | Priority | Service Time |
J1 | 2 | |||
J2 | 3 | |||
J3 | 1 |
Job | Arrival Time | Execute Time | Priority | Service Time |
J1 | 2 | |||
J2 | 3 | |||
J3 | 1 |
J1 of D1 | |
J2 of D1 | |
J3 of D1 | |
J1 of D2 | |
J2 of D2 | |
J3 of D2 | |
J1 of D3 | |
J2 of D3 | |
J3 of D3 |
J1 of D1 | |
J2 of D1 | |
J3 of D1 | |
J1 of D2 | |
J2 of D2 | |
J3 of D2 | |
J1 of D3 | |
J2 of D3 | |
J3 of D3 |
cost | |||
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 |
cost | |||
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 |
[1] |
Laura Aquilanti, Simone Cacace, Fabio Camilli, Raul De Maio. A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions. Journal of Dynamics & Games, 2020 doi: 10.3934/jdg.2020033 |
[2] |
Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051 |
[3] |
Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 |
[4] |
Van Duong Dinh. Random data theory for the cubic fourth-order nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020284 |
[5] |
Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020174 |
[6] |
Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021001 |
[7] |
Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 |
[8] |
Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020451 |
[9] |
Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054 |
[10] |
Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020 doi: 10.3934/mcrf.2020047 |
[11] |
David W. K. Yeung, Yingxuan Zhang, Hongtao Bai, Sardar M. N. Islam. Collaborative environmental management for transboundary air pollution problems: A differential levies game. Journal of Industrial & Management Optimization, 2021, 17 (2) : 517-531. doi: 10.3934/jimo.2019121 |
[12] |
Paul E. Anderson, Timothy P. Chartier, Amy N. Langville, Kathryn E. Pedings-Behling. The rankability of weighted data from pairwise comparisons. Foundations of Data Science, 2021 doi: 10.3934/fods.2021002 |
[13] |
Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020458 |
[14] |
Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024 |
[15] |
Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310 |
[16] |
Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026 |
[17] |
Anna Anop, Robert Denk, Aleksandr Murach. Elliptic problems with rough boundary data in generalized Sobolev spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020286 |
[18] |
Haruki Umakoshi. A semilinear heat equation with initial data in negative Sobolev spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 745-767. doi: 10.3934/dcdss.2020365 |
[19] |
Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020347 |
[20] |
Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]