Simulated imperialist competitive algorithm in two-stage assembly flow shop with machine breakdowns and preventive maintenance

Abstract

This article deals with the two-stage assembly flow shop problem considering preventive maintenance activities and machine breakdowns. The objective is to minimize the makespan. This problem is proven to be NP-hard; thus, we proposed two meta-heuristic algorithms, namely, imperialist competitive algorithm and genetic algorithm, to obtain solutions of the problem. This article describes an approach incorporating simulation with imperialist competitive algorithm for the scheduling purpose having machine breakdowns and preventive maintenance activities. The results obtained are analyzed using Taguchi experimental design, and the parameters of proposed algorithms are calibrated by artificial neural network. The computational results demonstrate that imperialist competitive algorithm is statistically better than genetic algorithm in quality of solution and reaches to better solutions at the same computational time.

Keywords

Two-stage assembly flow shop production and maintenance imperialist competitive algorithm Taguchi method artificial neural network

Introduction

International competition and the ability to respond to the changing demand in the markets are some of the key attributes in designing effective production systems. Two-stage assembly flow shop is a combinational production system, where different parts are manufactured on parallel machine independently. This system can be used as a method to produce a variety of goods by assembling and combining different set of parts. From production point of view, the two-stage assembly flow shop problem consists of two stages, where m machines are at the first stage and only one machine at the second stage. There are n jobs, and each job is composed of m + 1 operations; m operations are performed by m machines in parallel at the first stage, and the last operation is done by the assembly machine in the second stage. The two-stage assembly flow shop has several applications in real-life problems such as computer manufacturing,¹ fire engine,² production and queries scheduling on distributed database systems,³ as shown in Figure 1. The problem under study is common in an electronic industry like TV fabrication or air conditioner manufacturers.

Figure 1.

A two-stage assembly (distributed database) structure.³

Manufacturing environments are dynamic in nature, and these environments are subject to various disruptions, referred to as real-time events, which can change system conditions and affect its performance. Real-time events have been classified into two categories:^4–8

Resource related: machine breakdown, operator illness, unavailability or tool failures and delay in the arrival or shortage of material.

Job related: rush job, job cancelation, due date changes, early or late arrival of jobs, change in job priority and changes in job processing time.

In the face of the clear relationship between the maintenance planning and production scheduling in manufacturing systems, most production scheduling literature assumed that the machines are available during the planning horizon and employed separately. But this assumption is not reasonable since machines are not available for processing while machine breakdowns occur or preventive maintenance (PM) activities are done. PM activities carry out the operations on machines and tools before the breakdown takes place. Therefore, they prevent failures before breakdowns occur. In other words, system stays in good condition by PM activity.

This research is concentrated on machine breakdown and PM as the real-time event. For handling the structural and functional complexities of the problem, an approach incorporating simulation into imperialist competitive algorithm (ICA) is considered to solve the problem. Due to stochastic properties that exist in this problem, a scheduling method with predefined parameters cannot be suitable because it reduces the performance of the methods. Recently, artificial neural network (ANN) is employed as an efficient approach in engineering issues. ANNs can be used to predict suitable parameters for a scheduling method in real-time events by a pattern taken from a learning sample. To enhance the efficiency and effectiveness of proposed algorithms, their parameters are updated by the ANN.

The remainder of this study is organized as follows: section “Literature review” presents a literature review of two-stage assembly flow shop scheduling and scheduling with maintenance and breakdown constraints. Section “Problem description” describes the problem. The proposed ICA is given in section “The proposed algorithms.” ANN which tunes parameters of algorithms is described in section “ANN.” Section “Experimental design” presents the experimental design analyzing parameters of the problem. Finally, section “Conclusion and future works” presents the conclusions and directions for future work.

Literature review

The two-stage assembly flow shop problem with two machines was first introduced by Lee et al.⁹ Potts et al.¹ proved that two-stage assembly flow shop problem is NP-hard, and a solution with two machines was proposed by a branch-and-bound algorithm and then three heuristics have been presented. Different criteria have been considered in this problem. For instance, Lee et al.,⁹ Potts et al.,¹ Haouari and Daouas,¹⁰ Sun et al.¹¹ and Allahverdi and Al-Anzi³ considered the problem with makespan criterion. Tozkapan et al.¹² defined the problem with the total weighted flow time objectives. On one hand, Allahverdi and Al-Anzi¹³ reported this problem with total completion time criterion, and, on the other hand, Al-Anzi and Allahverdi¹⁴ addressed the problem with maximum lateness criterion. Shokrollahpour et al.,¹⁵ Torabzadeh and Zandieh,¹⁶ and Allahverdi and Al-Anzi¹⁸ defined this problem with bi-criteria of makespan and mean completion time. Al-Anzi and Allahverdi¹⁴ considered this problem with total completion time and solved it by three meta-heuristics. The computational results reveal that hybrid tabu search (TS) was better than two other meta-heuristics. Allahverdi and Al-Anzi¹³ presented the same problem. They applied three meta-heuristics, namely, simulated annealing (SA), self-adaptive differential evolutionary algorithm (SDE) and ant colony optimization (ACO), among which SA outperforms ACO and SDE. Allahverdi and Al-Anzi¹⁸ considered the two-stage assembly flow shop scheduling problem with setup times for minimizing the total completion time; they presented hybrid tabu search (Ntabu), SDE and a new version of SDE (NSDE). Computational results demonstrate that NSDE was better than other algorithms. Hwang and Lin¹⁹ addressed a two-stage assembly flow shop batch scheduling problem with a fixed job sequence. They considered four regular performance metrics with the goal of obtaining an optimal batching decision for the predetermined job sequence at stage 2. Mozdgir et al.²⁰ presented the two-stage assembly flow shop problem with the objective of minimizing the weighted sum of makespan and mean completion time; they considered sequence-dependent setup times at the first stage and multiple non-identical assembly machines in the second stage. They applied a variable neighborhood search (VNS) algorithm and developed a novel heuristic and compared its solutions with solutions obtained by general algebraic modeling system software (GAMS). Percentage errors and computational time in experiments showed that the hybrid VNS heuristic performs much better than GAMS. Seidgar et al.²¹ considered the two-stage assembly flow shop problem and proposed a hybrid ANN and ICAs for solving the generated problems. They compared proposed algorithm with the cloud theory based simulated annealing (CSA) introduced by Torabzadeh and Zandieh and showed that their obtained solutions are better and more efficient. Xiong and Xing²² focused on the distributed two-stage assembly flow shop scheduling problem for minimizing the weighted sum of makespan and mean completion time. They presented a mathematical model and solved the small-sized instances of the proposed problem. Because of the NP-hardness of the problem, they also proposed a VNS algorithm and a hybrid genetic algorithm (GA) combined with reduced variable neighborhood search (GA-RVNS) to solve the problem. Computational experiments have been conducted for comparing the performances of the model and proposed algorithms. For a set of small-sized instances, both the model and the proposed algorithms were effective. The proposed algorithms were further evaluated on a set of large-sized instances. The results statistically illustrated that both GA-RVNS and VNS obtain much better performances than the GA without RVNS-based local search step (GA-NOV). Hong-Sen Yan et al.²³ investigated two-stage assembly flow shop problem (TASFP) to minimize the weighted sum of makespan and earliness and tardiness. They used a hybrid neighborhood search electromagnetism-like mechanism (VNS-EM) for solving the problem. Simulation results illustrated that the proposed hybrid VNS-EM algorithm outperforms the EM and VNS algorithms in both average value and standard deviation.

Recently, extensive studies are done to solve production planning and PM scheduling problems. Lee,^17,24 Blazewicz et al.²⁵ and Kubiak et al.²⁶ surveyed production scheduling with PM activities being presented based on the “machine availability.” In these studies, time interval of PM activities was predefined and fixed. Sherif and Smith²⁷ and Wang²⁸ surveyed the comprehensive study on PM models. Kaabi et al.²⁹ studied single-machine and flow shop problem. In their research periods, maintenance activities were fulfilled during pre-known interval. Gharbi and Kenne³⁰ considered the production and PM activities control problem for a manufacturing system with multi-machine. Ruiz et al.³¹ considered different PM policies on machines regarding flow shop scheduling, while the aim was maximizing the availability or minimizing the level of reliability during the production horizon. Safari and Sadjadi³² explained flow shop scheduling problem subject to condition-based maintenance and unpredicted breakdown to minimize expected makespan with non-resumable jobs. They proposed a hybrid algorithm based on GA and simulated annealing and used the Taguchi experimental design method to set the parameters.

Berrichi et al.³³ proposed a mathematical model for parallel machine problem to joint production and maintenance scheduling. In their work, minimization of the makespan and system unavailability were considered, and two meta-heuristics were applied to find approximation of the Pareto-optimal front of the problem. Moradi et al.³⁴ studied flexible job shop problem where PM and the reliability concept were considered. Mokhtari et al.³⁵ jointed production and maintenance scheduling with multiple PM services, and the reliability approach was employed to model the maintenance aspects. Majazi Dalfard and Mohammadi³⁶ developed a new mathematical model for a multi-objective flexible job shop scheduling problem with parallel machines. They considered maintenance constraints and maintenance cost for the problem and applied two meta-heuristic algorithms, a hybrid GA and a simulated annealing algorithm. Sarker et al.³⁷ considered the job scheduling problem (JSP) and explained the effect of machine maintenance, whether preventive or breakdown. They proposed a hybrid evolutionary algorithm (HEA) for solving the problem and compared it with the existing algorithms. Benmansour et al.³⁸ presented a single-machine problem with periodic PM with the goal of minimizing the weighted sum of maximum earliness and maximum tardiness costs.

By reviewing the literature, no work focusing on assembly flow shop problem with machine breakdown was found, and thus, we will review the literature on scheduling under maintenance and random breakdown constraints. Yamamoto and Nof⁶⁰ studied job shop scheduling problem with random machine breakdowns by considering event-driven rescheduling policy. Allahverdi² considered the problem of scheduling in a two-machine proportionate flow shop, where the objective function is to maximize the lateness and machine random breakdowns are allowed. Allaoui and Artiba⁴⁰ employed simulated annealing for scheduling a hybrid flow shop with maintenance; they noted that amount of breakdown can be affected by heuristics. Gholami et al.⁸ explored the hybrid flow shop scheduling problems with sequence-dependent setup times and breakdown constraints for machines. A GA was used to find production sequence and simulation to obtain expected makespan. Zandieh and Gholami⁴¹ presented an immune algorithm for scheduling a hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. Jabbarizadeh et al.⁴² considered the hybrid flow shop scheduling problems with sequence-dependent setup times and maintenance activities for machines. Ghezail et al.⁴³ proposed a qualitative graphical approach to deal with disruptions in the flow shop problem. Their graphical approach showed the consequences of random failures to the decision maker, so they can choose the best sequence. Lei⁴⁴ studied stochastic job shop scheduling problem with random breakdowns for minimizing the stochastic makespan. He proposed an efficient GA and considered exponential processing time and non-resumable jobs. Naderi et al.⁴⁵ investigated scheduling flexible flow shops subject to periodic PM on machines. The objective was to minimize makespan. Two meta-heuristics, including GA and artificial immune system, and some constructive heuristics were developed to tackle the problem. The performance of the algorithms was evaluated by comparing their solutions. The results of the computational experiments indicated that the artificial immune system outperforms the other methods. Al-Hinai and ElMekkawy⁴⁶ studied the flexible job shop problem (FJSP) with random machine breakdowns using a two-stage hybrid GA to find robust and stable solutions. They used a bi-objective approach, and three stability measures were suggested. Dong and Jang⁴⁷ considered production scheduling at a job shop problem under machine breakdowns. They developed two novel heuristic rescheduling procedures, AWI-J and AWI-O, for minimizing mean tardiness and compared their performances with those of the affected operations rescheduling (AOR) procedure. Li et al.⁴⁸ presented a novel discrete artificial bee colony (DABC) algorithm for solving the multi-objective flexible job shop scheduling problem with maintenance activities. Performance criteria considered are the maximum completion time so-called makespan, the total workload of machines and the workload of the critical machine. Unlike the original ABC algorithm, the proposed DABC algorithm presented a unique solution representation where a food source was represented by two discrete vectors and TS was applied to each food sourceto generate neighboring food sources for the employed bees, onlooker bees and scout bees. The proposed DABC algorithm is tested on a set of well-known benchmark instances from the existing literature. Through a detailed analysis of experimental results, the highly effective and efficient performance of the proposed DABC algorithm was shown against the best performing algorithms from the literature. Moghadam⁴⁹ presented a new multi-objective nonlinear mixed-integer optimization model to determine Pareto-optimal PM and replacement schedules for a repairable multi-workstation manufacturing system with increasing rate of occurrence of failure. The operational planning horizon was segmented into discrete and equally sized periods, and in each period, three possible maintenance actions (repair, replacement or do nothing) have been considered for each workstation. The optimal maintenance decisions for each workstation in each period were investigated such that the objectives and the requirements of the system can be achieved. The multi-objective model was solved using a hybrid Monte Carlo simulation and goal programming procedure to obtain set of non-dominated schedules. The effectiveness and feasibility of the proposed solution methodology were demonstrated in a manufacturing setting, and the computational performance of method in obtaining Pareto-optimal solutions was evaluated. Such a modeling approach and the proposed solution algorithm could be useful for maintenance planners and engineers tasked with the problem of developing optimal maintenance plans for complex productions systems.

Problem description

A set of n multiple-operation jobs is simultaneously available at time 0, and preemption is not allowed. Each job requires m + 1 operations, and m operations are done at the first stage by m parallel machines and the last operation performed at the assembly stage. The operation of each job in assembly stage starts only after all the operations of job in the first stage. Each job is completed after finishing all of its operations in both stages. In this research, the sequence of jobs on all of the machines in both stages is the same.

In this problem, some assumptions are presumed, which are listed below:

All jobs are available for processing at time zero.

A job is composed of m + 1operations.

There are no preference constraints among the jobs.

Jobs are always processed without error.

Processing times of jobs are known.

Setup times among operations of jobs are negligible or included in the processing times (sequence-independent setup times).

Each job is processed on one machine at a time.

Infinite buffers exist between two stages; in other words, machines cannot be blocked.

Preemption is not allowed for jobs.

Machines can only process one job at the same time.

Machines are not available at all times due to breakdowns and PM. The breakdown occurs during time when machines are processing the operations.

The processing of job continues after the repairing of machine without change in time resumption.

Mean time between failures (MTBF) that show number of breakdowns follows the exponential distribution.

Mean time to repair (MTTR) follows the exponential distribution.

All machines have the same MTBF and MTTR values.

Traveling time between two stages is negligible.

When production planning joints to maintenance, we can consider different policies presented by researchers such as Cassady and Kutanoglu,⁵⁰ Sherif and Smith²⁷ and Ruiz et al.³¹ Three possible PM policies are explained as follows:

Policy 1. In this policy, PM activities are periodically carried out at fixed predefined time intervals. This policy is widely applied in industry.³¹

Policy 2. The objective of this policy is to maximize the availability of system by creating a balance between the effects of a failure and PM. In this policy, we assume that the time to failure follows a Weibull probability distribution $(T \approx W [θ, β])$ with $β > 1 \cdot t_{r}$ being the number of time units the repair takes and $t_{p}$ is the number of time units of the PM. The optimal maintenance interval $(T_{PMop})$ can be computed by the following formula³¹

T_{P M o p} = θ \cdot {[\frac{t_{p}}{t_{r} (β - 1)}]}^{\frac{1}{β}}

(1)

Policy 3. This policy makes a PM after a time $T_{PM}$ so as to satisfy a minimum reliability of the system from time t = 0. The PM activities should be carried out at regular intervals $0, 1 T_{PM}, 2 T_{PM}, 3 T_{PM}, \dots, n T_{PM}$ .The time interval between two PM activities $(T_{PM})$ is calculated as follows³¹

T_{PM} = {[- θ^{β} \cdot \frac{\ln R_{0} (t)}{t}]}^{\frac{1}{(β - 1)}}

(2)

This article manipulates a strategy to insert PM activities, and this strategy was called rational strategy by Berrichi et al.³³ In this strategy, it is possible to delay or to advance a maintenance activity. To our knowledge, there is no study related to the integrated approach in the two-stage assembly flow shop scheduling problem with PM activities and machine breakdowns as unavailability constraints. In this paper, Policy 1 is used and adapted with rational strategy that introduced by Berrichi et al.³³

Let $B_{j}$ and $C_{j}$ be the starting and completion time of job j, respectively. $T_{e}$ is the expected time to perform the PM activity. If $T_{e} ⩽ (B_{j} + C_{j}) / 2$ , then the PM activity is done to the date $B_{j}$ ; otherwise, it is postponed to $C_{j}$ .^33–35 The chosen strategy is shown in the following example.

Consider a system works based on policy 2 and rational strategy. This system consists of two stages, where two machines are in the first stage and only one machine is in the second stage. Suppose that there are three jobs which must be processed on three machines, and PM activities are carried out every 12 time units with 2 time units for duration of PM activities. Also, the processing times are shown in Table 1. The Gantt chart of two-stage assembly flow shop scheduling is shown in Figure 2, and Gantt chart for the integrated production and maintenance scheduling is shown in Figure 3.

Table 1.

Processing time of operations of jobs on machines.

Jobs	Job 1	Job 2	Job 3
Processing times of machine 1 ( $P_{O_{1 j}}$ )	8	14	10
Processing times of machine 2 ( $P_{O_{2 j}}$ )	9	8	14
Processing times of assembly machine ( $P_{O_{3 j}}$ )	8	7	12

$O_{kj} : operation kth of job$ .

Figure 2.

Gantt chart of assembly flow shop without maintenance activities.

Figure 3.

Gantt chart of the integrated production and maintenance activities.

Consider the instance illustrated in Table 1 and Figure 2. Figure 3 indicates Gantt chart of the integrated production and maintenance scheduling. As shown in Figure 3, PM activities are done at times 14 and 34 on machine 1, at times 17 and 33 on machine 2 and at time 32 on assembly machine.

The proposed algorithms

Due to breakdowns, time is not specific and occurs randomly on machines, and we used a simulator for simulating these statuses. The simulator allows us to disrupt operation of jobs when breakdown occurred on machines. We indicate how to handle the two-stage assembly flow shop scheduling with machine breakdowns to optimize the objective based on expected makespan using simulation incorporated into ICA.

For incorporating simulation into proposed meta-heuristics, it is necessary to note the following:

The time when breakdowns occur on machine m at the first or second stage must be calculated.

After each breakdown, repairing time must be calculated.

The time that is left for the last breakdown on the machine must be saved.

Repairing time is added to the completion time of operation of jobs at each stage.

Rational strategy is applied to consider the PM policy. $T_{e}$ is the expected time to perform the PM activity.

The objective value for algorithms is calculated (the expected makespan).

Future event list (FEL) indicates the failure time of a machine after it starts processing. It indicates the interval between every two events of breakdown for each machine; FEL follows exponential distribution.

After the machine repairs, the life time (life) will set to 0 because the exponential distribution has memoryless property.

Simulator algorithm

The basic notion of the simulator algorithm is derived from SPTCH and Johnson’s rule-based heuristic developed by Kurz and Askin.⁵¹ The simulator algorithm used in the proposed algorithms has the following steps:

1. Initialize FEL by random number that follows exponential distribution in which the mean value is MTBF for all of the machines in the two stages

FEL [machine] [stage] = \exp (MTBF)

2. In the first stage

2.1. Decode the country

2.2. For i = 1:n

2.3. For k = 1:m

2.4. Run breakdown algorithm

End for (k)

End for (i)

3. In the second stage

3.1. Update the ready times in second stage to completion at the first stage

3.2. For k = 1:m

3.3. Run breakdown algorithm

End for (k).

Breakdown algorithm

The steps of breakdown algorithm applied in simulator algorithm are as follows:

1. Add the processing time of operation of job on that machine at that stage to the life variable

Life [machine] [stage] = life [machine] [stage] + processing time [i] [machine] [stage]

2. If (life[machine][stage]>FEL[machine][stage]), do step 3 otherwise do step 4

End if

3. In this time breakdown occurred in machine, and we must do the following steps

3.1. Generate a random number called repair time; repair time follows exponential distribution, where mean value is MTTR

3.2. Repair time is added to the operation of job’s completion time on that machine at that stage

Completion [i] [machine] [stage] = Completion [i] [machine] [stage] + repair time

3.3. Apply the rational strategy to insert PM activity

If ( $T_{e} ⩽ (B_{j} + C_{j}) / 2)$ , then the PM activity is done to the date $B_{j}$

Else, the PM activity is postponed to the date $C_{j}$

End if

3.4. Update the time of next breakdowns for machines

FEL [machine] [stage] = \exp (MTBF)

3.5. Assign zero to the life variable for machine

Life [machine] [stage] = 0

4. Run the simulator algorithm.

Proposed ICA

The ICA is an evolutionary algorithm presented by Atashpaz-Gargari et al.^52,53 ICA is based on the concept of imperialist competition in the real world. ICA is a population-based algorithm; in other words, it starts its work by an initial population of solution which is named countries. Countries are solutions in the solution space, and they can be divided into two sections: imperialism and imperialistic. Each imperialism based on its power controlled and moved a number of imperialistic in its direction. The assimilation and competition policy are the basic core of this algorithm. Each solution in this algorithm is shown as a country. The country in ICA is similar to chromosome in GA. The countries have several attributes including culture, language, religion, economic policy and so on and are shown by vector F

F = [f 1, f 2, \dots, f_{N}]

in which $f_{i}$ indicates ith attribute of a country.

Countries based on its cost may be classified into imperialist and may create their own empire or classified into imperialistic and join an empire. In these competitions that occur in the real word, the weak empires lose their countries and powers. The imperialistic competition will increase in the power of great empires and decrease in the power of weaker ones. Finally, they are destroyed and the powerful ones expand to colonies which are grabbed from the weak empires. In each iteration of ICA, imperialistic moves in the direction to their imperialist, and if an imperialistic was better than its imperialist, then imperialistic is swapped with the imperialist. These processes iterate to meet the stop criteria.

In this problem, a country is a 1 × n array. The array of country represents a sequence of jobs. Initial population is produced as follows: one initial sequence is obtained by ordering all of the jobs into increasing order of $p_{[i]}$ . A good solution will be obtained by ordering jobs based on the shortest processing time when processing times on the assembly machine are larger than those of the first-stage machines. Generally, for the mean completion time criterion, the SPTCH rule performs well. By considering the first stage and ordering the jobs in increasing order of $\max {t_{[i, k], k = 1, 2, \dots, m}}$ , the second initial solution is obtained. Ordering the jobs in increasing order of $\max {t_{[i, k], k = 1, 2, \dots, m}} + p_{[i]}$ will yield a third sequence in which both stages are considered, and the others were generated randomly.¹⁵ After producing initial population, at the first step each country must be specified to either imperialist or colony. Next, the fitness value of countries will be calculated, and those with lowest cost are determined as imperialists and other countries will be considered as colonies.⁵² Then, the numbers of each imperialist’s colonies are calculated by equations (3)–(6)

c_{i} = Cost (country)

(3)

C_{n} = ma x_{i} {c_{i}} - c_{n}

(4)

P_{n} = | \frac{C_{n}}{\sum^{C_{i}}} |

(5)

Number of clonie s_{n} = round (P_{n} \cdot N_{col})

(6)

where $c_{n}$ and $C_{n}$ are the cost of nth imperialist and its normalized cost, respectively. $P_{n}$ is the imperialist’s power, and imperialists with lower cost have higher power so that it increases their chance to get more colonies (Figure 4).

Figure 4.

Generation of initial empires.¹⁵

After specifying imperialists and their colonies, ICA devices assimilation policy and revolution operators to search for better countries. Assimilation policy is performed on all colonies to form new ones. In this policy, each imperialist absorbs colonies by making changes in their attributes such as social, cultural, regional and so on. Next, the cost of new colonies that are absorbed to the current imperialist must be recalculated (Figure 5).

Figure 5.

Movement of colonies toward their relevant imperialist.⁵²

The steps of assimilation operator are explained as follows:

Select one cell randomly in imperialist array (cell 4, number 6).

Find that number in the colony’s array and shift that until it comes to the same position as in imperialist array (cell 2, number 6).

Put the right-hand side number in the imperialist’s array (it is 5 in this representation) at the right-hand side of the shifted cell in the colony’s array (swap numbers 5 and 4). This operator is shown in Figures 6 –8.

Figure 6.

Assimilation operator.

Figure 7.

Exchanging the positions of a colony and the imperialist.¹⁵

Figure 8.

The entire empire after position exchange.¹⁵

The second operator is revolution that creates diversification in countries. This operator randomly selects two attributes in a country and exchanges their values (Figure 9).

Figure 9.

Revolution: a sudden change in socio-political characteristics of a country.⁵³

After assimilation and revolution operators, the power of each emperor is calculated by equations (7)–(9)

T \cdot C_{n} = Cost (Imperialis t_{n}) + ζ \cdot mean {Cost (Colonies of Empir e_{n})}

(7)

N \cdot T \cdot C_{n} = ma x_{i} {T \cdot C_{i}} - T \cdot C_{n}

(8)

P_{Pn} = | \frac{N \cdot T \cdot C_{n}}{\sum_{i = 1}^{Nimp} N \cdot T \cdot C_{i}} |

(9)

where $T \cdot C_{n}$ is equivalent to the total cost of nth empire and $ζ$ is a positive number which is considered to be lower than 1, $N \cdot T \cdot C_{n}$ is the power of nth empire and $P_{Pn}$ is the possession possibility of each emperor. The emperor with the lowest cost will be considered as the weakest emperor. Then, the other emperors compete with each other to take possession of the weakest colonies of the weakest emperor. ICA uses a selection process to choose an emperor that will pick up the mentioned colonies. The vector R created uniformly distributed random number as follows

R = [r_{1}, r_{2}, \dots, r_{Nimp}]

From vector D in equation (6), the emperor with highest value will be selected, and the weakest colony of the weakest emperor will be assigned to it

D = P - R = [D_{1}, D_{2}, \dots, D_{Nimp}] = [p_{P 1} - r_{1}, p_{P 2} - r_{2}, \dots, p_{p_{Nimp}} - r_{p_{Nimp}}]

(10)

The stopping criterion of the algorithm is the remaining of one emperor (Figure 10).^15,52,53

Figure 10.

Imperialistic competition.¹⁵

GA

GA is an evolutionary method which can be used to solve optimization problems. This method is based upon Darwin’s theory about evolution, and it was first used by John Holland. During the last decades, GA has become one of the most well-known meta-heuristics and is widely used in many combinatorial optimization problems including machine scheduling. GA starts with a population which consists of population size (PS) of individuals, and it is suitable for encoding or representation of the solution to a problem. Each individual has a fitness value that measures the quality of the solution which is associated with the chromosome. A simple GA has most generation’s numbers in order to evolve the current population to the new one for each iteration. There are basic operations which are included: Selection, Crossover, Mutation and Elitisms.

By selection, parents are selected from the population. In a crossover operation, the parents are combined by crossover operator to produce one or more offspring based on crossover probability (P_c); the mutation operator alters offspring according to the mutation rules to offset convergence effect and guarantees the population diversity based on mutation probability (P_m); and sometimes in a GA, a number of fitter individuals are copied directly from current to the new population which is called elitisms. A quite large number of articles investigated GAs; some studies describe GA approach and its applications in detail.^54–56 One of the most important advantages of GA is considering a large number of sets of solutions in parallel.⁵⁷ We briefly describe crossover and mutation operator for the proposed problem.

Crossover operator

Crossover has the main rule in the processing of GA. It started its work with chromosomes that are selected by selection mechanism as parents and combined them to produce offspring. Crossover operator makes an optimistic attempt to swap parent sections and produce offspring that inherit promising features from their parents. The steps of the crossover operator are as follows:

The position-based crossover (PBX) selects a subset of positions in the first parent and copies the jobs at these positions into the offspring. The remaining positions are filled with the missing jobs appearing in the same relative order as in the second parent. This crossover is illustrated in Figure 11.

Figure 11.

PBX crossover.

Mutation operator

The mutation operator revolves the structure of some chromosomes in the generation in order to guaranty diversification of solutions. It also helps to prevent from falling into local optimum trap; in other words, mutation can be considered as a background operator in GA, and the use of a mutation is also controlled by a probability parameter, which is called the mutation rate. The simple mutation operator that is used here randomly selects two positions in a chromosome and exchanges their genes with each other. This procedure is shown in Figure 12.

Figure 12.

Mutation operator.

ANN

Neural networks are composed of simple elements operating in parallel. These elements are inspired by biological nervous systems. We can train a neural network to work by adjusting the weights between elements. Commonly neural networks are adjusted or trained so that an input leads to a target output.³⁹ Such a situation is shown in Figure 13.

Figure 13.

Structure of ANN.

In this research, ANN is applied to calibrate parameters of the proposed algorithm. The effective attributes for a learning sample on an optimization process (inputs) can be number of jobs (n), number of machines (m), mean operation processing time (MOPT) and operation processing time variance (OPTV), MTTR, the time between two consecutive PM activities on machine (TPM) and breakdown level of the shop floor (Ag). Therefore, ANN consists of seven neurons $x_{i}, i = 1, 2, \dots, 7$ . Outputs are considered as $y_{j}, j = 1, 2, \dots, r$ , where r is the number of hidden layer in ANN. The output layers are equal to the parameters of the proposed algorithm. In other words, the output layers in these algorithms are ζ, number of imperialists, Ni; number of (countries, iteration), Nc; and revolution rate, Rr.

We assume that the weight matrix between input and hidden layers is W and weight matrix between hidden and output layers is V. the parameters of the algorithms are determined using weights obtained from ANN. The samples and related desired algorithm parameters are obtained by experimental study. Back propagation network is indicated in Figure 14.

Figure 14.

The structure of three layers of back propagation network for the proposed algorithm.

The steps of the back propagation algorithm are as follows:^58,59

Step 1. Choose the learning coefficient (0 < η < 1).

Step 2. Choose initial V and W randomly.

Step 3. The learning samples that are obtained by experimental study are entered, and input and output net values of every neuron layer are calculated by layer set E = 0:

For hidden layers

Y_{jp} = \sum_{i = 1}^{7} x_{ip} \times W_{ij} \forall j = 1, 2 \dots, r and p = 1, 2, \dots, P_{\max}

(11)

Sigmoid function is used as transfer function for all hidden layers’ neuron

f (n) = \frac{1}{1 + e^{- n}} n \in (- \infty + \infty)

(12)

y_{jp} = f (Y_{jp}) \forall j = 1, 2, \dots, r and p = 1, 2, \dots, P_{\max}

(13)

For output layers

Z_{lp} = \sum_{j = 1}^{r} y_{jp} \times V_{jl} \forall l = 1, 2, \dots, 4 and p = 1, 2, \dots, P_{\max}

(14)

Linear function is used as transfer function for all output layers’ neuron

g (n) = n

(15)

z_{lp} = g (Z_{lp}) \forall l = 1, 2, \dots, 4 and p = 1, 2, \dots, P_{\max}

(16)

Step 4. Calculate the error (E)

E = \sum_{p = 1}^{P_{\max}} [\frac{1}{2} \sum_{l = 1}^{4} {(d_{lp} - z_{lp})}^{2}]

(17)

where nm is the number of parameters of the proposed algorithm that should be tuned, $d_{lp}$ is the lth desired output of ANN for pth learning sample and $z_{lp}$ is the lth actual output of ANN for pth learning sample.

Step 5. Calculate error signal of every neuron layer by layer

δ (z_{lp}) = (d_{lp} - z_{lp}) \times z_{lp} \times (1 - z_{lp}) \forall l = 1, 2, \dots, 4 and p = 1, 2, \dots, P_{\max}

(18)

δ (y_{jp}) = (\sum_{l = 1}^{nm} δ (z_{lp}) \times V_{jl}) \times y_{jp} (1 - y_{jp}) \forall j = 1, 2, \dots, r and p = 1, 2, \dots, P_{\max}

(19)

Step 6. Update V and W matrixes

W_{ij} = W_{ij} + η \times E (δ (y_{jp}) \times x_{ip}) \forall i = 1, 2, \dots, 7 and j = 1, 2, \dots, r

(20)

V_{jl} = V_{jl} + η \times E (δ (z_{lp}) \times y_{jp}) \forall j = 1, 2, \dots, r and l = 1, 2, \dots, 4

(21)

Step 7. Terminate the algorithm if the stopping criterion is met; otherwise, go to step 3.^58,59

Learning samples and related desired ICA parameters are obtained by experimental study. These learning samples are presented in Tables 2 and 3. For these calculations, the learning coefficient is assumed to be 0.95, number of layers in hidden layer is chosen as 11 and number of iteration is selected as 100,000, which is the stopping criterion. The effect of the number of neurons in hidden layer on E is computed 10 times, and mean values in ICA algorithm are shown in Figure 15. ICA parameters are determined by weights being obtained by ANN with the optimum number of neurons in the hidden layers.

Table 2.

Learning samples to train ANN.

Learning sample	N	m	TPM	MTTR	Ag	MOPTV	OPTV
1	20	4	450	0.1 $\bar{P}$	0.00524	49.73	838.15
2	20	8	650	$5 \bar{P}$	0.05	49.45	783.79
3	20	8	450	$5 \bar{P}$	0.11364	49.45	783.79
4	20	6	450	$\bar{P}$	0.025	56.7	774.17
5	20	2	650	$\bar{P}$	0.20833	49.5	957.31
6	40	4	650	$5 \bar{P}$	0.11364	49.6	958.05
7	40	2	450	$0.1 \bar{P}$	0.0051	51.69	927.12
8	40	8	650	$5 \bar{P}$	0.20833	49.45	761.87
9	40	2	450	$\bar{P}$	0.025	51.69	927.12
10	40	6	650	$5 \bar{P}$	0.11364	49.45	761.87
11	40	2	450	$\bar{P}$	0.0051	51.69	927.12
12	40	2	650	$0.1 \bar{P}$	0.0051	48.91	855.19
13	60	2	450	$5 \bar{P}$	0.11364	51.69	927.12
14	60	4	650	$0.1 \bar{P}$	0.0051	51.69	927.12
15	60	6	450	$0.1 \bar{P}$	0.0051	46.45	917.7
16	60	8	650	$\bar{P}$	0.025	47.48	842.18
17	60	4	650	$5 \bar{P}$	0.05	50.33	842.87
18	60	6	650	$0.1 \bar{P}$	0.0051	50.2	824.87
19	60	4	650	$0.1 \bar{P}$	0.00524	47.48	842.18
20	80	4	650	$\bar{P}$	0.025	50.56	821.2
21	80	6	650	$0.1 \bar{P}$	0.0051	49.6	778.3
22	80	8	450	$5 \bar{P}$	0.20833	49.26	839.6
23	80	8	650	$5 \bar{P}$	0.11364	49.26	839.6
24	80	2	650	$\bar{P}$	0.05	48.02	794.22
25	80	6	450	$\bar{P}$	0.11364	49.6	778.3
26	80	4	650	$0.1 \bar{P}$	0.00524	50.56	821.2

TPM: time between two consecutive PM activities on machine; MTTR: mean time to repair; MOPTV: mean operation processing time variance; OPTV: operation processing time variance; Ag: breakdown level of the shop floor.

Table 3.

Desired output to train ANN for ICA algorithm.

Learning sample	ICA
	ζ	Ni	Nc	Rr
1	0.04	5	(100, 100)	0.05
2	0.04	5	(100, 200)	0.05
3	0.05	5	(100, 200)	0.1
4	0.04	5	(100, 100)	0.1
5	0.05	5	(100, 100)	0.05
6	0.05	8	(150, 100)	0.15
7	0.04	8	(150, 100)	0.05
8	0.04	8	(250, 300)	0.1
9	0.05	12	(150, 100)	0.15
10	0.05	10	(250, 300)	0.15
11	0.05	8	(300, 400)	0.1
12	0.05	8	(250, 300)	0.1
13	0.06	10	(300, 400)	0.1
14	0.06	8	(250, 300)	0.05
15	0.06	10	(400, 400)	0.2
16	0.06	12	(300, 400)	0.15
17	0.06	12	(400, 400)	0.15
18	0.05	15	(300, 400)	0.2
19	0.06	15	(300, 400)	0.1
20	0.04	15	(400, 400)	0.15
21	0.04	12	(400, 500)	0.15
22	0.06	12	(400, 500)	0.15
23	0.06	15	(400, 400)	0.15
24	0.06	12	(400, 400)	0.2
25	0.06	15	(400, 500)	0.2
26	0.06	15	(400, 500)	0.2

Figure 15.

Effect of number of neurons in the hidden layer on mean error.

In this research, the number of simulations was selected by sensitivity analysis; in other words, the best value of this parameter is obtained by changing its value while keeping other parameters as constant after some experimentations, and after no major changes in the performance have been noted, the parameter was set as given in Table 4.

Table 4.

Number of simulation in simulator algorithm.

Number of jobs (n)	Number of simulation (ns)
20	8
40	10
60	10
80	14

Experimental design

Data required for this problem are classified into two groups: (1) data related to the production part and (2) data related to the maintenance and machine breakdown parts. The first group consisted of the number of jobs (n), number of machines (m) and processing time of jobs (P). Processing times are randomly generated from a uniform distribution (1,100). The second group consisted of duration of PM activities (DPM) and the interval between two consecutive PM activities (TPM) that we defined TPM by the number of jobs (n). If n ⩽ 40, then TPM = 450; otherwise, TPM = 650. The values for MTTR are chosen as $0.1 \bar{P}, \bar{P}, and 5 \bar{P}$ , where $\bar{P}$ is the mean total processing time of a job. Ag is the breakdown level of the shop, and it indicates the percent of time the machines have failure, where Ag = MTTR/(MTBF + MTTR). The problem data are illustrated in Table 5. For example, if MTTR = 50.5 time units ( $\bar{P}$ ) and Ag = 0.20833 time units, then $MTBF = ((1 - 0.20833) \cdot 50.5) / (0.20833) = 192$ ; in other words, if 20.833% of the time machines have failure in shop, then MTBF is 192 time units. Flowchart of the proposed algorithm is shown in Figure 16.

Table 5.

Problems factor levels.

Factor	Levels
Processing time	Unif(1–100)
Number of jobs	80	60	40	20
TPM	650	450
DPM	Unif(20–120)	Unif(20–100)	Unif(20–60)
Number of machines at stage 1	8	6	4	2
MTTR	$5 \bar{P}$	$\bar{P}$	$0.1 \bar{P}$
Ag	0.20833	0.11364	0.05	0.025	0.00524	0.0051

TPM: time between two consecutive PM activities on machine; MTTR: mean time to repair; DPM: duration of PM activities; Ag: breakdown level of the shop floor.

Figure 16.

Flowchart of the proposed ICA.

In this study, the Taguchi experimental design is applied to analyze the effect of parameters of the problem. The “parameter design” developed by Dr Taguchi in early 1960s can be applied to process design. Taguchi classifies factors into controllable and noise factors; this method searches to minimize the effect of noise factors and determine optimal level of important controllable factors based on the concept of robustness.

Taguchi classifies objective functions into three categories:

The smaller is the better;

The larger is the better;

The nominal is the best.

Taguchi introduces signal-to-noise (S/N) ratio and relative percentage deviation (RPD). The S/N ratio denotes the amount of variation in the response variable that must be maximized. The formula is

\frac{S}{N} = - 10 \log {(\frac{1}{k} \sum_{i = 1}^{k} E (O F_{i}))}^{2}

(22)

In the following, Taguchi scheme is explained and then the Taguchi experimental design and the analysis of variance (ANOVA) results are analyzed.

In the Taguchi method, for selecting the appropriate orthogonal array it is necessary to obtain the number of degrees of freedom. The appropriate scheme should have degrees of freedom 17 (1 + 3 + 1 + 2 + 3 + 2 + 5). Therefore, the appropriate design must have at least 17 rows. An appropriate array that satisfies this condition is $L_{32 (4^{8}, 8^{1})}$ , and it is shown in Table 6, where control factors are assigned to the columns of the orthogonal array. We should adjust this array to analyze the factors. Each trial calculated 10 times, and the S/N ratios of the expected makespan are summarized in Table 7. Figure 15 shows the mean S/N ratios in each level of factors for the proposed ICA.

Table 6.

The orthogonal array $L_{32 (4^{8}, 8^{1})}$ .

Trial	A	B	C	D	E	F	G	H	I
1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	4	4	3	3	2
3	1	2	3	4	1	2	3	4	3
4	1	2	4	3	4	3	1	2	4
5	1	3	1	3	2	4	2	4	5
6	1	3	2	4	3	1	4	2	6
7	1	4	3	2	2	3	4	1	7
8	1	4	4	1	3	2	2	3	8
9	2	1	3	4	3	4	2	1	4
10	2	1	4	3	2	1	4	3	3
11	2	2	1	1	3	3	4	4	2
12	2	2	2	2	2	2	2	2	1
13	2	3	3	2	4	1	1	4	8
14	2	3	4	1	1	4	3	2	7
15	2	4	1	3	4	2	3	1	6
16	2	4	2	4	1	3	1	3	5
17	3	1	3	1	4	2	4	2	5
18	3	1	4	2	1	3	2	4	6
19	3	2	1	4	4	1	2	3	7
20	3	2	2	3	1	4	4	1	8
21	3	3	3	3	3	3	3	3	1
22	3	3	4	4	2	2	1	1	2
23	3	4	1	2	3	4	1	2	3
24	3	4	2	1	2	1	3	4	4
25	4	1	1	4	2	3	3	2	8
26	4	1	2	3	3	2	1	4	7
27	4	2	3	1	2	4	1	3	6
28	4	2	4	2	3	1	3	1	5
29	4	3	1	2	1	2	4	3	4
30	4	3	2	1	4	3	2	1	3
31	4	4	3	3	1	1	2	2	2
32	4	4	4	4	4	4	4	4	1

Table 7.

S/N and RPD ratios for values of objective function.

Trial	Job	Machine	DPM	MTTR	Ag	TPM	S/N ratio for ICA	RPD ratio for ICA
1	1	1	1	1	1	1	−58.807891904	0.237779571
2	1	1	2	2	2	2	−58.567284894	0.693016566
3	1	2	3	1	3	1	−59.918400057	0.18124467
4	1	2	1	3	4	2	−57.532101962	0.49512815
5	1	3	1	3	5	1	−62.614615091	1.764631722
6	1	3	2	1	6	2	−61.186297797	0.637143493
7	1	4	3	2	5	1	−59.923918742	2.38260573
8	1	4	2	1	6	2	−58.12117802	0.91611337
9	2	1	3	3	4	1	−63.963036773	0.474927015
10	2	1	2	3	3	2	−62.516650849	0.42831552
11	2	2	1	1	2	1	−65.947789661	0.272120823
12	2	2	2	2	1	2	−64.956297797	0.48243402
13	2	3	3	2	2	1	−63.982906055	0.66209405
14	2	3	1	1	3	2	−62.650609557	0.837410559
15	2	4	1	3	6	1	−69.14667982	1.2721085
16	2	4	2	2	5	2	−66.385911773	2.056562344
17	3	1	3	1	5	1	−66.581407151	0.411562344
18	3	1	3	2	6	2	−66.519567403	0.483792778
19	3	2	1	1	5	1	−69.454131924	0.13284898
20	3	2	2	3	6	2	−70.27709516	0.721295
21	3	3	3	3	1	1	−66.813773266	1.14969711
22	3	3	2	1	2	2	−65.523401134	0.75523738
23	3	4	1	2	3	1	−69.644764804	0.2338752
24	3	4	2	1	4	2	−68.713049449	0.19631304
25	4	1	1	2	4	1	−71.841885522	0.4196932
26	4	1	2	3	1	2	−70.462680295	0.27715242
27	4	2	3	1	6	1	−70.311644943	0.58761985
28	4	2	3	2	5	2	−69.539794301	0.921088363
29	4	3	1	2	4	1	−72.219106317	0.437945224
30	4	3	2	1	3	2	−70.913177238	0.29657324
31	4	4	3	3	2	1	−69.716373122	0.2730574
32	4	4	2	3	1	2	−68.393019313	1.05715808

TPM: time between two consecutive PM activities on machine; MTTR: mean time to repair; DPM: duration of PM activities; Ag: breakdown level of the shop floor; S/N: signal-to-noise; ICA: imperialist competitive algorithm; RPD: relative percentage deviation.

As indicated in Figure 17, better robustness of the algorithms is achieved when we have problem with the following characteristics: job 2, machine 2, $MTTR = 0.1 \bar{P}$ , TPM = 650, DPM = Unif(20, 100)and Ag = 0.025. ANOVA for ICA algorithm is indicated in Table 8.

Figure 17.

The average signal-to-noise (S/N) ratio plot at each level for ICA algorithm.

Table 8.

ANOVA for S/N ratio in ICA algorithm.

Factor	DF	SS	MS	F	Percent X	Cumulative
Job	3	834.25426	278.08475	4.2778174	23.11	23.11
Machine	3	319.90433	106.63478	1.640378	4.51	27.62
MTTR	2	326.76173	163.38086	2.5133111	7.11	34.73
TPM	1	322.56633	322.56633	4.9620839	9.31	44.04
DPM	2	313.00628	156.50314	2.4075101	6.61	50.65
Error	5	325.03112	65.006223
Total	16	2766.5552	172.90970

TPM: time between two consecutive PM activities on machine; MTTR: mean time to repair; DPM: duration of PM activities; DF: degree of freedom; SS: sum of squares; MS: mean square.

The goal of ANOVA is to inspect the relevant implication of individual parameters based on the objective value. In other words, by means of ANOVA, the parameters that are more effective in problem will be identified. Results that are obtained from ANOVA indicate that the job and TPM factor have a significant impact on the robustness of the algorithm. RPD is used to understand adjustment factors and is calculated from the formula

RP D_{ij} = \frac{{(Al g_{sol})}_{ij} - Mi n_{sol}}{Mi n_{sol}} \cdot 100

where $Al g_{sol}$ is the objective value that is obtained for a trial by an algorithm and $Mi n_{sol}$ is the best solution obtained for each trial that is computed by any of the algorithms. The mean RPD for the proposed algorithms is summarized in Table 7.

Figure 18 shows the mean RPD in each level of factors; ANOVA for RPD is given in Table 9, and they show that machine, MTTR and Ag are considered as adjusting factors. The other factors that have no significant impact on the S/N or RPD ratio are economic factors, and the levels that reduce the CPU time can be selected.

Figure 18.

The average relative percentage deviation (RPD) ratio plot at each level for ICA algorithm.

Table 9.

ANOVA for RPD ratio in ICA algorithm.

Factor	DF	SS	MS	F	Percent X	Cumulative
Job	3	1.017224938	0.339074979	1.637380438	10.58751585	10.58751585
Machine	3	2.128221985	0.709407328	3.42570155	25.10683656	35.69435241
MTTR	2	1.158093541	0.579046771	2.796195275	13.33059711	49.02494952
Ag	5	3.141228523	0.628245705	3.033775094	36.54133076	85.56628028
Error	3	0.20708381	0.069027937
Total	16	7.651852797	0.4782408

MTTR: mean time to repair; Ag: breakdown level of the shop floor; DF: degree of freedom; SS: sum of squares; MS: mean square.

To compare proposed ICA, 32 combinations are considered that these are based on different values of number of job, number of machines at the first stage, DPM, TPM, MTTR and Ag. We used the Taguchi design to obtain them, and the computational results are transformed into RPD measure, which are illustrated in Table 10 for the two proposed algorithms.

Table 10.

Average relative percentage deviation (RPD) for the two proposed algorithms.

Trial	Algorithms		Trial	Algorithms
	GA	ICA		GA	ICA
1	0.00951	0.00723	17	0.01626	0.01126
2	0.0114	0.009	18	0.02519	0.01411
3	0.0135	0.0124	19	0.01134	0.01328
4	0.0123	0.00721	20	0.02617	0.01623
5	0.01321	0.01012	21	0.03412	0.01162
6	0.0114	0.0065	22	0.02724	0.02012
7	0.01426	0.01023	23	0.03518	0.02702
8	0.0102	0.0087	24	0.02291	0.01374
9	0.0142	0.011	25	0.02416	0.01672
10	0.01025	0.01127	26	0.02831	0.02251
11	0.01625	0.01081	27	0.03211	0.02157
12	0.0092	0.01023	28	0.02627	0.02117
13	0.01724	0.01131	29	0.02772	0.02014
14	0.02012	0.01331	30	0.02821	0.01547
15	0.02816	0.02014	31	0.02665	0.01325
16	0.01246	0.01373	32	0.02636	0.01981
Mean				0.020058	0.0141

GA: genetic algorithm; ICA: imperialist competitive algorithm.

Based on computational results that are demonstrated in Table 10, ICA performs better than GA; we used least significant difference (LSD) method for calculating significant difference. LSD is illustrated in Figure 19, and it shows that there is no significant difference between ICA and GA; in other words, ICA has better performance than GA.

Figure 19.

Means plot and LSD intervals (at the 95% confidence level) for the two proposed algorithms.

Moreover, the t-test is used as a method for statistical testing, and hypothesis testing is as follows

H_{0} = The average error of ICA = The average error of GA

H_{1} = The average error of ICA > The average error of GA

The null hypothesis was rejected for all combinations of parameter at a 95% significance level. Thus, average RPD of ICA is statistically smaller than GA; in other words, ICA performs better than GA in most of the problems. Figures 20 and 21 show the RPD values for GA and ICA in different values of number of jobs and machines.

Figure 20.

Average percent error for different values of number of jobs.

Figure 21.

Average percent error for different values of number of machines at the first stage.

Conclusion and future works

In this article, we considered the two-stage assembly flow shop scheduling problem with PM activities and random machine breakdowns. ICA and GA were proposed for finding schedules that minimize the expected makespan. For better performance of the proposed algorithms, parameters of them were tuned by the ANN, and then problem parameters were analyzed by the Taguchi experimental design to reach their effects on response. At the end, the conducted t-test showed that the average error of ICA is statistically smaller than GA; in other words, ICA performs better than GA in most of the problems. As future studies on this problem, it is possible to consider other objectives. As future studies, it is possible to find robust or stable schedules in the uncertainty condition. Another interesting direction for future research is to suggest the use of Weibull distribution that is used in many of the shops. A future research is to develop a multi-objective approach for this problem to create a balance between makespan and system reliability.

Footnotes

Declaration of conflicting interests

The authors declare that there is no conflict of interest.

Funding

This research received no specific grant from any funding agency in the public, commercial or not-for-profit sectors.

References

Potts

Sevast’janov

Van Wassenhove

. The two-stage assembly scheduling problem: complexity and approximation. Oper Res1995; 43(2): 346–355.

Allahverdi

. Two-machine proportionate flow shop scheduling with breakdowns to minimize maximum lateness. Comput Oper Res1996; 23: 909–916.

Allahverdi

Al-Anzi

. Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times. Int J Prod Res2006; 44(22): 4713–4735.

Suresh

Chaudhuri

. Dynamic scheduling: a survey of research. Int J Prod Econ1993; 32(1): 53–63.

Stoop

PPM

Weirs

VCS

. The complexity of scheduling in practice. Int J Oper Prod Man1996; 16(10): 37–53.

Cowling

Johansson

. Using real-time information for effective dynamic scheduling. Eur J Oper Res2002; 139(2): 230–244.

Vieira

Hermann

Lin

. Rescheduling manufacturing systems: a framework of strategies, policies and methods. J Sched2003; 6(1): 39–62.

Gholami

Zandieh

Alem-Tabriz

. Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. Int J Adv Manuf Tech2009; 42: 189–201.

Lee

C-Y

Cheng

TCE

Lin

BMT

. Minimising the makespan in the 3-machine assembly-type flowshop scheduling problem. Manage Sci1993; 39(5): 616–625.

10.

Haouari

Daouas

. Optimal scheduling of the 3-machine assembly-type flow shop. RAIRO-Oper Res1999; 33(4): 439–445.

11.

Sun

Morizawa

Nagasawa

. Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling. Eur J Oper Res2003; 146(3): 498–516.

12.

Tozkapan

Kirca

Chung

. A branch and bound algorithm to minimise the total weighted flowtime for the two-stage assembly scheduling problem. Comput Oper Res2003; 30(2): 309–320.

13.

Allahverdi

Al-Anzi

. The two-stage assembly flowshop scheduling problem to minimise total completion time with setup times. Comput Oper Res2009; 36(10): 2740–2747.

14.

Al-Anzi

Allahverdi

. A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times. Eur J Oper Res2007; 182: 80–94.

15.

Shokrollahpour

Zandieh

Behrooz

Dorri

. A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flow shop problem. Int J Prod Res2011; 49(11): 3087–3103.

16.

Torabzadeh

Zandieh

. Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flow shop. Adv Eng Softw2010; 41: 1238–1243.

17.

Lee

. Machine scheduling with an availability constraint. J Global Optim1996; 9(3–4): 395–416.

18.

Allahverdi

Al-Anzi

. The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time. Int J Adv Manuf Tech2007; 37(1): 166–177.

19.

Hwang

Lin

BMT

. Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence. J Oper Res Soc2012; 63(6): 839–845.

20.

Mozdgir

FatemiGhomi

SMT

Joli

. Two-stage assembly flow-shop scheduling problem with non-identical assembly machines considering setup times. Int J Prod Res2013; 51: 3625–3642.

21.

Seidgar

Kiani

Abedi

. An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flow shop problem. Int J Prod Res2014; 52(4): 1240–1256.

22.

Xiong

Xing

. Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time. Int J Prod Res2014; 52(9): 2743–2766.

23.

Yan

H-S

Wan

X-Q

Xiong

F-L

. A hybrid electromagnetism-like algorithm for two-stage assembly flow shop scheduling problem. Int J Prod Res2014; 52: 5626–5639.

24.

Lee

. Two-machine flowshop scheduling with availability constraints. Eur J Oper Res1999; 114(2): 420–429.

25.

Blazewicz

Berit

Formanowicz

. Heuristic algorithms for the two-machine flowshop problem with limited machine availability. Omega J2001; 29(6): 599–608.

26.

Kubiak

Blazewicz

Formanowicz

. Two-machine flow shops with limited machine availability. Eur J Oper Res2002; 136(3): 528–540.

27.

Sherif

Smith

. Optimal maintenance models for systems subject to failure—a review. Nav Res Log1981; 28(1): 47–74.

28.

Wang

. A survey of maintenance policies of deteriorating systems. Eur J Oper Res2002; 139(3): 469–489.

29.

Kaabi

Varnier

Zerhouni

. Genetic algorithm for scheduling production and maintenance in a flow-shop. Besançon: Laboratory of Automatic of Besancon, 2003 (in French).

30.

Gharbi

Kenne

. Maintenance scheduling and production control of multiple-machine manufacturing systems. Comput Ind Eng2005; 48(4): 693–707.

31.

Ruiz

Carlos Garcia-Diaz

Maroto

. Considering scheduling and preventive maintenance in the flowshop sequencing problem. Comput Oper Res2007; 34: 3314–3330.

32.

Safari

Sadjadi

. A hybrid method for flow shops scheduling with condition-based maintenance constraint and machines breakdown. Expert Syst Appl2011; 38: 2020–2029.

33.

Berrichi

Amodeo

Yalaoui

. Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem. J Intell Manuf2008; 20: 389–400.

34.

Moradi

Fatemi Ghomi

SMT

Zandieh

. Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem. Expert Syst Appl2011; 38(6): 7169–7178.

35.

Mokhtari

Mozdgir

Abadi

. A reliability/availability approach to joint production and maintenance scheduling with multiple preventive maintenance services. Int J Prod Res2012; 50(20): 5906–5925.

36.

Majazi Dalfard

Mohammadi

. Two meta-heuristic algorithms for solving multi-objective flexible job-shop scheduling with parallel machine and maintenance constraints. Comput Math Appl2012; 64: 2111–2117.

37.

Sarker

Omar

Kamrul Hasan

. Hybrid Evolutionary Algorithm for job scheduling under machine maintenance. Appl Soft Comput2013; 13: 1440–1447.

38.

Benmansour

Allaoui

Artiba

. Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance. Comput Oper Res2014; 47: 106–113.

39.

Bose

Liang

. Neural network fundamentals with graph, algorithms, and application. New Delhi, India: Tata McGraw Hill, 1996.

40.

Allaoui

Artiba

. Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. Comput Ind Eng2004; 47(4): 431–450.

41.

Zandieh

Gholami

. An immune algorithm for scheduling a hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. Int J Prod Res2009; 47: 6999–7027.

42.

Jabbarizadeh

Zandieh

Talebi

. Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints. Comput Ind Eng2009; 57: 949–957.

43.

Ghezail

Pierreval

Hajri-Gabouj

. Analysis of robustness in proactive scheduling: a graphical approach. Comput Ind Eng2010; 58: 193–198.

44.

Lei

. Scheduling stochastic job shop subject to random breakdown to minimize makespan. Int J Adv Manuf Tech2011; 55: 1183–1192.

45.

Naderi

Zandieh

Aminnaveri

. Incorporating periodic preventive maintenance into flexible flowshop scheduling problems. Appl Soft Comput2011; 11(2): 2094–2101.

46.

AL-Hinai

ElMekkawy

. Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm. Int J Prod Econ2011; 132: 279–291.

47.

Dong

Jang

. Production rescheduling for machine breakdown at a job shop. Int J Prod Res2012; 50(10): 2681–2691.

48.

J-Q

Pan

Q-K

Tasgetiren

. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Appl Math Model2014; 38(3): 1111–1132.

49.

Moghadam

. Multi-objective preventive maintenance and replacement scheduling in a manufacturing system using goal programming. Int J Prod Econ2013; 146(2): 704–716.

50.

Cassady

Kutanoglu

. Minimizing job tardiness using integrated preventive maintenance planning and production scheduling. IIE Trans2003; 35(6): 503–513.

51.

Kurz

Askin

. Scheduling flexible flow lines with sequence-dependent setup times. Eur J Oper Res2004; 159(1): 66–82.

52.

Atashpaz-Gargari

Lucas

. Imperialist competitive algorithm: an algorithm for optimization inspired by imperialist competition. In: IEEE congress on evolutionary computation, 25–28 September 2007, Singapore, pp.4661–4667. New York: IEEE.

53.

Atashpaz-Gargari

Hashemzadeh

Lucas

. Designing MIMO PIID controller using colonial competitive algorithm: applied to distillation column process, control and intelligent processing center of excellence. In: IEEE congress on evolutionary computation, 1–6 June 2008, Hong Kong, pp.1929–1934. New York: IEEE.

54.

Goldberg

. Genetic algorithms: Search, optimization machine learning. Boston, MA: Addison-Wesley, Inc., 1989.

55.

Reeves

. Genetic algorithms for the operations researcher. INFORMS J Comput1997; 9: 231–250, 572–573.

56.

Reeves

. Genetic algorithms. In: Glover

Kochenberger

(eds) Handbook of metaheuristics. Dordrecht: Kluwer Academic Publishers, 2003, pp.55–82.

57.

Khorshidian

Javadian

Zandieh

. A genetic algorithm for JIT single machine scheduling with preemption and machine idle time. Expert Syst Appl2011; 38: 7911–7918.

58.

Adibi

Zandieh

Amiri

. Multi-objective scheduling of dynamic job shop using variable neighborhood search. Expert Syst Appl2010; 37: 282–287.

59.

Zandieh

Adibi

. Dynamic job shop scheduling using variable neighborhood search. Int J Prod Res2010; 48: 2449–2458.

60.

Yamamoto

Nof

. Scheduling/rescheduling in the manufacturing operating system environment. Int J Prod Res1985; 23(4): 705–722.

Trial	A	B	C	D	E	F	G	H	I
1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	4	4	3	3	2
3	1	2	3	4	1	2	3	4	3
4	1	2	4	3	4	3	1	2	4
5	1	3	1	3	2	4	2	4	5
6	1	3	2	4	3	1	4	2	6
7	1	4	3	2	2	3	4	1	7
8	1	4	4	1	3	2	2	3	8
9	2	1	3	4	3	4	2	1	4
10	2	1	4	3	2	1	4	3	3
11	2	2	1	1	3	3	4	4	2
12	2	2	2	2	2	2	2	2	1
13	2	3	3	2	4	1	1	4	8
14	2	3	4	1	1	4	3	2	7
15	2	4	1	3	4	2	3	1	6
16	2	4	2	4	1	3	1	3	5
17	3	1	3	1	4	2	4	2	5
18	3	1	4	2	1	3	2	4	6
19	3	2	1	4	4	1	2	3	7
20	3	2	2	3	1	4	4	1	8
21	3	3	3	3	3	3	3	3	1
22	3	3	4	4	2	2	1	1	2
23	3	4	1	2	3	4	1	2	3
24	3	4	2	1	2	1	3	4	4
25	4	1	1	4	2	3	3	2	8
26	4	1	2	3	3	2	1	4	7
27	4	2	3	1	2	4	1	3	6
28	4	2	4	2	3	1	3	1	5
29	4	3	1	2	1	2	4	3	4
30	4	3	2	1	4	3	2	1	3
31	4	4	3	3	1	1	2	2	2
32	4	4	4	4	4	4	4	4	1

Trial	A	B	C	D	E	F	G	H	I
1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	4	4	3	3	2
3	1	2	3	4	1	2	3	4	3
4	1	2	4	3	4	3	1	2	4
5	1	3	1	3	2	4	2	4	5
6	1	3	2	4	3	1	4	2	6
7	1	4	3	2	2	3	4	1	7
8	1	4	4	1	3	2	2	3	8
9	2	1	3	4	3	4	2	1	4
10	2	1	4	3	2	1	4	3	3
11	2	2	1	1	3	3	4	4	2
12	2	2	2	2	2	2	2	2	1
13	2	3	3	2	4	1	1	4	8
14	2	3	4	1	1	4	3	2	7
15	2	4	1	3	4	2	3	1	6
16	2	4	2	4	1	3	1	3	5
17	3	1	3	1	4	2	4	2	5
18	3	1	4	2	1	3	2	4	6
19	3	2	1	4	4	1	2	3	7
20	3	2	2	3	1	4	4	1	8
21	3	3	3	3	3	3	3	3	1
22	3	3	4	4	2	2	1	1	2
23	3	4	1	2	3	4	1	2	3
24	3	4	2	1	2	1	3	4	4
25	4	1	1	4	2	3	3	2	8
26	4	1	2	3	3	2	1	4	7
27	4	2	3	1	2	4	1	3	6
28	4	2	4	2	3	1	3	1	5
29	4	3	1	2	1	2	4	3	4
30	4	3	2	1	4	3	2	1	3
31	4	4	3	3	1	1	2	2	2
32	4	4	4	4	4	4	4	4	1

Trial	A	B	C	D	E	F	G	H	I
1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	4	4	3	3	2
3	1	2	3	4	1	2	3	4	3
4	1	2	4	3	4	3	1	2	4
5	1	3	1	3	2	4	2	4	5
6	1	3	2	4	3	1	4	2	6
7	1	4	3	2	2	3	4	1	7
8	1	4	4	1	3	2	2	3	8
9	2	1	3	4	3	4	2	1	4
10	2	1	4	3	2	1	4	3	3
11	2	2	1	1	3	3	4	4	2
12	2	2	2	2	2	2	2	2	1
13	2	3	3	2	4	1	1	4	8
14	2	3	4	1	1	4	3	2	7
15	2	4	1	3	4	2	3	1	6
16	2	4	2	4	1	3	1	3	5
17	3	1	3	1	4	2	4	2	5
18	3	1	4	2	1	3	2	4	6
19	3	2	1	4	4	1	2	3	7
20	3	2	2	3	1	4	4	1	8
21	3	3	3	3	3	3	3	3	1
22	3	3	4	4	2	2	1	1	2
23	3	4	1	2	3	4	1	2	3
24	3	4	2	1	2	1	3	4	4
25	4	1	1	4	2	3	3	2	8
26	4	1	2	3	3	2	1	4	7
27	4	2	3	1	2	4	1	3	6
28	4	2	4	2	3	1	3	1	5
29	4	3	1	2	1	2	4	3	4
30	4	3	2	1	4	3	2	1	3
31	4	4	3	3	1	1	2	2	2
32	4	4	4	4	4	4	4	4	1