A New Approach for Solving Grey Assignment Problems

Document Type: بنیادی - نظری


1 Department of Mathematical Sciences, University of Mazandaran, Babolsar, Iran

2 ‎Department of Mathematics, Payame Noor University, Tehran, Iran

3 ‎Department of Mathematical Sciences, University of Mazandaran, Babolsar, Iran


Linear assignment problem is one of the most important practical models in the literature of linear programming problems‎. ‎Input data in the cost matrix of the linear assignment problem are not always crisp and sometimes in the practical situations is formulated by the grey systems theory approach‎. ‎In this way‎, ‎some researchers have used a whitening technique to solve the grey assignment problem‎. ‎Since the whitening technique only provides a crisp equivalent model and does not reflect the evolutionary characteristics of a grey set‎, ‎it cannot keep the uncertainty properties in an interval involving the optimal solution‎. ‎Based on these shortcomings‎, ‎in this paper a new direct approach is introduced to solve linear assignment problem in grey environments‎. ‎For preparing the mentioned method‎, ‎some theoretical results are given to support the methodology‎. ‎Finally‎, ‎a numerical example will be solved to test the validity of the proposed method‎. ‎Based on the suggested methodology‎, ‎we emphasize that the same approach can be used whenever any linear programming model is formulated in grey environments.


Main Subjects

[1] Albrecher H‎. ‎(2005)‎. ‎`` A note on the asymptotic behavior of bottleneck problems‎ ", ‎Operations Research Letters‎, ‎33‎, ‎183–186‎.

[2] ‎Aldous D‎. ‎(1992)‎. ‎`` Asymptotic in the random assignment problem‎ ", ‎Probability Theory and Related Fields‎, ‎93‎, ‎507–534‎.

[3] ‎Anstreicher K‎. ‎M‎. ‎(2003)‎. ‎``Recent advances in the solution of quadratic assignment problems"‎, ‎Mathematical Programming‎, ‎97(1-2)‎, ‎27–42‎.

[4] ‎Avis D.‎, ‎Devroye L‎. ‎(1985)‎. ‎``An analysis of a decomposition heuristic for the assignment problem"‎, ‎Operations Research Letters‎, ‎3(6)‎, ‎279-283‎.‎

[5] ‎Bai G‎. ‎(1992)‎. ‎`` Grey assignment problem‎ ", ‎Chinese Journal of Operation Research‎, ‎11(2)‎, ‎67–69‎.

[6] ‎Bai G‎. ‎Z‎. ‎(2009)‎. ‎`` Grey assignment problems‎ ", ‎Fuzzy Information and Engineering‎, ‎54‎, ‎245-250‎.

[7] ‎Bashiri M.‎, ‎Badri H.‎, ‎and Hejazi T‎. ‎H‎. ‎(2011)‎. ‎`` Selecting optimum maintenance strategy by fuzzy interactive linear assignment method‎ ", ‎Applied Mathematical Modelling‎, ‎35(1)‎, ‎152-164‎.

[8] ‎Bernardo J‎. ‎J‎. ‎and Blin J‎. ‎M‎. ‎(1977)‎. ‎`` A programming model of consumer choice among multi-attributed brands‎ ", ‎Journal of Consumer Research‎, ‎4(2)‎, ‎111-118‎.

[9] ‎Cheng F‎. ‎J.‎, ‎Hui S‎. ‎H.‎, ‎and Chen Y‎. ‎C‎. ‎(2002)‎. ‎`` Reservoir operation using grey fuzzy stochastic dynamic programming‎ ", ‎Hydrological Processes‎, ‎16‎, ‎2395-2408‎.

[10] ‎Deng J‎. ‎L‎. ‎(1982)‎. ‎`` The control problems of grey systems‎ ", ‎Systems and Control Letters‎, ‎15‎, ‎288–294‎.

[11] ‎Deng J‎. ‎L‎. ‎(1982)‎. ‎`` Introduction to grey system theory‎ ", ‎The Journal of Grey Systems‎, ‎1(1)‎, ‎1-24‎.

[12] ‎Eberhardt S‎. ‎P.‎, ‎Duad Kerns T‎. ‎A.‎, ‎Brown T‎. ‎X‎. ‎and Thakoor A‎. ‎P‎. ‎(1991)‎. ‎`` Competitive neural architecture for hardware solution to the assignment problem‎ ", ‎Neural Networks‎, ‎4(4)‎, ‎431-442‎.

[13] ‎Kuhn H‎. ‎W‎. ‎(1955)‎. ‎`` The hungarian method for the assignment problem‎ ", ‎Naval Research Logistics Quarterly‎, ‎2‎, ‎83-97‎.

[14] ‎Li Q‎. ‎X‎. ‎and Lin Y‎. ‎(2014)‎. ‎`` A briefing to grey systems theory‎ ", ‎Journal of Systems Science and Information‎, ‎2(2)‎, ‎178-192‎.

[15] ‎Li Q‎. ‎X.‎, ‎and Liu S‎. ‎F‎. ‎(2008)‎. ‎`` The foundation of the grey matrix and the grey input-output analysis‎ ", ‎Applied Mathematical Modelling‎, ‎32‎, ‎267–291‎.‎

[16] ‎Lin Y.‎, ‎Chen M‎. ‎Y‎. ‎and Liu S‎. ‎F‎. ‎(2004)‎. ‎`` Theory of grey systems‎: ‎capturing uncertainties of grey information‎ ", ‎Kybernetes‎, ‎33(2)‎, ‎196-218‎.

[17] ‎Liu S‎. ‎F‎. ‎and Lin Y‎. ‎(2006)‎. ‎`` Grey information‎, ‎theory and practical applications‎ ", ‎Springer‎.

[18] ‎Liu S‎. ‎F‎. ‎and Lin Y‎. ‎(2011)‎. ‎`` Grey systems‎: ‎Theory and applications‎ ", ‎Springer-Verlag‎, ‎Berlin‎.

‎[19] ‎Majumdar S‎. ‎(2013)‎. ‎`` Interval linear assignment problems‎ ", ‎Universal Journal of Applied Mathematics‎, ‎1(1)‎, ‎14-16‎.

[20] ‎Mcginnis L‎. ‎F‎. ‎(1983)‎. ‎`` Implementation and testing of a primal-dual algorithm for the assignment problem‎ ", ‎Operations Research‎, ‎31(2)‎, ‎277-291‎.

[21] ‎Nagoor Gani A‎. ‎and Mohamed V‎. ‎N‎. ‎(2013)‎. ‎`` Solution of a fuzzy assignment problem by using a new ranking method‎ ", ‎International Journal of Fuzzy Mathematical Archive‎, ‎2‎, ‎8-16‎.

[22] ‎Nasseri S‎. ‎H.‎, ‎Yazdani A.‎, ‎and Darvishi Salikolaei D‎. ‎(2016)‎. ‎`` A primal simplex algorithm for solving linear programming problem with grey cost coefficients‎ ", ‎Journal of New Researches in Mathematics‎, ‎1(4)‎, ‎121-141‎.

[23] ‎Pardalos P‎. ‎M‎. ‎and Pitsoulis L‎. ‎(2000)‎. ‎`` Nonlinear assignment problems‎: ‎Algorithms and applications‎ ", ‎Kluwer Academic Publishers‎.

[24] ‎Ramesh Kumar A‎. ‎and Deepa S‎. ‎(2014)‎. ‎`` Restrictions of interval assignment problem using Hungarian method‎ ", ‎International Journal in IT and Engineering‎, ‎2(12)‎, ‎56-61‎.

[25] ‎Ramesh G‎. ‎and Ganesan K‎. ‎(2015)‎. ‎`` Assignment problem with generalized interval arithmetic‎ ", ‎International Journal of Scientific and Engineering Research‎, ‎6(3)‎, ‎82-85‎.

[26] ‎Thorani Y‎. ‎L‎. ‎P‎. ‎and Ravi Shankar N‎. ‎(2013)‎. ‎`` Fuzzy assignment problem with generalized fuzzy numbers‎ ", ‎Applied Mathematical Sciences‎, ‎7(71)‎, ‎3511-3537‎.‎

[27] Wang Z‎. ‎X‎. ‎(2013)‎. ‎`` Correlation analysis of sequences with interval grey numbers based on the kernel and greyness degree‎ ", ‎Kybernetes‎, ‎42(2)‎, ‎309-317‎.

[28] ‎Wu Q‎. ‎(2013)‎. ‎`` Construction and application of grey concept lattices‎ ", ‎Informatica‎, ‎24(1)‎, ‎153-168‎.

[29] ‎Xie N‎. ‎M‎. ‎and Liu S‎. ‎F‎. ‎(2011)‎. ‎`` A novel grey relational model based on grey number sequences‎ ", ‎Grey Systems‎: ‎Theory and Application‎, ‎1(2)‎, ‎117-128‎.

‎[30] ‎Yang Y‎. ‎and John R‎. ‎(2012)‎. ‎`` Grey sets and greyness‎ ", ‎Information Sciences‎, ‎185‎, ‎249-264‎.