Manufacturing operations outsourcing through an artificial team process algorithm

Abstract

The successful applications of artificial intelligence techniques have been widely increased during recent years. Today, outsourcing is a common strategy to enhance competitive advantages particularly for manufacturing industries. When a manufacturer receives a number of orders from customers, an internal capacity shortage is inevitable, and then the manufacturer may decide to outsource a certain set of orders. To get the joint decision on order scheduling and operation outsourcing in a parallel machine shop, an intelligent decision making technique which is based on an artificial team process algorithm (TPA) is designed in current paper. TPA is a recently evolutionary tool where operations of exploration and an epitome-based learning behavior is employed, and the operation division between elite and plain groups is elaborated. For a successful global search, the TPA lets one group (elite) explore more global spaces, while, for fast convergence, another group (plain) is assigned to local search. So, TPA is an efficient computational-based algorithm with the potential of global search during reasonable computational efforts. Additionally, a neighborhood search algorithm (NSA) with three kinds of neighborhood structures is devised to further enhance the quality of solutions at each iteration of TPA. Furthermore, the List Scheduling (LS), as a conventional scheduler, a GA and a SA are also customized for the addressed problem as benchmark algorithms. The comparisons are carried out and the results reveal the superiority of suggested method.

Keywords

Artificial intelligence operations outsourcing team process algorithm learning operation

1 Introduction

The outsourcing is a strategic solution including crucial aspects of the business, IT, human resources, manufacturing, marketing and supply chain. Production outsourcing is a cost-effective option for capacity management in operational level of a supply chain, where a company transfers all or parts of its manufacturing activities to an external remote supplier. A coordinated outsourcing and production plan can shorten lead times, save the costs, make an organization more flexible, and get an opportunity to focus on more value-added activities, and prepare for scalability. Manufacturing companies often face with situations where demands requested from customers are too much to be taken care of by internal manufacturing capacity. In such situations, one of possible option is that the company outsources its productions to a third party in order to handle the demand fluctuations. In an effort to reduce manufacturing costs, many organizations are looking to outsource, or at a minimum offshore, their operations [37]. To achieve the maximum potential benefit, management needs to decide what amounts of each product to be manufactured and what amounts to be outsourced to external subcontractors [15, 16]. To this end, an integration issue between production scheduling and outsourcing plan should be taken into consideration to cope with the complexity of coordination in operational supply chain, because the isolated approach causes frequent deadlocks, inflexible manufacturing schedules and inefficient resource utilization [25]. The integrated problem considers a production system where outsourcing is possible in parallel with the internal manufacturing in order to enhance the total scheduling performance. When a manufacturer decides for outsourcing, the potential benefit cannot be achieved unless there is a proper production plan and schedule to can cope with the complexity of joint decisions in the problem [42]. Although the decision on whether to manufacture in-house or employ an external supplier has always been a fundamental issue associated with manufacturing companies [34], a few researchers have studied the scheduling problem with outsourcing option. Hence, in this paper we propose a production scheduling in a company with parallel machines and options for operation subcontracts/outsourcing.

Among parallel-machine scheduling problems presented in literature, the problem of minimizing the makespan is the most studied work. The study performed by Ibbara and Kim’s [27] is a basis of comparison to current research methodologies designed to solve such problem. In their work, a simple list scheduling rules that have a worst-case bound of total number of machines is developed. An approximation algorithm was designed by Martello et al. [38] based on Lagrangean relaxation and a branch and bound algorithm to enhance the efficiency of solution method. In another work, Schuurman and Woeginger [28] describe future research directions of polynomial time approximation schemes methods for the parallel-machine problem with makespan criteria. Many researchers discuss that two phase decomposition approach with a linear program in the first phase and a scheduling heuristic in a second phase will result in better solutions with a significant improvement in computational time. Several two-phase heuristics were developed by Hariri and Potts [2] based on an initial first phase relaxation of the integer program to evaluate the makespan problem. Recently, Allahverdi et al. [1] presented a review of scheduling problems in parallel machine environment with setup times. Moreover, a tabu search algorithm is given by Logendran et al. [33] for the weighted tardiness objective of problem. Another heuristic for the parallel machine scheduling problem with the weighted mean completion time is the paper proposed by Weng et al. [24]. Rocha de Paula et al. [23] proposed a variable neighborhood search strategy for both identical and unrelated parallel machines with the makespan objective. Moreover, Ying and Cheng [21] studied a dynamic parallel machine scheduling problem with sequence-dependent setup times and devised an iterated greedy algorithm to address it efficiently. Balin [35] considered a non-identical parallel machine problem where a new genetic algorithm with a new “crossover operator” and “optimality criterion” was adapted. Mokhtari and Salmasnia [12, 13] and Mokhtari [14] evaluated intelligent optimization approaches to optimize in a address parallel machine scheduling systems. Moreover Teymourian et al. [10] suggested an intelligent water drops algorithm for addressing an agile manufacturing system. As it can be seen, almost all of the traditional studies on machine scheduling assume that processing of received orders is just possible via internal resources, while in realistic environments, outsourcing is frequently found in various manufacturing industries, especially in electronic, motor and printing companies. On other hands, outsourcing has become an interested subject for intelligent and expert systems researchers during recent years [6 , 36].

The rest of this paper is structures as follows. A literature review of related works on production scheduling with outsourcing option is presented in Section 2. In Section 3, a brief description of problem is presented and mixed integer mathematical model is developed. Section 4 describes the solution procedure based on artificial TPA algorithm while, Section 5 presents the list scheduling heuristic as a comparison metric. Performance analysis of proposed model and algorithm is performed in Section 6. Finally concluding remarks is illustrated in Section 7.

2 Related literature

In this section we are going to present a review on production scheduling literature with outsourcing decisions. In their work, Cai et al. [39] investigated a manufacturing model that involves two processing machines, with one owned by the manufacturer and the other by the subcontractor, in which all the outsourced jobs have to be transported back from the outside machines after completion. In order to optimize the total cost, involving the lateness cost, the overtime cost, and the cost to use the third-party machine, the authors designed an integer nonlinear model and an algorithm to find optimal solution. In another work, Chen and Li [45] considered a manufacturer with make-to-order fashion that receives a set of orders from its customers at the beginning of the planning horizon. In that work, the objective is to minimize the total cost, subject to a restriction on maximum completion times. To develop a heuristic for solving the model and also analyze worst-case and asymptotic performances of the heuristic, the computational complexity of the model was performed. Another research was presented by Ruiz-Torreset al. [4] to deal with the problem of finding outsourcing strategies or solutions that consider trade-offs between outsourcing cost and average tardiness in a single machine environment where n one-operation jobs are available; each one can be completed by either in-house machine or m identical outsource machines. Moreover, Lee and Sung [18] suggested a single machine scheduling problem with the outsourcing allowed where each job can be either processed on an in-house single-machine or outsourced. They considered minimizing the weighted sum of the outsourcing cost and the sum of completion times as a single objective, subject to available outsourcing budget. Some solution properties are derived in their work and also two associated heuristic algorithms and a branch and bound are devised for solution approach. A similar study on single machine scheduling problem has been reported by Lee and Sung [19] that includes the problem of minimizing maximum lateness and outsourcing costs, and problem of minimizing total tardiness and outsourcing costs, subject to outsourcing budget. Different from previous researches, a general outsourcing model of single stage scheduling problem has been suggested by Qi [40] with transportation issues. All outsourced jobs have to be returned to the original manufacturer in batches, and the transportation costs have to be taken into account in problem. Another work based on single stage production outsourcing has been proposed by Ruiz-Torres et al. [3] where both internal and external parallel resources are available and a bi-criteria model was developed to minimize the number of late orders and the total outsource machine time, simultaneously. Besides, a research on two stage outsourcing model of production scheduling was presented by Qi [41] in which each job needs two successive operations. In this problem, there exist two in-house machines where each one can perform both operations, and also another possibility of outsourcing first operations to an outside subcontractor.

One major shortcoming in almost all of past studies is that they limit the number of subcontractors available for manufacturing company to just one outside supplier. However, in practice, there exist often several companies to choose from for each order to be subcontracted. The use of several suppliers makes the problem more realistic and, at the same time, more complex to be formulated and solved. The authors could find only one study [45] that considered several available subcontractors to be selected for outsourcing. Another shortcoming observed in some previous studies like [18, 19] is that they assume unlimited capacity for subcontractors and hence they ignore the scheduling of outsourced orders which should be considered in parallel with the in-house scheduling. As remedy, the current paper supports several available suppliers to be selected for subcontracting and also considers the scheduling of outsourced orders as well as in-house ones.

As in many real cases, the subcontractor is located in a different location than the manufacturer company, a transportation time may be incurred for an outsourced order. To our knowledge, the only studies concentrated on transportation considerations in production outsourcing are presented by the same author [40, 41]. In current paper, in order to close the suggested model to the real manufacturing situations, we also consider the transportation time and cost in decision making process.

3 Operations outsourcing

In this section, a mathematical programming model of the parallel machine scheduling problem with an option for operation subcontracts is formulated. This problem can be stated as follows. At the beginning of planning horizon, a manufacturer receives a set of n different jobs/orders J = {J₁, J₂, …, J_n} where each one has to be processed on a set of M identical parallel machines M = {m₁, m₂, …, m_m}. The order processing times p_ij is known in advance. The orders should be processed on a machine once and each machine could handle just one order at a moment. All orders are available at time zero with predefined due dates. The preemption of orders is prohibited and cancelation is not allowed for the commenced orders. Every machine is fully available at time horizon without maintenance and breakdowns and the idleness is allowed for machines. In addition, the manufacturer can either process each order at its own plant or outsource them to one of outside remote subcontractors for processing. There are p subcontractors S = {S₁, S₂, …, S_p} available; each one can processes all the orders received. It is also assumed that the outsourcing cost of order J_i transferred to the subcontractor k is denoted by C_i,k, and the transportation times are denoted by matrix T. The problem is to assign each order to an appropriate production resource (in-house or one among external suppliers), and to sequence the orders on the machines so that the maximum completion times for all the orders is minimized subject to an available outsourcing budget.

In order to expose the model, we first introduce some notations below.

Job/order index

Machine index

Production resource index (1 ≤ k ≤ p + 1)

Number of jobs

Number of in-house machines

Number of subcontractors

Job number i

Machine number j

Subcontractor number k

Processing time of J_i

Transportation time between manufacturer and subcontractor S

Total available budget

Furthermore, the model includes the following decision variables.

t_i Starting time of J_i

X_i,k A binary variable that indicates whether J_i is assigned to the production resource k

y_i,h A binary variable that indicates precedence relation between J_i and J_h

C_max Maximum completion time

The mathematical formulation of problem is suggested as follows. $Minimize C_{max}$ (1) $\begin{matrix} Subject to \\ (t_{i} - t_{h} \geq p_{h} - {My}_{ih}) X_{i, k} . X_{h, k} \\ for i = 1, 2, \dots, n, h = 1, 2, \dots, n, \\ k = 1, 2, \dots, m + p \end{matrix}$ (2) $\begin{matrix} (t_{h} - t_{i} \geq p_{i} - M (1 - y_{ih})) X_{ik} . X_{h, k} \\ for i = 1, 2, \dots, n, h = 1, 2, \dots, n, \\ k = 1, 2, \dots, m + p \end{matrix}$ (3) $\sum_{k = 1}^{m + p} X_{i, k} = 1 for i = 1, 2, \dots, n$ (4) $(t_{i} - T_{(s - m)} X_{i, s} \geq 0) \sum_{k = m + 1}^{m + p} X_{i, k}$ (5) $\begin{matrix} for i = 1, 2, \dots, n, s = m + 1, \dots, m + p \\ (t_{i} + p_{i} + T_{(s - m)} X_{i, s} \leq C_{max}) \sum_{k = m + 1}^{m + p} X_{i, k} \end{matrix}$ (6) $\begin{matrix} for i = 1, 2, \dots, n, s = m + 1, \dots, m + p \\ (t_{i} + p_{i} + \leq C_{max}) \sum_{k = 1}^{m} X_{i, k} \end{matrix}$ (7) $\begin{matrix} for i = 1, 2, \dots, n \\ (\sum_{i = 1}^{n} \sum_{k = m + 1}^{m + p} X_{i, k} C_{i, k}) \leq M \end{matrix}$ (8) $C_{max} \geq 0, t_{i} \geq 0$ (9) $\begin{matrix} for i = 1, 2, \dots, n \\ y_{ih} = 0, 1 \end{matrix}$ (10) $for i = 1, 2, \dots, n, h = 1, 2, \dots, n$

The objective function is to minimize the maximum completion time or makespan. With constraint set (2) and (3), we guarantee that the start time of each order on each machine be greater than the completion time of previous order processed on that machine. Equivalently, these constraints make the requirements to prevent the overlap between consecutive orders. Constraint set (4) ensures that every job is assigned to exactly one internal machine or subcontractor. Constraint set (5) forces the outsourced jobs to be started after transportation delay incurred by distance between manufacturer plant and associated subcontractor center, while the constraint set (6) computes the makespan of system which is based on the completion times for all the orders and the transportation time in return path. Constraint (8) ensures that the total available budget is not violated. Finally, set (9) and (10) defines the non-negative and binary variables used in the model.

4 Artificial TPA procedure

We can also find many applications of artificial intelligence techniques to manufacturing and scheduling context in literature like Mokhtari et al. [17], Vijay Chakaravarthy et al. [11], Li et al. [32], Buyukozkan and Sarucan [20], Chien et al. [7], and Shivasankarana et al. [26]. These days, the soft computing intelligent algorithms have become important tools for researchers, managers, economists, and industrialists [29 –31]. The team process algorithm (TPA) is a new evolutionary algorithm recently developed by Bo and Liu [43] in which the human’s behaviors of exploration and learning are adapted in the evolution procedure. One of the fundamentals in economics is that the labor division with the market exchange can extremely increase the social efficiency, and that human has reached the fastest evolution speed. Based on above ideas, two groups of members are generated in TPA algorithm as initialization and the performance measure is directly used to assess the abilities of members. In evolution process, the team members are divided into the elite group and the plain group according to their evaluations. In order to carry out the learning and exploration behaviors, the epitomes of each group are established as the average property of each group. For a successful global search, TPA let one group to explore more possible solutions, while for the fast convergence; another group is assigned to the local searches. To do this, the randomly local search and global search are shared by the elite group and the plain group, respectively. Additionally, the epitome-based learning mechanism enhances the directive search during algorithm. Thus, an efficient computational based algorithm with the potential of global, local and directional search is developed for solving complex optimization problems.

4.1 General structure

In general form, TPA is useable for a particular set of optimization problems with bounded variables x ∈ [a, b] and minimization objective f (x), where x = (x₁, x₂, …, x_n) ^T, [a, b] : = {a_i ≤ x_i ≤ b_i ; i = 1, 2, …, n} and a specific vector of x indicates an individual or a member with the properties of x_i and the function value f (x) is regarded as the evaluation of the member x. The problem is to seek the best member with the minimal function value by means of behavior division between the elite group and the plain group, inherited generation of new individual from one of the groups, and the replacement rules of the group members. In order to accomplish the task, N + M individuals are randomly produced and initially divided into the elite and the plain groups according to their evaluations. The best N individuals are selected to establish the elite group {x_e1, x_{e
₂}, …, x_eN} and others form the plan group {x_p1, x_p2, …, x_pN}. The elements of an elitist and a plain member are denoted by x_eji and x_pji respectively. The objective is to find the best elitist can be achieved through solution updating and replacement rules. Li and Chen [44] reported a successful application of TPA for solving a job-shop scheduling problem with makespan minimization. According to their results, TPA has the properties of simple implementation, high rate of global optimization and fast convergence.

4.2 Solution representation form

Solution representation is a procedure to make a solution recognizable for an evolutionary algorithm. It was recently mentioned that a proper encoding scheme plays a key role in maintaining the search-effectiveness of any algorithm. One of the most extensively used encoding schemes in scheduling context is random keys (RK). Random key representation was proposed by Norman and Bean [5] for an identical multiple machines problem. In a RK each job is assigned a real number whose integer part is the machine number to which the job is assigned and whose fractional part is used to sort the jobs assigned to each machine. Our purpose to represent the solutions by these RK is to make our encoding scheme easily adjustable to the algorithm. For example, consider a problem with eight jobs (n = 8), two machines (m = 2) and two subcontractors (p = 2). For this problem we should generate 8 random numbers from a uniform distribution on interval (1, 1 + m + p). According to the RKs method, jobs {J₈, J₄, J₁} are assigned to machine m₁; jobs {J₅, J₇} are assigned to machine m₂; job J₃ is assigned to subcontractor S₁; also jobs {J₂, J₆} are assigned to subcontractor S₂.

4.3 Artificial operators: Learning and exploration

As mentioned above, it is necessary for each new individual to select one of the learning or exploration operators to become a candidate member which is determined by a random binary number s. Before defining the learning behavior, it is needed to determine the elite epitome e_e and plain epitome e_p as the average property values of each group as follows. $e_{s} = \frac{1}{N} \sum_{j = 1}^{N} x_{sj} for s = e, p$ (11)

The learning behavior as a TPA operator means that new individual x_r moves towards the e_e or away from e_p in order to reach the new candidate solution x_c with the better performance. After that the group epitomes are calculated, the learning operation can be started. If the new individual x_r born from the plain group, the learning operation should be carry out in such a way that x_r is moved towards the elite epitome as follows. $x_{c} = (1 - γ) x_{r} γ - γ e_{e},$ (12) where γ is a random number between 0 and 1. On the other hand, if x_r comes from the elite group, the learning operation is performed to move along the direction away from the plain epitome to reach the candidate solution x_c as follows. $x_{c} = (1 - γ) x_{r} γ - γ e_{p}$ (13)

The procedure of learning operations is depicted in Fig. 1.

When the random number r > l, exploration operator is selected by new individual x_r to become a candidate solution x_c = (x_c1, x_c2, …, x_cn) ^T. In this operator, the candidate solution x_c is obtained by the following equation.

$x_{ci} = {\begin{matrix} x_{ri} + t_{e, p} (b_{i} - x_{ri}) for m_{i} = 0 \\ x_{ri} - t_{e, p} (x_{ri} - a_{i}) for m_{i} = 1 \end{matrix}$ (14) where $t_{e, p} = 1 - γ_{i}^{{(1 - \frac{k_{e}}{K})}^{α_{e, p}}}$ (15) and a_i and b_i are the maximum and minimum limits of variables x_i which in RK representation are 1 and p + 2 respectively. K indicates the maximum iteration threshold of algorithm, k_e shows number of iterations for exploration operator, t_e and t_p represent strength factor corresponding to strength digression exponents α_e and α_p respectively, γ_i is a random number between 0 and 1 used to update the property i and m_i is a binary random parameter. Figure 2 shows the steps of exploration operator.

4.4 Solution evaluation

In order to assess the effectiveness of TPA, each individual is assigned a fitness value which helps the TPA algorithm to direct the search process towards an area with greater probability for finding better solutions. The higher amount of fitness represents the better quality of solutions and vice versa. In this regard, we calculate the value of our objective function, i.e. makespan, as fitness value for each candidate solution. Furthermore, the solutions which violate the budge constraint, are penalized with an amount of excess objective.

4.5 Local search by NSA

In order to make full use of the information of the candidate solution x_c, local search procedure is used after the TPA operations. The local search adapted in this paper is based on neighborhood search algorithm (NSA), in which three commonly used neighborhood strategies are considered separately. The first strategy Sw₁ is applied to the candidate solution x_c and performed in the following way: randomly choose a jobJ_r ∈ J, randomly choose another jobJ_t ∈ {J|t ≠ r} and then exchange the RK of J_r and J_t in x_c. The second strategy Sw₂ is based on adjacent pairwise interchange in which a pair of adjacent jobs is selected and then their RKs are interchanged. In Sw₂, a job number r ≤ (n - 1) is chosen at random and then the RK of J_r and J_r+1 is exchanged to reach an enhanced x_c. The third strategy Sw₃ is similar, but it considers three successive jobs instead of a pair of jobs in Sw₁ and an adjacent pair of jobs in Sw₂. In this strategy, all possible permutations of these three jobs are then analyzed, and the best configuration is selected. A job number r ≤ (n - 2)is chosen at random and then the RK of J_r, J_r+1 and J_r+2 is exchanged repeatedly to reach an enhanced x_c. The procedure of NSA for a pre-known neighborhood strategy Sw₁ is depicted in Fig. 3.

4.6 Solution updating

In order to simultaneously enhance the search intensification and diversification, TPA allocate one group to explore more possible solutions in different search areas and another group to local search for fast convergence. In this regard, designing a strategy for population updating is necessary for behavior division between two groups. As it is obvious from definition of elite and plain groups, the worst member in elite group is better than any other members in plain group. In order to prevent the assimilation may be occurred in plain group, it is a reasonable strategy to eliminate the worst member in elite group rather than enter it to plain group, if it is replaced by a candidate solution. If the candidate is just poorer than the last elitist but better than the worst member in the team, the operation taken by the candidate solution must be checked to determine whether the candidate can enter to the plain group. On the other hand, if the selected operation is exploration, the obtained candidate can replace with the last member. Otherwise, the candidate is discarded in order to avoid the assimilation of the plain group.

4.7 Restart mechanism

A major drawback in optimization process by evolutionary algorithms is occurrence of premature convergence may leads to a fast termination of algorithm while the diversity is lost within short time. To address this problem, some restart mechanisms can be incorporated in the main algorithm. When C_max of all solutions in the population (elite and plain group) is identical, a restart scheme can be adapted to renew the population and prevent premature convergence. The procedure of applied restart mechanism is shown in Fig. 4.

According to the adapted operators, population updating rules, local search procedure and restart mechanism described above, the proposed solution algorithm is shown in Fig. 5.

As can be seen, an overall picture of procedure is presented in Fig. 5. As shown by this figure, initial parameters like member numbers N and M of two groups, learning probability, contraction exponents, and the search accuracy are set at the initialization stage. Then evaluation of members will be done by using the objective function to determine the overall best member x_opt, the overall last member x_wst and the last elitist x_ewst. Afterwards, the search process is commenced till the termination criterion, f (x_opt) < δ or number of iterations K, is violated. At first stage of search process, elite or plain group is selected by random binary number s. Then by using a random real number r, a new candidate solution x_c will be produced by learning or exploration operator. The local search is implemented to improve candidate solution x_c at this stage. Considering new solution, the members will be updated. At the last stage of one iteration of search, a restart mechanism is implemented to renew the population and prevent premature convergence.

5 List scheduling heuristic

In this section, we present a comparison metric will be used for investigating the performance of TPA algorithm. A reliable dispatching mechanism from the parallel machine scheduling literature is the list scheduling (LS) heuristic. Although optimal solutions to the makespan problems are difficult to obtain, some LS heuristic procedures perform quite well. The procedure of basic LS can be described as follows. First, LS constructs a list of the jobs, in some order. Then, it removes the first job from the list and places it in the schedule as early as possible. Next, LS repeats this step without changing the existing partial schedule, each time removing the first job on the list and placing it in the schedule to start at the earliest possible time. As some job finishes and its machine become free, the first job in the queue gets assigned to the free machine. In order to adapt the LS to the addressed problem in this paper, we should incorporate the processing option of subcontractors and also transportation delay between manufacturer and subcontractors into the traditional LS. To this end, the shortest processing time (SPT) rule is considered to determine the priorities of jobs at first, and then the earliest available resource (among in-house machines and subcontractors) is chosen to process the first job in queue. When the available outsourcing budget is consumed, all the subcontractors are discarded to be assigned any further job.

6 Experiments and comparisons

To evaluate the performance of TPA and demonstrate its advantage over the LS heuristic in practice, we consider a real-world application in commercial printing industry. Printing is a manufacturing process for reproducing text and image, typically with ink on paper. It is an essential stage of publishing and has a great contribution in GDP of countries. The production scheduling in printing industry can be divided into three major stages: (1) prepress, in which operations encompass that series of steps during which the idea for a printed image is converted into an image carrier such as a plate or screen. Prepress operations include composition, graphic photography, image assembly, and carrier preparation, (2) press, which refers to actual printing operations, and (3) postpress, which involves the assembly of printed materials and consists of binding and finishing operations. Postpress operations include cutting, folding, assembling, and binding.

In order to adapt the model developed in this paper for printing industry, this paper is focused on the second of these functions, i.e. press. We consider two cases with one and multiple identical in-house machines, each of which include several suppliers to handle the outsourced orders. The first case consists of 15 jobs (n = 15), one in-house machine (m = 1),2 outside suppliers (p = 2) with no transportation delay and 2200 units of currency total available budget. Data related to the orders received at the beginning of planning horizon of first case is presented in Table 1.

To assess the performance of TPA, we implement the procedure in MATLAB 2008a environment on a PC with 2.81 GHz Intel and 1 GB of RAM memory. Also to show the competitiveness of the proposed algorithm, we do comparison on it against a well-known heuristic i.e. List Scheduling. The schedule related to the first case is shown by Fig. 6. Note that, Processor 1 and 2 represent first and second supplier respectively, and Processor 3 shows the in-house machine.

According to the results, the maximum completion time for all the jobs is equal to 110 which represents the makespan of system and is a measure of quality of obtained solution. Furthermore the amount of cost incurred from outsourced jobs is computed 1450 which is less than total available budget and shows the feasibility of schedule.

To compare the results of algorithm with LS algorithm, the results of implementation of LS for the problem is depicted by Fig. 7.

As the results show, the maximum completion time of LS-based solution is 120 which concerns with job J₁₅ and the total consumed budget is 2195. As it can be seen, the results of first implementation dominates the schedule obtained by LS heuristic in terms of both makespan and total outsourcing cost. As mentioned earlier, we consider a relatively complex instance with 15 jobs (n = 15), one in-house machine (m = 3), 2 outside suppliers (p = 2). The jobs received by manufacturer in second case are same as those considered in first case. Figures 8 and 9 shows the schedule obtained by the algorithms graphically. Note that the Processors 3–5 represent the in-house machines in figures. As the results reveal, the makespan of system obtained from our algorithm is 70 which outperforms the LS heuristic with makespan 75.

In order to more investigate performance of suggested TPA, some computational experiments will be conducted in sequel. First of all, a range of test problems should be employed. Since there are no standard test problems in literature, we should generate a set of representative instances. To generate each problem, we should first delineate the data needed for these instances. These data include number of jobs (n), number of in-house machines (m), number of subcontractors (p), jobs’ processing times (p_i), jobs’ outsourcing cost, transportation times (T_s), and total available budget (M). To the end of generating problems in two classes (small and large), some levels of above mentioned parameters are considered as presented in Table 2.

To evaluate the quality of solutions gained by the proposed TPA, corresponding solutions were attained by LINGO. LINGO is a commercial optimization package which handles problems with both continuous and binary variables by using branch & bound technique. For all test problems, both TPA and LINGO results are recorded. Due to random nature of the TPA, the output results for a specific problem are unlikely same and hence 20 replications of TPA are implemented for each instances and the best solution is reported. The TPA parameters for the model are varied based on some primary experiments as follows.

Maximum number of iterations (K) :50 - 100

Population size (N + M) :100 - 140

Learning probability (l) :0.5 - 0.9

Digression exponents (α_e, α_p) :0.1 - 1

The search accuracy (δ) :0.1

The results are presented by Table 3. As results shows, the deviation for TPA from optimal solution is just 2.47 and 5.94 for small and large problems respectively, which indicate the reasonable performance of TPA with respect to the exact results. To test the performance of TPA, a performance index (PI) is introduced and reported. PI indicates average relative percentage deviation for TPA

$PI = \frac{{TPA}_{best} - LINGO}{LINGO} \times 100 %$ (16)

To further assess the performance of TPA, two famous metaheuristic algorithms, i.e., genetic algorithm (GA) and simulated annealing (SA) are employed as benchmark algorithms. Since the value of parameters have significant influence on the performance of GA and SA, the appropriate value of parameters used throughput of GA and SA are obtained based on some primary experiments as presented in Table 4. Moreover, the swap and reverse are used as operators and neighborhood mechanisms in GA and SA. The swap chooses two RKs at random, and then replaced them, and reverse arranges the numbers between two randomly selected RKs in reverse order. The termination criteria is same as TPA. To gain more reliable results, 20 replications are considered for each test problem. The results are presented in Table 5.

As it is obvious from results, the TPA outperforms both GA and SA with average makespan 353.05 as opposed to 381.25 and 355.95 obtained by GA and SA. SA uses a worst solution acceptance rate pwhich helps it to avoid trapping into local optimum. Hence it shows better performance than GA and its performance is close to TPA. A reason for appropriate performance of TPA is that it exploits advantages of NSA as a good local search. In order to demonstrate the performance of algorithms in comparative study, the results of comparisons are depicted by Figs. 10 and 11 for best and worst solutions separately. As can be seen, the results are summarized as average values within a specific number of job J = {5, 15, 30, 60}. As it is clear from figures, the proposed TPA gained the better solution than both GA and SA in both best and worst measures for all sizes of problems. Moreover, between GA and SA, as it is revealed by figures, the quality of solutions attained by SA is better than that of GA in average. As advantages of TPA, the TPA lets one group (elite) explore more global spaces for a successful global search, while, for fast convergence, another group (plain) is assigned to local search. Moreover, the epitome-based learning mechanism enhances the directive search during the iterations of algorithm. Hence, the TPA is an efficient computational-based algorithm with the potential of global, local and directive searches for solving complex optimization problems. In other words, using the inherited generation of new individual and the replacement rules, the behavior division between the elite and plain groups was implemented, which make the algorithm have the potential for the local and global search. As another advantage of TPA is that the number of parameters is relatively low to be set. However, despite of its appealing advantages, like to many other metaheuristics, there is no guarantee that the best solution found by TPA will be the optimal solution.

The change in the amount of parameters, in any decision-making process, is inevitable due to uncertainties existing in real-world situation. Sensitivity analysis is the process of studying how different factors of uncertainty in inputs of a system can affect the output values obtained. In order to assess the severity of these changes, the sensitivity analysis will be helpful in a decision-making process. Therefore, here, we aim to carry out the sensitivity analysis of various parameters the numerical example discussed in the section (10 × 2 ×2). The results of analysis are presented in Table 6.

As another analysis, in order to assess the efficiency of proposed TPA, we investigate the (i) convergence and (ii) CPU running time of experiments for different size of problems. For convergence analysis, the obtained results are depicted by Figs. 12–17. The results show the steady convergence of proposed TPA during iterations.

In addition to above analysis, Table 7 shows some other useful performance criteria for algorithms. The numerical example used in previous sections, is also utilized for this analysis. As first criterion, the robustness is an important measure for assessing the reliability of random search techniques. To assess the robustness, the best and worst solutions obtained in 20 replications of algorithm are considered and the difference between then are reported. The feasibility of solutions is another criteria usually considered in analyzing the performance of algorithms. Moreover, convergence ability of algorithms is another main characteristics. Finally, the run time which is an efficiency performance measure is reported for three algorithms in average.

7 Concluding remarks

In this paper, we designed and analyzed an improved TPA for solving a case of parallel machine manufacturing when the outsourcing of received jobs is allowed. Each job can be either planned for in-house production or outsourced to a remote outside subcontractor. The optimization criterion was the minimization of the maximum completion time subject to a predefined value of outsourcing budget. We first formulated the problem by a mathematical mixed integer model. Due to the complexity of problem, the mathematical model is not an efficient solution strategy for large-scale problems and so we presented an effective metaheuristic algorithm based on team process algorithm which is a computational optimal-seeking technique. This algorithm is based on the human’s behaviors of exploration and learning with mimicry of a two-group team (elite and plain) for a specific objective. The operations of exploration and epitome-based learning are defined as TPA artificial operators. Using the inherited generation of new individual and the replacement rules, the behavior division between the elite and plain groups was implemented, which make the algorithm have the potential for the local and global search. In addition, in order to further improve the quality of candidate solutions, a neighborhood search algorithm (NSA) with three neighborhood structures was devised and embedded to the main TPA as a local search. Furthermore, to prevent the premature convergence of algorithm, some restart mechanisms was also incorporated in the main algorithm. As a comparison metric, list scheduling (LS) algorithm, which is a simple but efficient heuristic method for solving pure parallel machine scheduling, was also adapted for the addressed problem. Moreover a GA and a SA are also adapted. In order to assess the performance of algorithms, two instances from commercial printing industry are applied and the comparison results showed that proposed algorithm outperforms other methods. Moreover, a computational study was conducted based on comparisons between solutions obtained by LINGO and TPA, and the results revealed good performance of suggested TPA.

References

Allahverdi

, Ng

, Cheng

and Kovalyov

, A survey of scheduling problems with setup times or costs, European Journal of Operational Research187 (2008), 985–1032.

Hariri

and Potts

, Heuristics for scheduling unrelated parallel-machines, Computers and Operations Research18 (1991), 323–331.

Ruiz-Torres

A.J.

, Ho

J.C.

and Lopez

F.J.

, Generating Pareto schedules with outsource and internal parallel resources, International Journal of Production Economics103 (2006), 810–825.

Ruiz-Torres

A.J.

, Lopez

F.J.

, Ho

J.C.

and Wojciechowski

P.J.

, Minimizing the average tardiness: The case of outsource machines, International Journal of Production Research46 (2008), 3615–3640.

Norman

B.A.

and Bean

J.C.

, A genetic algorithm methodology for complex scheduling problems, Naval Research Logistics46 (1999), 199–211.

Hsu

C.C.

, Liou

J.J.H.

and Chuang

Y.C.

, Integrating DANP and modified grey relation theory for the selection of an outsourcing provider, Expert Systems with Applications40 (2013), 2297–2304.

Chien

C.F.

, Diaz

A.C.

and Lan

Y.B.

, A data mining approach for analyzing semiconductor MES and FDC data to enhance overall usage effectiveness (OUE), International Journal of Computational Intelligence Systems7 (2014), 52–65.

Samantra

, Datta

and Mahapatra

S.S.

, Risk assessment in IT outsourcing using fuzzy decision-making approach: An Indian perspective, Expert Systems with Applications41 (2015), 4010–4022.

D.F.

and Wan

S.P.

, Fuzzy heterogeneous multiattribute decision making method for outsourcing provider selection, Expert Systems with Applications41 (2014), 3047–3059.

10.

Teymourian

, Kayvanfar

, Komaki

GH.M.

and Khodarahmian

, An enhanced intelligent water drops algorithm for scheduling of an agile manufacturing system,, International Journal of Information Technology & Decision Making (2016). In Press, DOI: 10.1142/S0219622016500024

11.

Vijay Chakaravarthy

, Marimuthu

and Naveen Sait

, Comparison of firefly algorithm and artificial immune system algorithm for lot streaming in m-machine flow shop scheduling, International Journal of Computational Intelligence Systems5 (2012), 1184–1199.

12.

Mokhtari

and Salmasnia

, An evolutionary clustering based optimization to minimize total weighted completion time variance in a multiple machine manufacturing system, International Journal of Information Technology & Decision Making14 (2015a), 971–991.

13.

Mokhtari

and Salmasnia

, A monte carlo simulation based chaotic differential evolution algorithm for scheduling a stochastic parallel processor system), Expert Systems with Applications42 (2015b), 7132–7147.

14.

Mokhtari

, A nature inspired intelligent water drops evolutionary algorithm for parallel processor scheduling with rejection, Applied Soft Computing26 (2015), 166–179.

15.

Mokhtari

and Nakhai Kamal Abadi

, Scheduling with an outsourcing option on both manufacturer and subcontractors, Computers & Operations Research40 (2013), 1234–1242.

16.

Mokhtari

and Nakhai Kamal Abadi

and Amin-Naseri

M.R.

, Production scheduling with outsourcing scenarios: A mixed integer programming and efficient solution procedure), International Journal of Production Research502 (2012a), 5372–5395.

17.

Mokhtari

, Mozdgir

and Nakhai Kamal Abadi

, A reliability/availability approach to joint production and maintenance scheduling with multiple preventive maintenance services), International Journal of Production Research50 (2012b), 5906–5925.

18.

Lee

I.S.

and Sung

C.S.

, Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed,a), European Journal of Operational Research186 (2008), 931–952.

19.

Lee

I.S.

and Sung

C.S.

, Single machine scheduling with outsourcing allowed,b), International Journal of Production Economics111 (2008), 623–634.

20.

Buyukozkan

and Sarucan

, Applicability of artificial bee colony algorithm for nurse scheduling problems, International Journal of Computational Intelligence Systems7 (2014), 121–136.

21.

Ying

K.C.

and Cheng

H.M.

, Dynamic parallel machine scheduling with sequence-dependent setup times using an iterated greedy heuristic, Expert Systems with Applications37 (2010), 2848–2852.

22.

Moghaddam

K.S.

, Fuzzy multi-objective model for supplier selection and order allocation in reverse logistics systems under supply and demand uncertainty, Expert Systems with Applications42 (2015), 6237–6254.

23.

Rocha de Paula

, Gómez-Ravetti

, Robson-Mateus

and Pardalos

, Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighborhood search. IMA, Journal of Management Mathematics18 (2007), 101–115.

24.

Weng

, Lu

and Ren

, Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective, International Journal of Production Economics70 (2001), 215–226.

25.

Mishra

, Choudhar

A.K.

and Tiwari

M.K.

, Modeling the planning and scheduling across the outsourcing supply chain: A Chaos-based fast Tabu–SA approach, International Journal of Production Research46 (2008), 3683–3715.

26.

Shivasankarana

, Senthil Kumar

and Venkatesh Raja

, Hybrid sorting immune simulated annealing algorithm for flexible job shop scheduling, International Journal of Computational Intelligence Systems8 (2015), 455–466.

27.

Ibbara

and Kim

, Heuristic algorithms for scheduling independent tasks of nonidentical processors, Journal of the Association for Computing Machinery24 (1977), 280–289.

28.

Schuurman

and Woeginger

, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Journal of Scheduling2 (1999), 203–213.

29.

Vasant

P.M.

, Meta-Heuristics Optimization Algorithms in Engineering, Business, Economics, and Finance. Hershey, PA: IGI Global, 2013, pp. 1–734. http://dx.doi.org/10.4018/978-1-4666-2086-5.

30.

Vasant

P.M.

, Handbook of Research on Novel Soft Computing Intelligent Algorithms: Theory and Practical Applications (2 Volumes). Hershey, PA: IGI Global, 2014, pp. 1–1018. http://dx.doi.org/10.4018/978-1-4666-4450-2.

31.

Vasant

P.M.

, Handbook of Research on Artificial Intelligence Techniques and Algorithms (2 Volumes). Hershey, PA: IGI Global, 2015, pp. 1–796. http://dx.doi.org/10.4018/978-1-4666-7258-1.

32.

, Dou

, Chen

and Nan

, A QoS-oriented Web service composition approach based on multi-population genetic algorithm for Internet of things, International Journal of Computational Intelligence Systems7 (2014), 26–34.

33.

Logendran

, McDonell

and Smucker

, Scheduling unrelated parallel machines with sequence-dependent setups, Computers & Operations Research34 (2007), 3420–3438.

34.

McIvor

, The influence of capability considerations on the outsourcing decision: The case of a manufacturing company, International Journal of Production Research48 (2010), 5031–5052.

35.

Balin

, Non-identical parallel machine scheduling using genetic algorithm, Expert Systems with Applications38 (2011), 6814–6821.

36.

Fahed Alkhatib

, Darlington

, Yang

and Thanh Nguyen

, A novel technique for evaluating and selecting logistics service providers based on the logistics resource view, Expert Systems with Applications42 (2015), 6976–6989.

37.

Kumar

, Zampogna

and Nansen

, A closed loop outsourcing decision model for developing effective manufacturing strategy, International Journal of Production Research48 (2010), 1873–1900.

38.

Martello

, Soumis

and Toth

, Exact and approximation algorithm for makespan minimization on unrelated parallel-machines, Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science75 (1997), 169–188.

39.

Cai

, Lee

C.Y.

and Vairaktarakis

G.L.

, Optimization of processing and delivery decisions involving third-party machines, Nonlinear Analysis63 (2005), 2269–2278.

40.

, Coordinated logistics scheduling for in-house production and outsourcing, IEEE Transactions on Automation Science and Engineering5 (2008), 188–192.

41.

, Two-stage production scheduling with an option of outsourcing from a remote supplier, Journal of Systems Science and Systems Engineering18 (2009), 1–15.

42.

, Outsourcing and production scheduling for a two-stage flow shop, International Journal of Production Economics129 (2011), 43–50.

43.

and Liu

, An Epitome-Based Evolutionary Algorithm with Behavior Division for Multimodal Optimizations. ICNNSP, (2008), pp. 406–411.

44.

, Chen

, An effective TPA-based algorithm for job-shop scheduling problem, Expert Systems with Applications38 (2011), 2913–2918.

45.

Chen

Z.L.

and Li

C.L.

, Scheduling with subcontracting options, IIE Transactions40 (2008), 1171–1184.