ابزار پشتیبانی تصمیم برای مشکلات برنامه ریزی تولید کارگاهی چندهدفه با توابع تصمیم گیری معرف های کمی زبانشناختی

This paper presents a new tool for multi-objective job shop scheduling problems. The tool encompasses an interactive fuzzy multi-objective genetic algorithm (GA) which considers aspiration levels set by the decision maker (DM) for all the objectives. The GA's decision (fitness) function is defined as a measure of truth of a linguistically quantified statement, imprecisely specified by the DM using linguistic quantifiers such as most, few, etc., that refer to acceptable distances between the achieved objective values and the aspiration levels. The linguistic quantifiers are modelled using fuzzy sets. The developed tool is used to analyse and solve a real-world problem defined in collaboration with a pottery company. The tool provides a valuable support in performing various what-if analyses, for example, how changes of batch sizes, aspiration levels, linguistic quantifiers and the measure of acceptable distances affect the final schedule.

Scheduling problems have a vital role in most manufacturing and production systems. They concern allocation of scarce resources to tasks over a period of time [17]. These problems are generally defined as decision-making problems with the aim of optimising one or more scheduling criteria. The diversity of scheduling problems, large-scale dimensions and their dynamic nature make scheduling problems computationally very complex and difficult to solve. A job shop scheduling problem is described by a number of jobs to be processed on a number of machines, each job consisting of a set of operations to be processed in a predetermined order. The aim of the job shop scheduling problem is to find the best sequence of operations on each machine in order to minimise or maximise a specific objective or a set of objectives. This problem is NP-complete; hence, various heuristic approaches have been developed to solve it. Local search methods such as simulated annealing [1] and [21], tabu search [18], genetic algorithms (GA) [16], [22] and [26] and hybrid GAs [11] have been successfully applied to job shop problems yielding good results. Although most scheduling investigations have been focused on single objective scheduling problems, in practice, most often these problems are multi-objective. Hoogeveen [14] presented a survey of multi-criteria scheduling problems where the most common scheduling performance criteria were identified. The author surveyed different approaches to solving single machine, parallel machine, job shop and open shop bi-criteria scheduling problems. Recently, a number of approaches have been proposed to solving multi-objective job shop scheduling problems [19]. For example, Itoh et al. [15] proposed a twofold look-ahead search to solve a bi-criteria job shop scheduling problem. Fonseca and Fleming [8] developed a generic multi-objective genetic optimiser that presents a set of points to the DM for evaluation in each generation of the GA. After the assessment is made, the DM communicates his or her preferences to the GA, and the GA proceeds with the next generation. Brandimarte and Maiocco [6] solved a bi-criteria job shop scheduling problem by developing suitable neighbourhood structures. Esquivel et al. [7] studied the influence of different evolutionary algorithm's parameter combinations and chromosome representations in diverse multi-objective optimisation problems including the multi-objective job shop problem. Baykasoglu et al. [4] developed a multi-objective tabu search combined with a Giffler and Thompson's priority rule-based heuristic to solve a flexible job shop problem. Gorczyca et al. [12] proposed a new approach to multi-objective job shop scheduling problems in the presence of limited resources, based on priority dispatching rules with two objectives, namely minimisation of makespan and minimisation of resource consumption. They developed a multi-objective genetic algorithm based on a two-component chromosome that represented weights associated with the priority dispatching rules and proportions of resources allocated to operations. Bagchi [3] discussed multi-objective GAs-based approaches to a variety of scheduling problems. In order to solve multi-objective problems considering imprecise nature of DM's judgements, optimisation techniques have been combined with concepts of fuzzy sets theory. Bellman and Zadeh [5] introduced a framework for solving both single and multi-objective optimisation problems in fuzzy environments. They defined a single decision function that aggregates degrees of satisfaction achieved with respect to both fuzzy objectives and fuzzy constraints. In this context, operator minimum has been most often used as an aggregation operator [27]. This paper presents a new approach to solving multi-objective job shop scheduling problems taking into consideration the DM preferences. They are expressed using aspiration levels where the aspiration levels represent “attainment levels of the objectives which the DM personally desires to achieve” [10]. The GA's fitness function is defined as a measure of truth of a linguistically quantified statement expressed in terms of distances between the achieved objective values and the corresponding aspiration levels, such as ‘many distances are acceptable’, ‘most distances are acceptable’ and so on. An algebraic method is used to evaluate the degree of truth of the linguistically quantified statement. The new approach is applied to a real life job shop scheduling problem identified in collaboration with a manufacturing pottery company. The paper is organised as follows. A multi-objective job shop scheduling problem is defined in Section 2. In Section 3, the new multi-objective GA for the multi-objective job shop problem is described including the GA's fitness function, the job shop problem representation scheme and the GA's operators. Additionally, Section 4 introduces a real-world scheduling problem and analysis of results obtained by using the multi-objective GA. Main conclusions and directions for future work are presented in Section 5.

A new decision support tool for analysing and solving multi-objective job shop scheduling problems that combines GAs and fuzzy sets is developed and implemented. It is an interactive tool that allows the DM to set aspiration levels and modify them sequentially. The objectives considered are incommensurable, i.e., given in different units of measure with different scales. The objectives are handled simultaneously by introducing the normalised distance between the achieved objective values and the aspiration levels. The GA's fitness function is defined as a measure of truth of a linguistically quantified statement, specified in terms of the normalised distances between the achieved objective values and the aspiration levels. The algebraic method is used to evaluate the degree of truth of the linguistically quantified statement. A real-world job shop scheduling problem defined in collaboration with a pottery company has been analysed and solved using the developed tool. It is shown that the tool is very flexible in different aspects and can be applied in treating real life scheduling problems. It can be applied to a problem with any number of jobs, machines and objectives to be optimised. In addition, the tool can operate with different batch sizes of the jobs and can be used to perform the what-if analysis with respect to batch sizes. It can also be used to analyse the effects of different aspiration levels on the quality of the solutions. Finally, the tool enables the DM to express preferences regarding multiple objectives using natural language expressions and linguistic qualifiers. Further work will be undertaken including: – investigation of different linguistically quantified statements to be used in GA's fitness functions, – development of different methods to evaluate degree of truth of the linguistically quantified statements that take into consideration the allocation of satisfaction degrees associated with the objectives, instead of the algebraic method that considers a cumulative satisfaction degree only, – incorporation of objective weights into the GA in order to model different objective priorities, – investigation of additional objectives that are of interest for the pottery scheduling problem under consideration, such as to maximise throughput, to minimise energy consumption, etc.