تجزیه و تحلیل حساسیت پیشرفته از مسئله تخصیص فازی

This paper concentrates on sensitivity analysis of the fuzzy assignment problem (FAP). Since most real environments are uncertain, the FAP is more realistic than the assignment problem in application. Owing to the high degeneracy of the FAP, as that of the assignment problem, traditional sensitivity analysis, called Type I sensitivity analysis, which determines the range in which the current optimal basis remains optimal, is impractical. Hence, we attempt to perform other two types of advanced sensitivity analysis, called Type II and Type III sensitivity analysis, to overcome this problem. A labeling algorithm is then presented, where Type II sensitivity analysis is to determine the range of perturbation to keep the current optimal assignment remaining optimal, and Type III sensitivity analysis is to determine the range for which the rate of change of optimal value function remains unchanged. The procedure of the labeling algorithm is divided into two parts: one is when the unassigned cell is perturbed, and the other is when the assigned cell is perturbed. An example is presented to demonstrate that the labeling algorithm is a useful tool for determining the Type II and Type III sensitivity analysis of the FAP.

Assignment problem (AP) has been widely used in manufacturing and service systems as well as many indirect applications. The AP can be stated as: Let a number n of jobs be given that must be performed by n workers, where the costs depend on the specific assignments. Each job must be assigned to one and only one worker and each worker has to perform one and only one job. The problem is to find such an assignment that the total cost becomes a minimum [1]. An AP can be formulated as a 0–1 integer programming or linear programming problem as follows: equation(1.1) View the MathML sourcemin∑i=1n∑j=1ncijxijs.t.∑j=1nxij=1 for   i=1,2,…,n, ∑i=1nxij=1 for   j=1,2,…,n, xij∈{0,1}   or   xij≥0 for   i,j=1,2,…,n; Turn MathJax on where cij, the only input parameter, represents the cost associated with worker i (i = 1,2,…,n) who has performed job j (j = 1,2,…,n). All the cij's are deterministic numbers and usually denoted as an n × n matrix C = [cij]. An assignment problem is then defined to choose precisely one element from each row and column so that the total sum is minimized. However, in many real-world applications, costs are not deterministic numbers. In recent years, many researchers have begun to investigate assignment problem and its variants under fuzzy environments. Belacela and Boulasselb [2] studied a multi-criteria fuzzy assignment method applied to medical diagnosis. Ridwan [3] studied a fuzzy preference-based traffic assignment problem. Liu and Li [4] studied the fuzzy quadratic assignment problem with penalty. Feng and Yang [5] studied a two-objective fuzzy k-cardinality assignment problem. Liu and Gao [6] studied the fuzzy weighted equilibrium multi-job assignment problem. Lin and Wen [7] investigated a fuzzy assignment problem (FAP) in which the cost depends on the quality of the job. The quality of job is regarded as the performance of worker. The manager of the workers also has to limit the total cost with a range, and thus the total cost is related to the performance of the manager. Hence, they define the membership function of cost, denoted as View the MathML sourcec˜ij, as the linear monotone increasing function shown in (1.2). α ij is the minimum cost for worker i to perform job j , and β ij is the minimum cost associated with worker i to perform job j at the highest quality q ij. The greater the cost spent, between α ij and β ij, the higher the quality is attained. However, any expense exceeding β ij is useless since the quality can no longer be enhanced. Without loss of generality, it is assumed that 0 < α ij < β ij and they define the quality matrix [q ij] where 0 < q ij ≤ 1. Condition x ij = 1 is added to (1.2) because there is no real expense if x ij = 0 in any feasible solution. equation(1.2) View the MathML sourceμij(cij)=qijif   cij≥βij, xij=1,qij(cij−αij)βij−αijif   αij≤cij≤βij, xij=1,0otherwise. Turn MathJax on Moreover, notation 〈α ij, β ij〉 is employed to denote View the MathML sourcec˜ij. Matrix View the MathML source[c˜ij] is shown as follows: View the MathML source[c˜ij]=[〈αij,βij〉] Turn MathJax on In addition, all the αij's form the matrix [αij] and all the βij's form the matrix [βij]. They also define the membership function of total cost View the MathML sourcec˜T, which is related to the performance of the manager, as the linear monotonically decreasing function in (1.3). Numbers a and b are the lower and upper bounds of total cost, respectively; and notation 〈a , b 〉 denotes the fuzzy interval View the MathML sourcec˜T. It is suggested that a number less than or equal to the minimum assignment of matrix [αij] should be taken as a, and a number larger than or equal to the maximum assignment of matrix [βij] should be taken as b. equation(1.3) View the MathML sourceμT(cT)=μT∑i=1n∑j=1ncijxij=1,cT≤a,b−∑i=1n∑j=1ncijxijb−a=b−cTb−a,a≤cT≤b,0,cT≥b. Turn MathJax on Assume that a team comprises all workers and the manager. The performance of the team is determined by taking the lowest performance of members in the group, the company has to equally emphasize the performance of each member in the group. Hence, the Bellman–Zadeh's criterion [8] is used and the FAP can be derived as: equation(1.4) View the MathML sourcemaxb−∑i=1n∑j=1nαijxijb−a+∑i=1n∑j=1nγijxijs.t.∑j=1nxij=1 for   i=1,2,…,n ∑j=1nxij=1 for   j=1,2,…,n xij∈{0,1} or xij≥0 for   i,j=1,2,…,n Turn MathJax on where γij = (βij − αij)/qij for ∀ i, j, is the slope of the membership function. Furthermore, Lin and Wen [7] proposed an efficient labeling algorithm, denoted as the LW algorithm, for solving (1.4), which is a linear fractional programming problem and extreme-point optimum exists. Note that the constraints of (1.4) are identical to those of (1.1). Hence, the optimal solution of (1.4) is inherently highly primal degenerate and corresponds to several different optimal bases. Consequently, changing the optimal basis does not ensure that the optimal assignment will be changed. Degeneracy thus makes the traditional sensitivity analysis, an important issue after obtaining the optimal solution, impractical. The main objective of this paper is to investigate the properties of the FAP and then propose a modified labeling algorithm to determine two other types of practical sensitivity range. The rest of this paper is organized as follows. Section 2 reviews the concepts of the LW algorithm, types of sensitivity range and various perturbations of the FAP. We then propose the algorithm which is extended from the LW algorithm to determine the two types of sensitivity range in Sections 3 and 4, respectively. Furthermore, two numerical examples are presented in order to demonstrate the proposed approaches. Section 5 concludes the study with a brief summary.

The constraints of FAP are identical to those of AP, which is inherently a highly primal degenerate LP model. Degeneracy negatively influences the computation of an optimal solution and sensitivity analysis of LP. This paper proposes a Type II SA algorithm for identifying Type II SR, which can also be extended for identifying Type III SR of the FAP. The Type II SA algorithm generates a streamlined procedure from searching the optimal solution till performing the sensitivity analysis of assignment problem. Commercially available software can only help to determine Type I SRs, which is impractical in degenerate problems. However, Type II and Type III SRs provide more precise and accurate information and help make correct decisions. We summarize the relationships between three types of sensitivity ranges as follows: (1) Type I SR is always a subset of Type II SR; (2) since Type III sensitivity depends only on the problem data and perturbing parameter, it is independent of Type I and Type II sensitivity analysis; (3) if there is only one optimal assignment, then Type II SR and Type III SR are identical; and (4) when optimal value function happens to be a breakpoint at Δst = 0, Type III SR = [0,0] will be a subset of Type II SR. There are several application areas of this study, such as human resource management, job assignment planning, transportation planning, fuzzy network planning, etc. Besides, the further extensions and applications of this research are suggested in following directions: 1. Consider the perturbation more than one parameter. In the real world applications, it is usual that perturbation occurs on more than one parameters, e.g., perturbing αij and γij at the same time, one column of matrix αij, or one row of matrix qij, etc. 2. Extend the two-dimensional fuzzy assignment problem to multi-dimensional fuzzy assignment problem and develop a solution algorithm and sensitivity analysis procedure for the multi-dimensional fuzzy assignment problem. Multi-dimensional assignment problems have been widely used in scheduling problem, capital investment and facility location problem, etc.