Optimization Multicriteria Scheduling Criteria through Analytical Hierarchy Process and Lexicographic Goal Programming Modeling

Abstract

The rapidity of technological development and multi-criteria decision-making (MCDM) has enabled a diversity of models and multi-criteria decision support methods. Then, in Multi-criteria Decision Making problems dealing with qualitative criteria and uncertain information is suitable for the experts in order to express their judgments. It is common that the group of experts involved in such problems have different degrees of knowledge about the criteria. MCDM problems have been solved in the literature by using different methods, In this chapter we propose the multicriteria methodology to solve problem scheduling criteria based of application the Analytical hierarchy process methods and lexicographic goal programming.

1. Introduction

Production scheduling is the technique of production control, the purpose of which is to enable the production program to be carried out on time, at minimum cost.

The objective is to find a schedule, an optimal program from the M possible scheduling sequences, where j is the number of jobs and M the number of machines.

The scheduling problem becomes even more complex when it occurs in an open and dynamic environment, where changes in the number of jobs or machines can occur at any time.

The scheduling problem has been addressed, mainly due to its combinatorial aspects, dynamic nature, and applicability in manufacturing systems [1] and many scheduling methods have been developed, based on different techniques such as heuristics, linear programming, constraint satisfaction techniques, La grangienne relaxation, neighborhood search techniques (eg annealing by simulation or taboo search) and genetic algorithms [2]. The aim of this chapter is the application of the optimization methodology to the problem of scheduling criteria based on a multicriteria approach.

2. General overview

The spill of products requested by customers was produced in a production workshop, however due to low productivity and high production costs, production workshops are not generally suitable for high volume production [3]. There is a need for production systems capable of producing a wide variety of products which can cost as little as mass production [4].

Scheduling systems can be considered as a special case of business information systems. Planning is defined as the allocation of resources to jobs over time.

It is a decision-making process which makes it possible to optimize one or more objectives [5].

The objectives can be the minimization of the production time, the average flow time, the delay of the works, the manufacturing costs …, planning has an important role in many manufacturing and production systems.

The problems of planning seeking to optimize the time of realization of the project while respecting a certain number of constraints, are for the most part NP-difficult.

Research has mainly focused on finding optimal (or near optimal) solutions for static models with respect to various measures.

These approaches mostly have used the implicit assumption of static environments without any kind of failures. Extensive literature reviews on static deterministic scheduling can be found in [6, 7, 8, 9].

Predictive planning has now become the planning of production systems [10, 11]. For example, machine breakdowns, arrival of urgent work, change of due date, etc. [12] addressed the nature of the gap between scheduling theory and the practice of scheduling [13], in their research on intelligent time control real in manufacturing systems, said the comparison of scheduling theory and practice showed very little correspondence between the two. Cowling and Johansson [14] found a large gap between scheduling theory and practice, and stated that scheduling models and algorithms are incapable of using real-time information. Until very recently, the problem of programming in the presence of real-time events, called dynamic programming. In this chapter, we focus on a number of issues that have arisen in recent years with dynamic planning in manufacturing systems.

We are mainly concerned with the question of knowing how to manage the occurrence of events in real time during the execution of a given schedule in the workshop?

In order to close this gap between scheduling models and procedures, and their implementation in a real manufacturing setting, the former should be translated into a system supporting scheduling decisions in a company.

Among the various activities that must be present in the development of a production planning system is the design of the system architecture. Despite the importance of the architecture of production planning systems, planning research has often overlooked this topic because the related literature is scarce and does not provide researchers with a complete view of the planning system [15].

3. Multicriteria decision analysis methods

However, the MCDA approach has certain drawbacks linked to the subjective nature of the preferences granted by decision-makers. Specially, the criteria weighting profile can be considered as the uncertain part as it relies heavily on subjective measurements and has a great influence on the final result.

Linkov offers traditional risk analysis and Monte Carlo simulation taking into account the uncertainties underlying the point estimates, to which all considerations and calculations are reduced [16].

Historically Multiple Criteria Evaluation methods were developed to select the best alternative from a set of competing options [17].

3.1 Analytical hierarchy process methods

The Analytical Hierarchy Process (AHP) is a method that was invented by Professor Thomas Saaty. It provides a decision-making structure that takes into account factors weighed in as a group [18].

The analytical hierarchy process for decision making is a relative measurement theory based on pairwise comparisons. Pairwise comparison matrices are formed either by providing judgments to estimate dominance using absolute numbers from the 1 to 9 fundamental scales of the AHP, or by directly constructing pairwise dominance ratios using real measurements.

The process of synthesis of weighting and addition applied in the hierarchical structure of the AHP combines multidimensional measurement scales into a single “one-dimensional” priority scale [19].

The steps of the AHP method are as follows:

• Construction of the hierarchy, it is an abstraction of the structure of the problem used to study; the interaction with the components of the problem and their effect on the final solution, it allows the problem to be broken down into a hierarchy of interconnected data. At the top of the hierarchy, we find the objective, and at the lower level, the elements contributing to achieve this objective, the last level is that of actions (Figure 1).

• To proceed to comparisons by elemental pairs of each hierarchic relative level to an element of the hierarchic superior level. This step permits to build matrix of comparisons. Values of those matrix are obtained by the judgments transformation in numerical values according to the ladder of Saaty (Ladder of binary comparisons), everything respecting the principle of reciprocity (Table 1)

  $$\left(\mathrm{Ea},\mathrm{Eb}\right)=\frac{1}{\mathrm{Pc}\left(\mathrm{Eb},\mathrm{Ea}\right)}$$E1

• To determine the relative elemental importance calculating primary vectors to correspond of the maximal values of comparisons matrix.

• To verify the judgments coherence. One to calculate at first, the indicator coherence IC:

  $$\mathit{IC}=\frac{\mathit{\text{λmax}}-n}{n-1}$$E2

  Where: λ max is the primary maximal value running in matrix of comparisons by pairs; and n: is a large number of comparative elements. Then; the ratio of coherence (RC) defines by:

  $$\mathit{RC}=100.\frac{\mathit{IC}}{\mathit{ACI}}$$E3

  Where: ACI is the means coherence indicator of obtained generating aleatory matrix of judgment equalizes height. The means of indicator coherence is identified in the following Table 2.

  A value of RC inferior to 10% is generally acceptable; otherwise, comparisons by pairs must be examined again to reduce the incoherence.

• To settle the relative performance of each action:

  $$P_k\left(e_1^k\right)=\sum _{J=1}^{\mathit{nk}-1}{P}_{K-1}\left(e_i^{k-1}\right)P_k\frac{e_i^k}{e_i^{k-1}}$$E4

  With: $P_k\left(e_1^k\right)=1$, and: $\mathrm{nk}-1$ are a large number of elements of the hierarchic level k-1, $\mathrm{Pk}\left({\mathrm{e}}_{\mathrm{i}}^{\mathrm{k}}\right)$ is the terms priority to the element ${\mathrm{e}}^{\mathrm{i}}$ to the hierarchic level k [20].

Figure 1.

Construction of the hierarchy.

Importance grade	Define
1	Importance equalizes of both elements.
3	Importance weak person of a relative element to another.
5	Importance strong or determinant of a relative element to other.
7	Importance attested of a relative element to another.
9	Importance absolved of a relative element to another
2,4,6,8	Intermediate values with two values neighbor.

Table 1.

Saaty scales.

Matrix dimension	Aleatory coherence ACI
1	0.00
2	0.00
3	0.58
4	0.90
5	1.12
6	1.24
7	1.32
8	1.41
9	1.45
10	1.49

Table 2.

Means coherence indicator.

3.2 The lexicographic goal programming approach (LGP)

The LGP is an extension of linear programming (LP), was originally introduced by [21] and further presented by [22], and others. This technique was developed to handle multi-criteria situations within the general framework of LP. In the variant of the lexicographic Goal Programming, the objectives are ranked in order of priority, as the relative importance given to them by the decision maker. The mathematical formulation corresponding to this variant consists of a vector the deviations ordered on different objectives, which implies a minimization in the order of the different priority levels q [23]. The mathematical program is written as follows:

$$\mathit{lex}.\underset{\underset{¯}{x}\in A}{\overset{}{Min.\mathrm{L}=}}\left[l1\left({\delta }^{-},{\delta }^{+}\right),\dots ,\mathit{lq}\left({\delta }^{-},{\delta }^{+}\right)\right]$$E5

Subject to:

$$\begin{array}{c}{\mathrm{a}}_{1\mathrm{j}}{\mathrm{x}}_{\mathrm{j}}+{{\mathrm{\delta }}^{-}}_1+{{\mathrm{\delta }}^{+}}_1\le {\mathrm{g}}_1;\\ {\mathrm{a}}_{2\mathrm{j}}{\mathrm{x}}_{\mathrm{j}}+{{\mathrm{\delta }}^{-}}_2+{{\mathrm{\delta }}^{+}}_2\le {\mathrm{g}}_2;\\ \dots \\ {\mathrm{a}}_{\mathrm{nj}}{\mathrm{x}}_{\mathrm{j}}+{{\mathrm{\delta }}^{-}}_{\mathrm{n}}+{{\mathrm{\delta }}^{+}}_{\mathrm{n}\le }{\mathrm{g}}_{\mathrm{n}};\end{array}$$E6

$$\begin{array}{c}{{\mathrm{\delta }}^{-}}_{\mathrm{i}},{{\mathrm{\delta }}^{+}}_{\mathrm{i}}\ge 0\text{pour}\left(\mathrm{i}=1,2,\dots ,\mathrm{n}\right)\\ {\mathrm{x}}_{\mathrm{j}}\ge 0\text{pour}\left(\mathrm{j}=1,2,\dots ,\mathrm{n}\right)\end{array}$$E7

4. Application: process of cutting the electric cables

It is difficult to imagine modern cars without electronics. Computer board, control lamp, reversing sensors… were designed to increase the comfort level and safety of the motorist. Electrical motor, the intensities being involved cover a range of about 0.5 A, a dashboard light bulb and up to several hundred amperes for a starter. But, any short circuit involves very high currents and can easily set fire to the vehicle and cause severe burns on contact elements short circuit.

In this paper, we propose a methodology for multicriteria optimization criteria considered essential to establish the correct ordering of the machines to avoid the loss of time and minimize the rate of waste and waste (Figure 2).

Figure 2.

Cut marking process flow chart setting.

4.1 The analytical hierarchy process to ranking criteria scheduling

In the process of cutting the electric cables, we have identified six criteria:

• L1: qualification of workers,

• L2: safety culture,

• L3: equipment performance,

• L4: scheduling equipment,

• L5: production technology,

• L6: cost of upgrading waste.

Step 1: structure combination of scheduling criteria (Figures 3 and 4)

Figure 3.

Hierarchical structure of scheduling criteria.

Figure 4.

Pairwise comparison of criteria.

Step 2: Pairwise comparisons of the elements of each hierarchical level with respect to an element of higher level

The pairwise comparison of criteria by the matrix above has identified the choice of the decision maker on the degree of importance of each criterion. For the decision maker, the most important criterion is “cost of upgrading waste”, and the test that has no great fatality of the decision of the prioritization of scheduling criteria machines is “production technology”.

Step 3: Determination of the relative importance of elements by calculating the eigenvectors corresponding to the maximum eigenvalue of comparison matrix (Figures 5–10):

Figure 5.

Eigenvector of the criterion L1. The alternative is the most important criterion L1” qualification of workers”, is C2 “Awareness use of safety rules” how long has the value of the eigenvector is greater.

Figure 6.

Eigenvector of the criterion L2. The alternative is the most important criterion L2” qualification of workers”, is then C2 “Awareness use of safety rules” how long has the value of the eigenvector is greater.

Figure 7.

Eigenvector of the criterion L3. For the eigenvector criterion L3 “equipment performance” alternative C4 “location of carts and reels”, is the largest, and the criterion C2 is also essential according to the criterion L2.

Figure 8.

Eigenvector of the criterion L4. For the eigenvector criterion L4 “scheduling equipment”, alternative C3’number of maintenance” is the essential.

Figure 9.

Eigenvector of the criterion L5. The alternative of C4“ location of carts and reels”, is considered essential and priority according to the criterion L5.

Figure 10.

Eigenvector of the criterion L6. For the eigenvector criterion L6“ cost of upgrading waste “, then, the alternative of C4“ location of carts and reels”, is considered essential and priority.

Step 4: Check the consistency of judgments. All judgments are consistent (Table 3)

Eigenvector	Ratio of coherence	Décision
Eigenvector L1	0.08	Consistency accepted
Eigenvector L2	0.03	Consistency accepted
Eigenvector L3	0.08	Consistency accepted
Eigenvector L4	0.02	Consistency accepted
Eigenvector L5	0.05	Consistency accepted
Eigenvector L6	0.06	Consistency accepted

Table 3.

Judgment consistency ratios.

Step 5: Calculation of performance

Prioritization method AHP has established the classification scheduling criteria as follows (Figure 11).

Figure 11.

Prioritization of scheduling criteria ranking.

The decision maker considers that the scheduling criteria L6 is a priority to set up an optimal schedule.

4.2 Scheduling optimization criteria according to the prioritization by the method of lexicographic goal programming

In this section we will make multicriteria optimization of six criteria identifies previously, in order of priority Realize by AHP. The problem is to find an optimal solution of scheduling in a cutting process by acting on all the criteria considered indispensable. We propose:

a1: cost per worker qualification;

a2: cost of training per worker safety culture;

a3: maintenance cost per machine;

a4: cost of extending the area of machine scheduling;

a5: cost of purchasing software programmable machine;

a6: cost of recycling machine.

Then, the goal to which the decision maker for each criterion to minimize the deviation are as follows (Table 4):

Criterion	Permissible limit
L1*: qualification of workers	1600£
L2*: safety culture	2000£
L3*: equipment performance	5000£
L4*: scheduling equipment	1600£
L5*: production technology	35000£
L6*: cost of upgrading waste	500£

Table 4.

Permissible limit of criterion.

In order of priority for the AHP method the objective functions of each criterion is as follows:

The objective function L6 is:

Max L = δ-6

Subject to:

800x1+ δ-1+ δ + 1 ≤ 1600;

400x2+ δ-2+ δ + 2 ≤ 2000;

50x3+ δ-3+ δ + 3 ≤ 5000;

200x3+ δ-4+ δ + 4 ≤ 1600;

50x4+ δ-5+ δ + 5 ≤ 35000;

20x5+ δ-6+ δ + 6 ≤ 500;

δ-i, δ + i ≥ 0 pour (i = 1,2,…,6)

xj ≥ 0 pour (j = 1,2,…,6)

The objective function L1 is:

Max L = δ-1

Subject to

800x1+ δ-1+ δ + 1 ≤ 1600;

400x2+ δ-2+ δ + 2 ≤ 2000;

50x3+ δ-3+ δ + 3 ≤ 5000;

200x3+ δ-4+ δ + 4 ≤ 1600;

50x4+ δ-5+ δ + 5 ≤ 35000;

20x5+ δ-6+ δ + 6 ≤ 500;

δ-i, δ + i ≥ 0 pour (i = 1,2,…,6)

xj ≥ 0 pour (j = 1,2,…,6)

The objective function L3 is:

Max L = δ-3

Subject to

800x1+ δ-1+ δ + 1 ≤ 1600;

400x2+ δ-2+ δ + 2 ≤ 2000;

50x3+ δ-3+ δ + 3 ≤ 5000;

200x3+ δ-4+ δ + 4 ≤ 1600;

50x4+ δ-5+ δ + 5 ≤ 35000;

20x5+ δ-6+ δ + 6 ≤ 500;

δ-i, δ + i ≥ 0 pour (i = 1,2,…,6)

xj ≥ 0 pour (j = 1,2,…,6)

The objective function L4 is:

Max L = δ-4

Subject to

800x1+ δ-1+ δ + 1 ≤ 1600;

400x2+ δ-2+ δ + 2 ≤ 2000;

50x3+ δ-3+ δ + 3 ≤ 5000;

200x3+ δ-4+ δ + 4 ≤ 1600;

50x4+ δ-5+ δ + 5 ≤ 35000;

20x5+ δ-6+ δ + 6 ≤ 500;

δ-i, δ + i ≥ 0 pour (i = 1,2,…,6)

xj ≥ 0 pour (j = 1,2,…,6)

The objective function L2 is:

Max L = δ-2

Subject to

800x1+ δ-1+ δ + 1 ≤ 1600;

400x2+ δ-2+ δ + 2 ≤ 2000;

50x3+ δ-3+ δ + 3 ≤ 5000;

200x3+ δ-4+ δ + 4 ≤ 1600;

50x4+ δ-5+ δ + 5 ≤ 35000;

20x5+ δ-6+ δ + 6 ≤ 500;

δ-i, δ + i ≥ 0 pour (i = 1,2,…,6)

xj ≥ 0 pour (j = 1,2,…,6)

The objective function L5 is:

Max L = δ-5

Subject to

800x1+ δ-1+ δ + 1 ≤ 1600;

400x2+ δ-2+ δ + 2 ≤ 2000;

50x3+ δ-3+ δ + 3 ≤ 5000

200x3+ δ-4+ δ + 4 ≤ 1600;

50x4+ δ-5+ δ + 5 ≤ 35000;

20x5+ δ-6+ δ + 6 ≤ 500;

δ-i, δ + i ≥ 0 pour (i = 1,2,…,6)

xj ≥ 0 pour (j = 1,2,…,6)

By using the software LINDO, the ideal solution obtained for optimize the scheduling problem in a cutting process is (Table 5).

Criterion	Result
L6: cost of upgrading waste	1600£
L1: qualification of workers	2000£
L3: equipment performance	5000£
L4: scheduling equipment	1600£
L2: safety culture	35000£
L5: production technology	500£
Z*	45700£

Table 5.

Optimal solution.

The solution is satisfactory with the support of the decision maker’s preferences. It is obvious that the implementation of the prioritization criterion that the lexicographic goal programming, the solution is much improved. The level of satisfaction achieved for the six objectives is 100%. Achieved this level of satisfaction implies that all specifications are met.

5. Conclusions

In this paper, we presented a multicriteria methodology to optimize the problem of scheduling in cutting process of electrical cables.

Then, this multicriteria approach has debited by the classification criteria with the AHP methods for identify the prioritization, and in the second parts we have optimized this criteria with the lexicographic goal programming. This methodology has given optimal results as long as it is based on the preferences and the intervention of any decision-maker during the optimization process.