\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Sequencing grey games

Abstract Full Text(HTML) Figure(4) / Table(6) Related Papers Cited by
  • 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:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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] $
     | 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
  • [1] S. Z. Alparslan GökR. BranzeiV. 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. BormH. 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. CallejaM. A. Estevez-FernandezP. 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. CurielG. 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. CurielH. 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. LawlerJ. K. LenstraA. 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. OlgunS. 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ökS. 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. RoyG. 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)

SHARE

Article Metrics

HTML views(1733) PDF downloads(428) Cited by(0)

Access History

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return