استفاده از برنامه ریزی خطی چندهدفه برای حل مسألۀ زمان بندی چندهدفه تک-ماشینه

This paper develops a fuzzy multi-objective linear programming (FMOLP) model for solving a multi-objective single-machine scheduling problem. The proposed model attempts to minimize the total weighted tardiness and makespan simultaneously. In this problem, a proposed FMOLP method is applied with respect to the overall acceptable degree of the decision maker (DM) satisfaction. A number of numerical examples are solved to show the effectiveness of the proposed approach. The related results are compared with the Wang and Liang's approach. These computational results show that the proposed FMOLP model achieves lower objective functions and higher satisfaction degrees.

Scheduling consists of planning and arranging jobs in an orderly sequence of operations in order to meet customer's requirements [17]. The scheduling of jobs and the control of their flows through a production process are the most significant elements in any modern manufacturing systems. The single-machine environment is the basis for other types of scheduling problems. In single-machine scheduling, there is only one machine to process all jobs optimizing the system performance measures such as makespan, completion time, tardiness, number of tardy jobs, idle times, sum of the maximum earliness and tardiness [18] and [19]. In single-machine scheduling, most research is concerned with minimizing a single criterion. However, scheduling problems often involve more than one aspect and therefore may require multiple criteria analyses [14]. Ishi and Tada [11] considered a single-machine scheduling problem minimizing the maximum lateness of jobs with fuzzy precedence relations. A fuzzy precedence relation relaxes the crisp precedence relation and represents a satisfaction level with respect to the precedence between two jobs. Thus, the problem considers an additional objective in order to maximize the minimum satisfaction level that is obtained by the fuzzy precedence relations. An algorithm for determining non-dominated solutions is proposed based on a graph representation of the precedence relations. Adamopoulos and Pappis [2] presented a fuzzy-linguistic approach to a multi-criteria sequencing problem. They considered a single machine, in which each job is characterized by fuzzy processing times. The objective was to determine the processing times of jobs and the common due as well as to sequence the jobs on the machine where penalty values are associated with due dates assigned, earliness, and tardiness. Another approach to solve a multi-criteria single-machine scheduling problem is presented by Lee et al. [12]. They used linguistic values to evaluate each criterion (e.g., very poor, poor, fair, good, and very good) and to represent its relative weights (e.g., very unimportant, unimportant, moderately important, important, and very important). Also, a tabu search method is used as a stochastic tool to find the near-optimal solution for an aggregated fuzzy objective function. Chanas and Kasperski [6] considered two single-machine scheduling problems with fuzzy processing times and fuzzy due dates. They defined the fuzzy tardiness of a job in a given sequence as a fuzzy maximum of zero and the difference between the fuzzy completion time and the fuzzy due date of this job. In the first problem, they minimized the maximal expected value of a fuzzy tardiness. In the second one, they considered minimizing the expected value of a maximal fuzzy tardiness. Chanas and Kasperski [7] considered the single-machine scheduling problem with parameters given in the form of fuzzy numbers. It is assumed that the optimal schedule in such a problem cannot be determined precisely. In their paper, it is shown how to calculate the degrees of possible and necessary optimality of a given schedule in one of the special cases of single-machine scheduling problems. Azizoglu et al. [4] studied the bi-criteria scheduling problem of minimizing the maximum earliness and the number of tardy jobs on a single machine. They assumed that idle time inserted is not allowed. First, they examined the problem of minimizing maximum earliness while keeping the number of tardy jobs to its minimum value. They also developed a general procedure to find an efficient schedule minimizing a composite function of the two criteria by evaluating only a small fraction of the efficient solutions. They adopted the general procedures for the bi-criteria problem of minimizing the maximum earliness and number of tardy jobs. Eren and Güner [8] considered a bi-criteria single-machine scheduling problem with sequence-dependent setup times. The objective function is to minimize the weighted sum of total completion time and total tardiness. An integer programming model was developed for the problem, which belongs to the NP-hard class. For solving problems containing a large number of jobs, a special heuristic is also used for large-sized problems. To improve the performance of the tabu search (TS) method, the result of the proposed heuristic algorithm was taken as an initial solution of the TS method. Tavakkoli-Moghaddam et al. [20] presented a fuzzy goal programming approach for solving a mixed-integer model of a single-machine scheduling problem minimizing the total weighted flow time and total weighted tardiness. Because of the conflict between these two objectives, they proposed a fuzzy goal programming approach to solve the extended mathematical model of a single-machine scheduling problem. This approach was constructed based on desirability of the decision maker (DM) and tolerances considered on goal values. Huo et al. [10] considered bi-criteria single-machine scheduling problems involving the maximum weighted tardiness and number of tardy jobs. They gave NP-hardness proofs for the scheduling problems when one of these two criteria is the primary criterion and the other one is the secondary criterion. They considered complexity relationships between the various problems and proposed polynomial algorithms for some special cases as well as fast heuristics for the general case. It is well known that the optimal solution of single-objective models can be quite different if the objective is different (e.g., for the simplest model of one machine without any additional constraint, the shortest processing time (SPT) rule is optimal to minimize View the MathML sourceF¯ (i.e., mean flow time) but the earliest due date (EDD) rule is optimal to minimize the maximal tardiness (Tmax)). In fact, each particular decision maker often wants to minimize the given criterion. For example, the commercial manager of a company is interested in satisfying customers and then minimizing tardiness. On the other hand, the production manager wishes to optimize the use of machines by minimizing the makespan or the work in process by minimizing the maximum flow time. In addition, each of these objectives is valid from a general point of view. Since these objectives are conflicting, a solution may perform well for one objective, but giving bad results for others. For this reason, scheduling problems often have a multi-objective nature [14]. Zimmermann [22] first extended his FLP approach to a conventional multi-objective linear programming (MOLP) problem. For each of the objective functions of this problem, it was assumed that the DM has a fuzzy goal such as ‘the objective functions should be essentially less than or equal to some value’. Then, the corresponding linear membership function is defined and the minimum operator proposed by Bellman and Zadeh [5] is applied in order to combine all objective functions. By introducing an auxiliary variable, this problem can be transformed into equivalent, conventional LP problem and can be easily solved by the simplex method. Subsequent work on fuzzy goal programming (FGP) is given in [9], [13], [15] and [16]. The aim of this paper is to develop a fuzzy multi-objective linear programming (FMOLP) model for solving the multi-objective single-machine scheduling problem in the fuzzy environment. First, a MOLP model of a multi-objective single-machine scheduling problem is constructed. The model attempts to minimize the makespan and total weighted tardiness. Furthermore, this model is converted into an FMOLP model by integrating fuzzy sets and objective programming approaches.