Scheduling multiple servers to facilitate just-in-time part-supply in automobile assembly lines

Tao Peng (School of Mechanical Engineering, Tongji University, Shanghai, China)
Binghai Zhou (School of Mechanical Engineering, Tongji University, Shanghai, China)

Assembly Automation

ISSN: 0144-5154

Publication date: 6 August 2018

Abstract

Purpose

With regard to product variety and cost competition, just-in-time (JIT) part-supply has become a critical issue in automobile assembly lines (AALs). This paper aims to investigate a multiple server scheduling problem (MSSP) encountered in the JIT part-supply process of AALs. Parts are stored in boxes and allotted from the JIT-supermarket to consumptive stations with a multiple server system. The schedule is to dispatch and sequence material boxes on each server for minimizing line-side inventory levels.

Design/methodology/approach

A mixed integer linear programming (MILP) model is established to formulate the proposed MSSP to pave the way for CPLEX procedure. Considering the high complexity of MSSP, a hybrid ant colony optimization (HACO) approach is developed by integrating basic ant colony optimization (ACO) with local optimizers that comprise of a fast local search and a tailored breadth-first tree search method.

Findings

Both CPLEX and HACO approach are capable of solving small-scale instances to optimality within reasonable computation time. The proposed HACO has been well enhanced with the embedded fast local search and tailored breadth-first tree search, and it performs robustly in a statistically significant manner when applied to real-world scale instances.

Originality/value

No stock-outs constraints and weighted line-side inventory level are considered in this paper, and the MSSP is solved satisfactorily to facilitate an efficient JIT part-supply of the AAL. In terms of the algorithm design, a tree search-based local optimizer is embedded into ACO to combine the mechanisms of ACO and problem-specific optimization.

Keywords

Citation

Peng, T. and Zhou, B. (2018), "Scheduling multiple servers to facilitate just-in-time part-supply in automobile assembly lines", Assembly Automation, Vol. 38 No. 3, pp. 347-360. https://doi.org/10.1108/AA-08-2017-102

Download as .RIS

Publisher

:

Emerald Publishing Limited

Copyright © 2018, Emerald Publishing Limited


1. Introduction

The ongoing customization has enforced auto manufacturers to extensively adopt mixed-model assembly lines (MMALs) for the automobile assembly industry (Kamal Uddin et al., 2010). In the meantime, the in-plant logistic scheduling problem has turned into a critical issue of these high-variant MMALs (Kilic and Durmusoglu, 2015). Enormous amount and diversities of parts have to be delivered to consumptive stations in a just-in-time (JIT) manner to ensure the efficiency of the part-supply processes, i.e. stock-outs and the overflow of line-side inventories are prohibited.

In such contexts, an increasing number of enterprises begin to adopt the so-called “supermarket concept” to provide a reliable and flexible in-house logistics process for MMALs (Battini et al., 2012; Alnahhal and Noche, 2015). The core of this application is to avoid unforeseen events through frequent small-lot deliveries. All required parts are first received at the central store and then transported to the decentralized JIT-supermarket, which is an intermediate storage area for parts required by nearby line segments. Parts allocated to a supermarket are re-packaged into smaller boxes and then delivered to assigned stations by multiple servers. Such an application is able to coordinate the part-supply with time-varying demands of the final assembly line (Boysen and Emde, 2014).

This article is motivated by this context and aims to deal with the in-time delivery of parts from the JIT-supermarket to the consumptive stations. Figure 1 provides a detailed description of current problem setting where a multiple server system takes charge of the distribution task. In the supermarket, each material box contains a predefined number of parts for a specific station. One material box is picked up by a server and then transported to the specified station within each delivery. Upon arriving at the station, the server returns to supermarket and immediately fetches another box for the next delivery. The proposed multiple server scheduling problem (MSSP) is to dispatch the material boxes to the servers and sequence the boxes on each server.

Each delivery leads to a release of a predefined number of part units into the line-side inventory at the specified station. Meanwhile, the consumption of line-side stock is triggered by predetermined time-varying demand of the automobile assembly line (AAL). Thus, it is extremely complicated to schedule multiple servers to facilitate JIT part-supply of AAL. This can be explained from the following two aspects. On one hand, stock-outs are not allowed; otherwise it would be extremely costly because of the resulting line-stoppages (Battini et al., 2015). On the other hand, the space at assembly stations is extremely scarce and excessive line-side inventory would incur high holding cost and impede assembly operations (Emde, 2017). To ensure the efficiency of the part-supply processes, the current research aims to minimize the line-side inventory in all stations during the planning horizon.

The remainder of this research is organized as follows. Section 2 presents a brief literature review. Section 3 provides a detailed problem description and formulates the proposed MSSP using mixed integer linear programming (MILP). Section 4 develops hybrid ant colony optimization (HACO) procedure by integrating ACO with a fast local search and a breadth-first tree search method. Computational experiments are designed in Section 5 to confirm the efficiency and effectiveness of MILP formulation and HACO approach. Finally, conclusions and further research work are discussed in Section 6.

2. Literature review

Existing literatures associated with AALs have mainly investigated the line balancing and car-sequencing problems (Merengo et al., 1999). Boysen et al. (2007, 2009) provided extraordinary surveys about extensive mathematical models and methodologies in these two respects. In the meantime, the design of part feeding system is of great significance to AALs, as an efficient part feeding system is capable of improving the performance of the coupled AAL. For recent and comprehensive studies about the design of part feeding system, please refer to excellent works presented by Faccio et al. (2013) and Caputo et al. (2015). In relation to the proposed MSSP, the aforementioned three problems are assumed to be solved. Therefore, the configuration of the multiple server system and the time-varying demand of the AAL could be determined with certainty.

The proposed MSSP in this article is an extension of the research originally presented by Boysen and Bock (2011). The original version investigated a hoist scheduling problem (HSP) where a number of material boxes with parts required JIT distribution to consumptive stations by one hoist. The schedule was to determine the best delivery sequence of boxes with minimization of line-side inventory. The authors established an exact dynamic programming and an improved simulated annealing (SA) algorithm for HSP. The proposed MSSP in current research is a complex variant of HSP with multiple transportation devices, where the assignment and sequence of boxes on each server have to be determined. According to the complexity analysis by Boysen et al. (2013), the proposed MSSP is still NP-hard in the strong sense.

Meanwhile, similar JIT part-supply problems of AAL have been investigated in recent years. Rao et al. (2013) studied the combined loading and scheduling problem of a single vehicle. One destination station was assumed to be included within each delivery, and the solution was to determine the destination station, part quantity and departure time of each delivery. The authors aimed to minimize traveling and holding costs by introducing an exact backward-backtracking approach and a hybrid genetic algorithm (GA). Zhou and Peng (2017) addressed an analogous in-house logistics distribution problem of AALs, where a point-to-point part-supply model was formulated to specify the destination station and part quantity within each delivery. To optimize line-side inventory with no stock-outs constraints, an exact backtracking procedure and a modified discrete artificial bee colony metaheuristic were developed for solution methodology.

Moreover, considerable efforts have been made to tackle the JIT milk-run part-supply problems for AALs, which would provide some enlightenment for the proposed MSSP. Emde et al. (2012) formulated the tow train loading problem for decreasing the line-side stocks at stations. An exact procedure, which requires a polynomial increase in computing time, was proposed for the solution methodology. Fathi et al. (2014a, 2014b, 2015) addressed the combined delivery scheduling and loading problem of the milk-run part-supply scheduling for AALs under three different problem settings. Considering the NP-hardness nature, the authors presented three metaheuristic methodologies for the solution procedure, including a novel SA, a memetic ACO-based heuristic and a hybrid particle swarm optimization (HPSO). The effectiveness of the proposed algorithms has been efficiently validated through the comparison of the results obtained from metaheuristics and CPLEX.

According to the above discussion, those wonderful research studies have provided a beneficial reference to some scheduling problems encountered when facilitating JIT part-supply for AALs. To the best of our knowledge, little was published on the JIT part-supply scheduling problem with multiple servers. In current study, an attempt is made to deal with such an issue.

It should be noticed that the proposed MSSP is closely related to the well-known parallel machines scheduling (PMS) when the delivery of each material box and the server are interpreted as a job and a machine (or processor), respectively. The relevant scheduling models have been widely investigated to optimize certain objective functions in terms of job completion times, power cost, etc. (Biskup et al., 2008; Fang and Lin, 2013). However, there exists three major differences between the proposed MSSP and PMS. First, the goal of MSSP is to minimize the line-side inventory levels instead of the objectives related to job completion times in PMS. Second, stock-outs of AALs are not allowed in MSSP. However, the job tardiness is permitted in most cases when solving PMS problems. Third, the delivery time of each material box depends mainly on its destination station in MSSP while the job processing time in PMS is determined by the nature of job and machine.

As for solution methodologies, many efforts have been made to tackle MSSP and analogous problems. Because of the NP-hardness nature, some exact algorithms have been presented to solve small-scale problems to optimality, including dynamic programming (Doğramaci, 1984) and branch and bound-related methods (Elmaghraby and Park, 1974; Azizoglu and Kirca, 1998; Tanaka and Araki, 2008). However, the computational efforts required these exact algorithms imply a non-polynomial growth with increasing problem scales. In the meantime, the applications of exact methods are limited to special problem settings in most cases. Therefore, a great number of heuristic rules have been developed to obtain quick solutions with less computational efforts. Dogramaci and Surkis (1979) designed a list-algorithm-based heuristic method for PMS. Baker and Scudder (1990) proposed a heuristic based on neighborhood search to optimize earliness and tardiness penalties. Ho and Chang (1991) developed a dispatching rule noted traffic priority index that consisted of well-known shortest processing time (SPT) and earliest due dates rules. Recently, several other excellent works have also presented different heuristics for tackling similar problems (Beraldi et al., 2008; Ou et al., 2015). As the solution quality obtained by heuristic rules is far away from optima, many metaheuristics have been proposed recently to obtained approximate optimal solutions with less computational time owing to the development of evolutionary algorithms. Bean (1994) adopted GA to PMS with a specified representation technique named random keys, and Koulamas (1997) developed a hybrid approach for PMS-based SA. Kim and Shin (2003) established a restricted tabu search for PMS with consideration of release times, setup times and due dates. To minimize tardiness penalty and power cost, Fang and Lin (2013) presented a novel PSO for PMS with consideration of controllable processing speeds.

This paper presents a hybrid ACO procedure to solve the proposed MSSP. ACO is a constructive metaheuristic for complicated combination optimization problems (COPs) (Meuleau and Dorigo, 2002). This algorithm is inspired by the pheromone trail laying and following behaviors of real ants, which uses the pheromones as a communication medium. Initially, the algorithm was applied to find an optimal path in a graph. In the past decades, the ACO metaheuristic has been applied successfully to solve many hard COPs, including vehicle routing (Pedemonte et al., 2011), assignment (Lee et al., 2002) and machine scheduling problem (Raghavan and Venkataramana, 2009). Experimental results of these research studies have validated the feasibility and effectiveness of ACO. Meanwhile, the ACO method is able to reach optimum performance when incorporated with some local search techniques (Dorigo et al., 2006). Consequently, the current research presents a hybrid ACO approach with a fast local search method and tailored a breadth-first tree search method to further enhance the exploitation capability of basic ACO.

3. Problem description and model formulation

3.1 Problem description

In the current problem setting, all required parts are packed into material boxes that are temporarily stored at the supermarket. One material box is selected and then delivered to the specified station by a server within each delivery. The proposed MSSP is to dispatch and sequence material boxes on all servers. Other situations considered in the proposed MSSP are summarized as follows:

  • For simplicity sake, it is assumed that the assembly operations at each station only contain a single category of part, and each material box contains a predefined number of parts for a specific station. Consequently, each kind of part and material box could be unambiguously assigned to a specified station.

  • The time unit of the in-plant logistics system is normalized to the equidistant length of a work cycle, i.e. the timespan between entries of two continuous workpiece into one station.

  • The assembly sequence is predetermined, and the exact demands of parts at each station during the planning horizon could be known with certainty.

  • All material boxes and servers are available at initial state (time zero). Meanwhile, no idle time is allowed between any two consecutive deliveries on a server.

  • The travelling time between the JIT-supermarket and a station is predefined, and the elapsed time for picking up (or dropping) a box is short and not considered.

  • The parts in a material box are available for assembly operations upon the arrival of the box, and the part consumption at each workstation is immediate.

  • Because of the costly line-stoppages, stock-outs are not allowed in the proposed MSSP.

According to the above descriptions, the proposed MSSP could be formally described as follows. Suppose there is a set N = {1,2,⋯,n} of n material boxes to be scheduled on m identical servers for feeding S assembly stations. At initial state, the inventory at station s is given by as0. Each box (indexed i) contains a predefined number (ai) of parts for a specified station (si), and the processing (i.e. delivery activity) for a box leads to a releasing of ai parts into the lineside inventory at station si. The delivery time pi for box i is given by pi = 2 ⋅ bsi, where bsi defines the traveling time between the JIT-supermarket and station si. Consumption at each station is triggered by the time-varying demand of the assembly operations, that is, the planning horizon is divided into T production cycles, and notation Ds,t defines the cumulative parts at station s up to cycle t. Moreover, all material boxes and servers are ready at time zero, and preemption, division and cancelation of each delivery are forbidden in the current research.

With above definitions and developments, the schedule of MSSP is to find schedules of all boxes on all servers σ = {σj|jM}, where σj represents the sequence of boxes allocated to server j. The arrival time of box i [Ai(σ)] to its destination station could be determined by equation Ai(σ)=Ci(σ)pi2, where Ci(σ) defines the delivery completion time of the box i in schedule σ. Then, the resulting inventory level at station s in cycle t could be known with certainty. With the given weighted coefficients ωs related to the inventory level at station s, this research aims to find the optimal schedule that minimizes the maximum weighted inventory level per station (s = 1,2,⋯,S) and production cycle (t = 1,2,⋯,T), that is Minmaxs=1,2,,S;t=1,2,,T{ωsLs,t}.

3.2 Mixed integer linear programming formulation

This subsection formulates the proposed MSSP as a MILP model to pave the way for CPLEX procedure. Table I defines the notations, and the MILP model is presented subsequently.

Objective function:

Minimize Z

Constraints:

(1) h=1nyhm
(2) yh+i=1,ihnxih=1,hN
(3) i=1,ihn+1xih=1,hN
(4) Chphyh,hN
(5) ChCi+phR(1xih),i,hN,ih
(6) Ai=Cipi2,i=1,2,,n
(7) Γs,t={iN|Aiτ,si=s},s=1,2,,S;t=1,2,,T
(8) Ls,t=as0+iΓs,taiDs,t,s=1,2,,S;t=1,2,,T
(9) Ls,t0,s=1,2,,S;t=1,2,,T
(10) ZsωsLs,t,s=1,2,,S;t=1,2,,T
(11) ZZs,s=1,2,,S
(12) yh{0,1},hNxih{0,1},i,hN,ihCh0,hN

The proposed MILP model aims to minimize the maximum weighted inventory level in all stations during the planning horizon (Boysen and Bock, 2011; Zhou and Peng, 2017). This min-max objective attempts to restrict inventory peaks in whole production process, which well coincides with the JIT philosophy in the current research.

Equation (1) guarantees that at most m material boxes could be the first box on a server. Equation (2) ensures that each of the material boxes must either be preceded by some other box or start on a server. Meanwhile, equation (3) ensures that each of the material boxes must either be succeeded by another box or end on a server, and equation (4) shows that the delivery completion time for the first box of every server must be equal to or greater than its delivery time. For all of the remaining boxes h, equation (5) states that the completion time Ch must be equal to or greater than its delivery time ph plus the delivery completion time of its direct preceding box Ci. The subtraction of parameter R makes this constraint non-restrictive if box i is not the direct predecessor of box h. Moreover, equation (6) defines the arrival time of each box, and equation (7) is applied to obtain the subset of boxes that have been delivered to at station s up to cycle t. Equation (8) depicts the calculation of line-side inventory status, and no stock-outs constraint is presented in equation (9). Equations (10) and (11) are established for the calculations of min-max objective. Finally, equation (12) defines boundary values of all variables.

3.3 An illustrative example

Consider the scenario where seven material boxes (n = 7) are to be delivered to three stations by two servers (m = 2). Table II collects the demand information (Ds,t). Meanwhile, Table III defines the destination station (si) and parts amount (ai) of each material box. Traveling times between the supermarket and stations are b1 = b2 = b3 = 1, i.e. the delivery times are pi = 2(∀i). Moreover, all stations are equally weighted (ω1 = ω2 = ω3 = 1), and the initial inventories ( as0) are a10=1, a20=2 and a30=1.

Consider a solution σ = {{7,2,1,3} and {5,4,6}} where the sequence of material boxes scheduled on two servers are {7,2,1,3} and {5,4,6}. Figure 2 illustrates the resulting varying inventory level (Ls,t) at all three stations. It can be observed that the inventory status at stations 1 and 2 remains lean and at extreme low levels (i.e. max{L1,t|t = 1,⋯,8} = 3 and max{L2,t|t = 1,⋯,8} = 2) while the inventory peaks is disproportionately high at Station 3 (i.e. max{L3,t|t = 1,⋯,8} = 7). Therefore, the maximum weighted inventory level per station and production cycle (the objective function Z) amounts to 7.

4. The hybrid ant colony optimization procedure

This section develops a HACO procedure to deal with the proposed MSSP. HACO approach presented here uses a hybrid framework consisting of server selection, box selection, fast local search, breadth-first tree search and pheromone update. Figure 3 depicts the flowchart of HACO for the proposed MSSP, and detailed descriptions are presented as follows.

4.1 Solution representation and domain properties

HACO adopts multiple-level encoding for the solution representation. Each level defines the scheduled box sequence on a server. Figure 4 presents a schematic diagram of solution σ = {{5,2,1,3} and {6,4,7}} in the aforementioned example, where server 1 and server 2 takes charge of the delivery task of box sequence {5,2,1,3} and {6,4,7}, respectively.

Property 1: According to the assumptions, the line-side inventory at every station is reduced in a step-wise manner. Meanwhile, the inventory peak at a station occurs only when it is currently supplied with a material box. Thus, the objective function could be transformed into the one which focus on the weighted inventory level at the destination station of boxes when they reach the assembly line. Specifically, the modification is defined by the following equation:

Z=max{ωsiLAi,si|iN}
where the inventory level at station si in production cycle ⌈Ai⌉ has to be calculated. The application of Property 1 is capable of simplifying the calculation of objective function.

Property 2: For a complete schedule σ = {σ1,σ2,⋯,σm}, a minimum inventory level at one station (i.e. a potential material shortage) only occurs in the production cycle right before a material box reaches its specified station. For the delivery activity of box i, the corresponding potential stock-outs production cycle is defined as follows:

tiv={min{max{0,Ai1},T}ifAi=Aimin{max{0,Ai},T}otherwise

For these specific points in time and corresponding station, the resulting inventory level Ltiv,si has to be calculated. Obviously, the schedule σ is infeasible if miniN{Ltiv,si}<0 holds. Property 2 can be used to examine the no stock-outs constraint of the proposed MSSP.

Considering the no stock-outs constraints of the MSSP, a penalty value is required when evaluating schedule σ. Specifically speaking, the modified evaluation function Z͂ is given by:

Z˜=Z+αi=1nmax{Ltiv,si,0}
where notation α is a positive number that depicts the penalty cost generated by stock-outs.

A partial schedule σ = {σ1,σ2,⋯,σm} refers to the solution that some of material boxes have been assigned and scheduled to the servers. For a partial schedule σ, this research defines the stock-outs production cycle of station s as the specific time point when station s runs out of all its line-side parts. It should be noticed that notation ℓs(σ) depicts the emergency part-supply time of station s, and Property 3 gives the formulation of ℓs(σ).

Property 3: For a partial schedule σ = {σ1,σ2,⋯,σm}, the stock-outs production cycle of station s can be calculated by:

s(σ)=argmint=1,2,,T{Ds,t>(as0+kE(σ,s)ak)}
where notation Es(σ) represents the set of martial boxes that have been delivered to station s in partial schedule σ. Specifically, set Es(σ) is determined as follows:
Es(σ)={ijMσj|si=s}

4.2 Solution construction

The proposed MSSP is to assign and schedule boxes to the servers. Generally, the solution construction process is carried out in n (i.e. equal to the number of boxes) stages, and each stage includes two decisions: server selection first and then box selection. Table IV collects all the notations used in HACO.

4.2.1 Server selection

In server selection phase, a server is selected by an ant according to the state transition rule. The greediness is defined as the availability of all servers. Let qM be the favoring exploitation probability in server selection, and rand(0,1) represents an equally distributed random number generated from interval [0,1]. The state transition rule is given by:

j={argmin{cj|jM}rand(0,1)qMj˜otherwise
where notation j͂ represents a randomly selected server index through a Monte Carlo simulation. The probability distribution is calculated with the reciprocal of all servers’ makespan, and probability Pj of server j to be selected is:
Pj=1cjkM1ck,jM

According to the biased exploration, the server with a minimum makespan would be selected when rand(0,1) ≤ qM; otherwise, server j͂ would be selected in a random manner.

4.2.2 Box selection

Once server j′ is determined, the next decision is to assign a material box to this selected server. The state transition rule in this phase considers both the heuristic information and pheromone trails. First, the stock-outs production cycle [ℓs(σ)] at station s, is calculated according to Property 3. Subsequently, the heuristic information is defined by incorporating weighted SPT (WSPT) rule with minimum slack. Variable ηij, representing the heuristic information of box-server pair (i,j), is calculated as follows:

ηij=ωsimax{si(σ),cj+bsi}cj

Meanwhile, the attractiveness between the job and the selected processor plays another important role in job selection. Let σİ represent the set of unscheduled boxes. The state transition rule of box selection for the selected server j′ is defined as follows:

i={argmax{ηij(τij)β|iσ¯}rand(0,1)qNi˜otherwise

A biased exploration is applied in job selection with the probability (1 – qN) in state transition rule. Specifically, the exploitation is favored with probability qN by selecting a job i′ for the selected server j′ with maximum value of ηij (τij)β. Otherwise, the ant randomly selects a job i′ from the probability distribution formed by the probabilities Pij:

Pij={ηij(τij)βiσ¯ηij(τij)βif iσ¯0Otherwise

4.3 Fast local search

Once a complete schedule has been established, a fast local search method is presented here to improve the solution performance. The proposed local optimizer adopts three basic operators, which have been proved to be able to tackle PMS efficiently. Detailed explanations of these operators are summarized as follows, and Figure 5 provides the schematic representations:

  • Box swaps on one server: randomly choose a server j, and then randomly choose two boxes i1 and i2 from server j. Swap boxes i1 and i2.

  • Box swaps on different servers: randomly choose two servers j1 and j2, and then randomly choose two boxes, i1 from server j1 and i2 from server j2. Swap boxes i1 and i2.

  • Box insertion: randomly choose one box i and one server j, where i does not belong to j; randomly choose a valid position r in server j, and then transfer box i to j at position r.

The proposed fast local search is carried out by the stochastic combination of these three basic operators. A greedy selection is applied for the variant schedule, i.e. the solution with better evaluation between the original schedule and the variant is accepted by HACO.

4.4 Breadth-first tree search

To better adapt ACO for the proposed MSSP, this article considers the specific features of the current problem and designs a more appropriate local optimizer for ACO. Specifically, a tailored breadth-first tree search is applied by each ant when a feasible solution is obtained after the solution construction and the fast local search. To clearly explain the procedure of this local optimizer, this subsection defines a specified neighborhood structure first, and then formulates the subproblem as a sequencing problem. Subsequently, the detailed tree search descriptions are presented with applications of domain properties. Moreover, an illustrative example is presented to explain this local optimizer.

With a feasible solution σ, let notation s′ represent the bottleneck station of solution σ (i.e. the station where maximum weighted inventory level occurs in σ), and L s max be the corresponding maximum inventory level. These two variables could be given by:

s=argmaxs=1,2,,S{ωsmax{Ls,t|t=1,2,,T}}
L s max = max { L s , t | t { A i | i N s } }
where the maximum weighted inventory level occurs at station s′ during the whole planning horizon. To improve solution σ, the proposed local optimizer generates compound neighborhoods by rearranging all boxes destined for station s′ while retaining the releasing of remaining boxes. Figure 6 provides an explanation of the example in Section 3, where σ = {{7,2,1,3} and {5,4,6}}. According to the resulting varying inventory level in Figure 2, the maximum weighted inventory level occurs at Station 3 (bottleneck station of schedule σ) and the corresponding variable L s max is 7. As boxes 5, 6 and 7 are destined for Station 3, the proposed local optimizer tries to improve solution σ by rearranging these three boxes in positions ① – ③. As the delivery times of each box is uniquely determined by its destination station, this modified process would have no influences on the specific points in time when the bottleneck station is supplied with parts. Obviously, it is a sequencing problem in nature, and the delivery sequence of boxes destined for bottleneck station would directly determine the state of line-side inventory at station s′, (i.e. the performance of solution σ). Moreover, the inventory status at other stations remains the same as the original solution.

Let Ns denote the set of material boxes destined for station s′ and Hs(σ) be objective-related production cycles of boxes in set Ns, that is Hs(σ) = {⌈Ai⌉ |si = s′}. For simplicity sake, all the elements in Hs(σ) are sorted in descending order. With above notations, the proposed breadth-first tree search optimizer takes following steps to generate competitive solution of current solution:

  • Step 1. Set π = ∅, k = 1 and Π = {π}. Then go to step 2.

  • Step 2. ∀πi ∈ Π, obtain the set Ω(πi) = Hs(σ)\πi and go to step 3.

  • Step 3. ∀πi ∈ Π, form the set Ψ(πi) = {πiψj|ψj ∈ Ω(πi)}. If |Ω(πi) |≥ ℓ, keep ℓ sequence with most aψj value.

  • Step 4. ∀πp ∈ Ψ(πi), calculate the inventory status Ls',tk at station s′ in time tk(tk ∈ Hs(σ)). If πp satisfies no stock-out constraint according to property 2 and it holds that L s ' , t k < L s max , retain πp; otherwise, set Ψ(πi) = Ψ(πi)\πp.

  • Step 5. Update Π=i=1|Π|Ψ(πi) and set kk + 1. If k >|Ns| or Π = ∅, terminate the tree search procedure; otherwise, go to step 2.

Variable L s max and the no stock-outs constraints are used to cut unpromising branches in the tailored tree search optimizer. Meanwhile, parameter ℓ is adopted here to control the search space. Competitive solutions of solution σ are obtained when set Π is nonempty, and the sequence with the best performance would be selected.

Figure 7 illustrates the graphical tree search and the explanations when applying the tailored optimizer to the given example in Section 3. It can be noticed that two sequences ({5,6,7} and {6,5,7}) are obtained in the final, and each of these two sequences holds that max{Ls,t|t ∈ Hs(σ)} = 4. Therefore, the local optimizer generates two competitive solutions, i.e. {{5,2,1,3},{6,4,7}} and {{6,2,1,3},{5,4,7}}). Figure 8 depicts the inventory information of the improved solution. Obviously, the inventory status at Station 3 remains lean and at extreme low levels when compared to Figure 2.

4.5 Pheromone update

The pheromone update is carried out at the end in each iteration, which consists of two aspects: pheromone deposit and pheromone trail evaporation. In the proposed HACO, the pheromone trail (τij) is referred to as the attractiveness between the unscheduled material boxes and the selected server in box selection. The pheromone deposit aims to enhance the pheromone information of solution components in good solutions, which makes those components more desirable for ants. Meanwhile, pheromone deposited by previous ants would slowly diminish in pheromone trail evaporation, which has efficiently avoided the convergence to local optima. In the initial phase, the pheromone trails on all solution components are set to a small value (i.e. τij= τ0) as there are no pheromone trails on these components. Once a complete schedule has been established by an ant, the proposed local optimizers are applied to further improve the solution performance. Then, the pheromone on visited solution components are to be updated by local pheromone update operation in the following equation:

τij=(1ρL)τij+ρL(QZ)
where ρL(0 < ρL < 1) represents the local pheromone evaporation rate and Z denotes the evaluation of the current solution.

Once a colony of ants has finished their solution exploration and local pheromone update, global pheromone updating is performed to enhance pheromone information to the schedule with the best performance. Consequently, only the ant that has found the best-known schedule is permitted to deposit pheromone. The following equation defines the global pheromone updating, where Z* represents the evaluation of best solution in the current colony:

τij=(1ρG)τij+ρL(QZ)

5 Computational experiments

5.1 Instance generation and parameter settings

The computational experiments distinguish between two groups of instances: Group 1 represents small-scale instances that could be solved optimally using a CPLEX solver within limited computation time, and Group 2 consists of real-world size instances that required to be solved heuristically. As there exists no available test-beds, this subsection is designed to generate instances for a computational study according to the original research by Boysen and Bock (2011). According to parameter settings in Table V, the scale of instance could be uniquely denoted by notation (n,m). As the proposed HACO approach is primarily designed for real-world scale scenarios, five different instances for problem (n,m) in Group 2 are generated randomly to reduce random errors in the computation. Consequently, the number of instances in Group 1 and Group 2 amount to 6·3 = 18 and 6·3·5 = 90, respectively.

Based on parameter settings collected in Table V, each single instance with n material boxes and m servers is established by taking the following steps:

  • For each instance, all n material boxes are randomly assigned to stations, where each station is assured of receiving at least one box.

  • Then, the time-varying demand of each station Ds,t (t = 1,2,⋯,T, s = t = 1,2,⋯,S) is determined by a random choice:

    Ds,t={Ds,t-1ifrand(0,1)0.5Ds,t-1+1otherwise

  • Finally, the initial inventory as0 at station s is determined as a random integer from uniform distribution in interval [2,5]. And the resulting remaining parts at each station are randomly assigned to the boxes destined for the corresponding station.

The proposed HACO procedure was coded in MATLAB 2016a and implemented on a personal computer with a 2.5 GHz Intel Core i5 CPU and 4 GB of RAM. Meanwhile, the MILP formulation was solved by the CPLEX 12.4 MATLAB interface, and the time limitation for the default CPLEX solver was set to 3,600 s. The stopping criterion of HACO is the computational time limitation, which was, respectively, set to 30 and 600 s for each instance in Group1 and Group2. According to tentative experiments, the parameters of HACO metaheuristic are set as follows: qM = 0.7, qN = 0.7, ρL = 0.01, ρG = 0.01, β = 3 and the population size is 30. In the case of parameters Q and ℓ, the values are Q = 10 and ℓ = 5 for Group 1 and Q = 50 and ℓ = 10 for Group 2.

5.2 Comparison between HACO and CPLEX

First, 18 small-scale instances in Group 1 were applied to verify the effectiveness of MILP formulation and HACO approach. Notation Zo in Table VI represents the optimal objective value obtained by CPLEX, and CPU defines the corresponding computation time. To guarantee constancy of HACO, the simulation for each instance is repeated for 15 independent times. The best objective value in 15 runs for each instance is defined as Zb, while the worst is defined as Zw and the average is defined as Za. Meanwhile, the last column of Table VI lists the average gap between HACO and CPLEX (OG), calculated as (ZaZo)/Zo·100 per cent.

According to simulation results in Table VI, all 18 small-scale instances could be solved to optimality by CPLEX solver. However, it requires an enormous amount of computation time with the increasing instance scale. For the instance with 25 boxes and 5 machines, the elapsed time amounts to 1,393.96 s. Meanwhile, HACO approach is capable of obtaining the optimal solutions in 15 runs for each instance. In terms of the average performance, metric OG is (or pretty close to) 0 in most cases, which implies the effectiveness of HACO for solving small-scale instances.

Subsequently, 18 instance sets, including 90 instances, are examined with CPLEX and HACO. Considering increasing problem scales, the optimization by CPLEX may take several hours or even more, which exceeds the predefined time limitation (i.e. 3,600 s). Consequently, the lower bounds found by CPLEX within 3,600 s are used to analyze the simulation results of these instances. For each instance set, Table VII presents the average computation time required by CPLEX to solve five different instances. As for HACO approach, the simulation for each instance is repeated for 15 independent times to guarantee constancy. Considering the large amount of computational data, the simulation results of HACO are processed in the following way before listed in Table VII. For instance set (n,m), the best objective value for instance k (k = 1,2,⋯,5) among 15 runs is defined as Zbk and the average defined as Zak(h). Then, the relative gap values are calculated by taking Zbk(CPLEX) as reference: GAPbk=(ZbkZbk(CPLEX))/Zbk(CPLEX)100% and GAPak=(ZakZbk(CPLEX))/Zbk(CPLEX)100%, where Zbk(CPLEX) stands for the optimal result or lower bound by CPLEX within 3,600 s. Finally, the average relative gap values are given by: GAPb¯(h)=15k=15GAPbk and GAPa¯(h)=15k=15GAPbk(h).

According to the experimental results, only two instance sets are solved optimally in limited computation time with CPLEX solver. The performance of CPLEX is not good when applied to solve these real-world scale instances, as it adopts the general branch and bound method. In some instance sets, where CPLEX is able to obtain the optimal solution within 3,600 s, the gap (metrics GAPb¯ and GAPa¯) is pretty close to 0. For the other instance sets, where only lower bounds are found, the gap is relatively large. By checking the outputs of CPLEX solver in these instance sets, the results indicate that the solution found by HACO is not worse than the best and feasible solution obtained by CPLEX within 3,600 s (i.e. the upper bound of CPLEX).

5.3 Comparison between three ACO versions

Table VIII examines algorithm performance of three ACO versions on 6·3·5 = 90 real-world scale instances generated in Group 2, where “ACO”, “ACOL” and “HACO”, respectively, denote basic ACO, ACO with fast local search and proposed hybrid ACO approach. To guarantee constancy of these metaheuristics, the simulation for each instance is repeated for 15 independent times.

Considering the large amount of computational data, the simulation results are processed in the following way before collected in Table VIII. As five different instances are randomly generated for problem (n,m), the best objective value for instance k (k = 1,2,⋯,5) among 15 runs by algorithm h (h ∈ {AOC, ACOL, HACO} is defined as Zbk(h), while the worst is defined as Zwk(h) and the average is defined as Zak(h). Then, the relative objective values are calculated by taking Zbk(HACO) as reference: RZbk(h)=Zbk(h)/Zbk(HACO), RZwk(h)=Zwk(h)/Zbk(HACO) and RZak(h)=Zak(h)/Zbk(HACO). Finally, the average relative values for instance set (n,m) are given by: RZb¯(h)=15k=15RZbk(h), RZw¯(h)=15k=15RZwk(h) and RZa¯(h)=15k=15RZbk(h). Moreover, the gap values of different problem scales with a selected ACO approach are given by GAP=RZb¯(h)RZw¯(h) to indicate the robustness of three ACO versions (Figure 9).

To better illustrate the statistical significance of the results when comparing HACO with other two ACO versions, pairwise comparisons are carried out here with Wilcoxon rank-sum test that has been increasingly introduced for the intelligent computing research (Derrac et al., 2011). The null hypothesis is set to be that there is no statistical difference between HACO and ACO (or ACOL). As the simulation for each instance is repeated for 15 independent times, the null hypothesis could be rejected (at the 0.05 level) when the ranks-related variable W(W = min{W+, W})is less than or equal to 25. For problem (n,m), the average W value (denoted as W̄) of five different instances is calculated and listed in Table VIII.

According to the experimental results in Table VIII and Figure 9, some observations of the comparison among three ACO versions are summarized as follows:

  1. In terms of best performance in the 15 independent runs, it holds that RZb¯(HACO)=1 and RZb¯(HACO)<RZb¯(h) (h ∈ {ACO, ACOL}) for all 18 sets with 90 instances. This verifies the capabilities of HACO to obtain better results than ACO and ACOL approaches.

  2. As for the mean of metric RZa¯ over all 18 instances sets, the value of HACO amounts to 1.036, which are significantly smaller than those obtained by ACO (1.068) and ACOL (1.079). Meanwhile, HACO performs significantly better than basic ACO for all 18 instances sets and outperforms ACOL for 17 out of all 18 instance sets in a statistically significant manner. Although the difference is statistically insignificant for instance set (20,100), HACO is capable of obtaining better results than ACOL in terms of average performance (i.e., metric RZa¯). Consequently, it could be deduced that HACO is more efficient than ACO and ACOL approaches in a statistical sense.

  3. In regard to the gap values of different problem scales with a selected ACO approach (illustrated in Figure 9), the gap obtained by HACO is smaller than the one obtained by ACO and ACOL in most cases. This indicates that HACO performs more robustly when applied to solve these instance sets in different executions.

The optimization difficulty to solve these instances increases systematically when considering the real-world scales. Under such circumstances, the proposed modifications to basic ACO exhibit greater advantages. On the one hand, the fast local search is able to quickly improve solution performance through simple and efficient operations. On the other hand, the tailored breadth-first tree search procedure can directly minimize the inventory levels at bottleneck station. These applications have effectively overcome the blindness of basic ACO, which is beneficial to obtain high-quality schedules with a large probability.

5.4 Comparison with TLBO and ABC

A further performance comparison is investigated between HACO and other two metaheuristics: teaching learning-based optimization (TLBO) and artificial bee colony (ABC) (Rao et al., 2011; Karaboga and Basturk, 2007). The comparison could be explained for two reasons. First, ABC and TLBO have been proved to be most powerful metaheuristics for complex optimization problems, and they are similar and comparable to HACO approaches presented here (i.e. these three methods rely on a population-based exploration). Second, ABC and TLBO are algorithm-oriented designs and are relatively general methods. Meanwhile, HACO is a problem-oriented design with a fast local search and breadth-first tree search technique that focuses on solving the MSSP in the best way possible. Therefore, the comparison between HACO and these two metaheuristics is significant and interesting to some extent.

To guarantee constancy of these metaheuristics, the simulation for each instance is repeated for 15 independent times. Analogous to the experimental design in the previous subsection, both TLBO and ABC are introduced to solve all 18 instance sets, and simulation results are preceded and collected in Table IX. As TLBO and ABC are initially designed for continuous optimization problem, this subsection uses the coding and decoding method proposed by Niu et al. (2010) to adopt these metaheuristics to the proposed MSSP in the current research. The parameter settings of TLBO and ABC are set to be same as HACO, i.e. the population size is 50 and computational time limitation is 600 s. Meanwhile, the trails step of ABC in scout bee phase is set to 30. Four metrics used in the previous subsection are calculated here to evaluate the algorithm performance, and simulation results are collected in Table IX. Meanwhile, the gap values of different problem scales with a selected algorithm are illustrated in Figure 10 to explain the robustness-related information.

According to the experimental results in Table IX and Figure 10, some observations of simulation results are collected as follows:

  • In regard to the mean of metric RZa¯ over all 18 instances sets, the value of HACO amounts to 1.036, which is significantly smaller than TLBO (1.056) and ABC (1.060).

  • As for pairwise comparisons, HACO performs significantly better than TLBO for 15 out of all 18 instance sets and outperforms ABC for 17 out of all 18 instance sets in a statistically significant manner. As for other four instance sets (marked with “*”), HACO is able to obtain better average results (i.e. metric RZa¯) than TLBO or ABC.

  • In term of metric GAP (depicted in Figure 10), the gap obtained by HACO is smaller than the one obtained by TLBO and ABC in most cases, which indicate that HACO performs more robustly than TLBO and ABC when applied to solve these instance sets in different executions.

According to these computational experiments, it could be concluded that this problem-oriented HACO approach performs more effectively and robustly when applied to solve the proposed MSSP in different problem settings and executions.

6. Summary and conclusions

This article investigates a multiple server scheduling problem to facilitate a JIT part-supply for the AAL. A MILP model is developed to formulate the proposed MSSP to pave the way for CPLEX procedure. Because of the NP-hard nature, a hybrid ACO approach with embedded domain properties and two local optimizers is designed to solve this problem. The experimental results demonstrate that both CPLEX and HACO approach are capable of finding optimal solutions within limited computing time. Moreover, the performance of problem-oriented HACO for practical size instances robustly outperforms other general metaheuristics in a statistically significant manner.

In the future, stochastic aspects of real-world JIT part-supply processes shall be taken into consideration, including machine breakdowns and defective parts. Besides that, efficient solution procedures are required to provide decision support for automobile manufacturers.

Figures

Schematic representation of current problem setting

Figure 1

Schematic representation of current problem setting

Inventory level at each station

Figure 2

Inventory level at each station

Algorithm flowchart

Figure 3

Algorithm flowchart

Solution representation

Figure 4

Solution representation

Fast local search operators

Figure 5

Fast local search operators

Bottleneck station

Figure 6

Bottleneck station

Breadth-first tree search

Figure 7

Breadth-first tree search

Inventory status of the improved solution

Figure 8

Inventory status of the improved solution

The Gap values of three ACO versions

Figure 9

The Gap values of three ACO versions

The Gap values of three population-based approaches

Figure 10

The Gap values of three population-based approaches

Notations and definitions for MILP model

Notation Definition
Ch Delivery completion time of material box h(h = 1,2,⋯,n)
Γs,t Subset of boxes that have been delivered to at station s up to cycle t
yh Binary variable that takes the value one if material box h is the first box on one of the m servers (h = 1,2,⋯,n)
xih Binary variable that takes the value one if material box i is scheduled directly before box h on the same server (i,h = 1,2,⋯,n, ih)
xi,n + 1 Binary variable that takes the value one if material box i is the last box on a server i = 1,2,⋯,n
Zs The maximum weighted inventory level at station s in all production cycles (t = 1,2,⋯,T)
Z The maximum weighted inventory level per station (s = 1,2,⋯,S) and production cycle (t = 1,2,⋯,T)
R Sufficiently large number

Demand information

Station s Production cycle t
1 2 3 4 5 6 7 8
1 0 1 2 3 3 4 5 6
2 1 2 3 4 5 5 6 7
3 1 3 4 6 6 7 9 10

Box information

i 1 2 3 4 5 6 7
si 1 1 2 2 3 3 3
ai 2 3 2 3 2 2 5

Notations of HACO

Parameter Explanation
cj Makespan of the scheduled boxes on server j
ηij Heuristic information on the box-server pair (i,j)
τij Pheromone information on the box-server pair (i,j)
qM Favoring exploitation probability in server selection
qN Favoring exploitation probability in box selection
ρL Local pheromone evaporation rate
ρG Global pheromone evaporation rate
β Relative importance of τij over ηij

Parameter settings for instance generation

Notations Explanation Values
Group 1 Group 2
n The number of material boxes 15,17,19,21,23,25 100,120,140,160,180,200
m The number of servers 3,4,5 10,15,20
S The number of stations 3 20
T The number of production cycles 30 200
ωs Weighted coefficient at station s 1 Uniformly distributed in [1,2]
bs Delivery time for station s Uniformly distributed in [1,2] Uniformly distributed in [1,3]

Comparison between CPLEX and HACO for small-scale instances

Problem size CPLEX HACO
m n Zo CPU(seconds) Zb Zw Za OG/%
3 15 5 0.30 5 5 5.00 0.00
17 6 1.34 6 6 6.00 0.00
19 5 5.00 5 5 5.00 0.00
21 6 35.60 6 6 6.00 0.00
23 5 98.25 5 6 5.00 0.00
25 6 357.88 6 7 6.07 1.11
4 15 8 0.58 8 8 8.00 0.00
17 6 2.70 6 6 6.00 0.00
19 5 11.31 5 5 5.00 0.00
21 6 72.07 6 5 5.00 0.00
23 5 222.92 5 6 5.07 1.33
25 4 843.96 4 5 4.07 1.67
5 15 5 0.96 5 5 5.00 0.00
17 6 4.36 6 6 6.00 0.00
19 5 21.91 5 5 5.00 0.00
21 5 123.76 5 5 5.00 0.00
23 5 341.91 5 6 5.07 1.33
25 6 1,393.96 6 7 6.07 1.11

Comparison between CPLEX and HACO for real-world scale instances

Problem size Average computation time of CPLEX (seconds) HACO
m n GAPb¯/% GAPa¯/%
10 100 2,310.06* 0.000 0.043
120 2,989.89* 0.000 0.039
140 3,600.00 4.332 9.712
160 3,600.00 6.806 10.475
180 3,600.00 9.067 13.489
200 3,600.00 6.432 12.145
15 100 3,600.00 7.176 10.692
120 3,600.00 6.516 11.212
140 3,600.00 4.549 9.787
160 3,600.00 7.013 10.720
180 3,600.00 10.445 14.455
200 3,600.00 6.576 12.293
20 100 3,600.00 8.692 13.172
120 3,600.00 6.979 12.241
140 3,600.00 5.032 10.957
160 3,600.00 7.609 12.067
180 3,600.00 10.588 14.504
200 3,600.00 6.714 13.097
Note:

*The optimal solution found by CPLEX within 3,600 s

Comparison between three ACO versions

Problem size HACO ACOL W̄ ACO
m n RZb¯ RZa¯ RZw¯ RZb¯ RZa¯ RZw¯ RZb¯ RZa¯ RZw¯ W̄
10 100 1.000 1.043 1.063 1.042 1.061 1.113 16.8 1.036 1.060 1.138 15.7
120 1.000 1.039 1.068 1.035 1.061 1.122 18.0 1.042 1.068 1.147 14.7
140 1.000 1.023 1.076 1.022 1.071 1.144 19.6 1.021 1.080 1.154 12.8
160 1.000 1.026 1.074 1.019 1.065 1.118 17.5 1.022 1.068 1.154 16.3
180 1.000 1.043 1.074 1.033 1.068 1.128 18.4 1.046 1.076 1.154 15.7
200 1.000 1.023 1.088 1.021 1.078 1.135 13.9 1.019 1.084 1.154 13.2
15 100 1.000 1.031 1.065 1.023 1.056 1.119 13.1 1.026 1.063 1.133 12.1
120 1.000 1.028 1.071 1.020 1.066 1.122 14.6 1.023 1.070 1.149 14.5
140 1.000 1.023 1.063 1.018 1.061 1.115 23.2 1.021 1.065 1.137 20.2
160 1.000 1.029 1.053 1.020 1.050 1.097 15.2 1.025 1.054 1.139 14.8
180 1.000 1.064 1.083 1.053 1.083 1.154 19.2 1.054 1.082 1.177 14.8
200 1.000 1.043 1.107 1.030 1.098 1.147 13.8 1.045 1.112 1.192 13.1
20 100 1.000 1.048 1.071 1.044 1.055 1.127 26.8* 1.045 1.071 1.151 13.8
120 1.000 1.036 1.100 1.035 1.100 1.178 17.9 1.033 1.096 1.192 13.8
140 1.000 1.047 1.116 1.036 1.104 1.172 18.9 1.044 1.119 1.187 14.3
160 1.000 1.046 1.076 1.035 1.068 1.130 16.0 1.048 1.076 1.162 14.8
180 1.000 1.023 1.083 1.018 1.075 1.136 15.5 1.025 1.084 1.162 14.1
200 1.000 1.030 1.076 1.029 1.066 1.136 18.7 1.030 1.080 1.165 16.1
Mean of all 1.000 1.036 1.078 1.030 1.068 1.133 1.034 1.079 1.158
Note:

*Pairwise comparison between HACO and ACO (or AOL) is not significant at the 0.05 level

Comparison with TLBO and ABC

Problem size HACO TLBO W̄ ABC
m n RZb¯ RZa¯ RZw¯ RZb¯ RZa¯ RZw¯ RZb¯ RZa¯ RZw¯ W̄
10 100 1.000 1.043 1.063 1.016 1.055 1.087 20.8 1.018 1.059 1.089 18.8
120 1.000 1.039 1.068 1.012 1.055 1.100 22.1 1.026 1.057 1.098 19.2
140 1.000 1.023 1.076 1.012 1.047 1.134 22.9 1.013 1.055 1.145 22.2
160 1.000 1.026 1.074 1.013 1.042 1.125 21.3 1.014 1.056 1.120 21.2
180 1.000 1.043 1.074 1.025 1.058 1.100 22.8 1.021 1.054 1.107 27.1
200 1.000 1.023 1.088 1.010 1.051 1.156 20.7 1.016 1.043 1.161 14.5
15 100 1.000 1.031 1.065 1.014 1.048 1.104 20.9 1.017 1.051 1.102 14.1
120 1.000 1.028 1.071 1.015 1.053 1.110 21.9 1.013 1.056 1.113 18.3
140 1.000 1.023 1.063 1.007 1.044 1.102 24.8 1.010 1.045 1.099 23.9
160 1.000 1.029 1.053 1.009 1.038 1.080 27.3* 1.020 1.043 1.074 22.6
180 1.000 1.064 1.083 1.029 1.070 1.102 28.6* 1.027 1.075 1.105 22.7
200 1.000 1.043 1.107 1.022 1.076 1.164 21.6 1.024 1.088 1.159 19.1
20 100 1.000 1.048 1.071 1.015 1.057 1.092 29.5* 1.025 1.063 1.090 17.1
120 1.000 1.036 1.100 1.015 1.067 1.160 24.4 1.017 1.061 1.172 19.8
140 1.000 1.047 1.116 1.015 1.083 1.176 24.9 1.032 1.076 1.192 24.3
160 1.000 1.046 1.076 1.020 1.064 1.106 22.8 1.026 1.059 1.117 26.2*
180 1.000 1.023 1.083 1.012 1.048 1.153 19.6 1.012 1.053 1.158 17.8
200 1.000 1.030 1.076 1.014 1.047 1.130 24.8 1.020 1.055 1.128 21.0
Mean of all 1.000 1.036 1.078 1.015 1.056 1.121 1.020 1.060 1.124
Note:

*Pairwise comparison between HACO and TLBO (or ABC) is not significant at the 0.05 level

References

Alnahhal, M. and Noche, B. (2015), “A genetic algorithm for supermarket location problem”, Assembly Automation, Vol. 35 No. 1, pp. 122-127.

Azizoglu, M. and Kirca, O. (1998), “Tardiness minimization on parallel machines”, International Journal of Production Economics, Vol. 55 No. 2, pp. 163-168.

Baker, K.R. and Scudder, G.D. (1990), “Sequencing with earliness and tardiness penalties: a review”, Operations Research, Vol. 38 No. 1, pp. 22-36.

Battini, D., Boysen, N. and Emde, S. (2012), “Just-in-time supermarkets for part supply in the automobile industry”, Journal of Management Control, Vol. 24 No. 2, pp. 209-217.

Battini, D., Gamberi, M., Persona, A. and Sgarbossa, F. (2015), “Part-feeding with supermarket in assembly systems: transportation mode selection model and multi-scenario analysis”, Assembly Automation, Vol. 35 No. 1, pp. 149-159.

Bean, J.C. (1994), “Genetic algorithms and random keys for sequencing and optimization”, ORSA Journal on Computing, Vol. 6 No. 2, pp. 154-160.

Beraldi, P., Ghiani, G., Grieco, A. and Guerriero, E. (2008), “Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs”, Computers & Operations Research, Vol. 35 No. 11, pp. 3644-3656.

Biskup, D., Herrmann, J. and Gupta, J.N. (2008), “Scheduling identical parallel machines to minimize total tardiness”, International Journal of Production Economics, Vol. 115 No. 1, pp. 134-142.

Boysen, N. and Bock, S. (2011), “Scheduling just-in-time part supply for mixed-model assembly lines”, European Journal of Operational Research, Vol. 211 No. 1, pp. 15-25.

Boysen, N., Bock, S. and Fliedner, M. (2013), “Scheduling of inventory releasing jobs to satisfy time-varying demand: an analysis of complexity”, Journal of Scheduling, Vol. 16 No. 2, pp. 185-198.

Boysen, N. and Emde, S. (2014), “Scheduling the part supply of mixed-model assembly lines in line-integrated supermarkets”, European Journal of Operational Research, Vol. 239 No. 3, pp. 820-829.

Boysen, N., Fliedner, M. and Scholl, A. (2007), “A classification of assembly line balancing problems”, European Journal of Operational Research, Vol. 183 No. 2, pp. 674-693.

Boysen, N., Fliedner, M. and Scholl, A. (2009), “Sequencing mixed-model assembly lines: survey, classification and model critique”, European Journal of Operational Research, Vol. 192 No. 2, pp. 349-373.

Caputo, A.C., Pelagagge, P.M. and Salini, P. (2015), “A decision model for selecting parts feeding policies in assembly lines”, Industrial Management & Data Systems, Vol. 115 No. 6, pp. 974-1003.

Derrac, J., García, S., Molina, D. and Herrera, F. (2011), “A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms”, Swarm and Evolutionary Computation, Vol. 1 No. 1, pp. 3-18.

Doğramaci, A. (1984), “Production scheduling of independent jobs on parallel identical processors”, The International Journal of Production Research, Vol. 22 No. 4, pp. 535-548.

Dogramaci, A. and Surkis, J. (1979), “Evaluation of a heuristic for scheduling independent jobs on parallel identical processors”, Management Science, Vol. 25 No. 12, pp. 1208-1216.

Dorigo, M., Birattari, M. and Stutzle, T. (2006), “Ant colony optimization”, IEEE Computational Intelligence Magazine, Vol. 1 No. 4, pp. 28-39.

Elmaghraby, S.E. and Park, S.H. (1974), “Scheduling jobs on a number of identical machines”, AIIE Transactions, Vol. 6 No. 1, pp. 1-13.

Emde, S. (2017), “Scheduling the replenishment of just-in-time supermarkets in assembly plants”, OR Spectrum, Vol. 39 No. 1, pp. 321-345.

Emde, S., Fliedner, M. and Boysen, N. (2012), “Optimally loading tow trains for just-in-time supply of mixed-model assembly lines”, IIE Transactions, Vol. 44 No. 2, pp. 121-135.

Faccio, M., Gamberi, M., Persona, A., Regattieri, A. and Sgarbossa, F. (2013), “Design and simulation of assembly line feeding systems in the automotive sector using supermarket, Kanbans and tow trains: a general framework”, Journal of Management Control, Vol. 24 No. 2, pp. 187-208.

Fang, K.T. and Lin, B.M.T. (2013), “Parallel-machine scheduling to minimize tardiness penalty and power cost”, Computers & Industrial Engineering, Vol. 64 No. 1, pp. 224-234.

Fathi, M., Rodríguez, V. and Alvarez, M.J. (2014b), “A novel memetic ant colony optimization-based heuristic algorithm for solving the assembly line part feeding problem”, International Journal of Advanced Manufacturing Technology, Vol. 75 No. 1, pp. 629-643.

Fathi, M., Alvareza, M.J., Rodríguezb, V. and Mehrabanc, F.H. (2014a), “A multiobjective optimization algorithm to solve the part feeding problem in mixed-model assembly lines”, Mathematical Problems in Engineering, Vol. 11 No. 1, pp. 809-812.

Fathi, M., Rodríguez, V., Fontes, D.B.M.M. and Alvarez, M.J. (2015), “A modified particle swarm optimization algorithm to solve the part feeding problem at assembly lines”, International Journal of Production Research, Vol. 54 No. 3, pp. 878-893.

Ho, J.C. and Chang, Y.L. (1991), “Heuristics for minimizing mean tardiness form parallel machines”, Naval Research Logistics, Vol. 38 No. 3, pp. 367-381.

Kamal Uddin, M., Cavia Soto, M. and Martinez Lastra, J.L. (2010), “An integrated approach to mixed-model assembly line balancing and sequencing”, Assembly Automation, Vol. 30 No. 2, pp. 164-172.

Karaboga, D. and Basturk, B. (2007), “A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm”, Journal of Global Optimization, Vol. 39 No. 3, pp. 459-471.

Kilic, H.S. and Durmusoglu, M.B. (2015), “Advances in assembly line parts feeding policies: a literature review”, Assembly Automation, Vol. 35 No. 1, pp. 57-68.

Kim, C.O. and Shin, H.J. (2003), “Scheduling jobs on parallel machines: a restricted tabu search approach”, The International Journal of Advanced Manufacturing Technology, Vol. 22 Nos 3/4, pp. 278-287.

Koulamas, C. (1997), “Decomposition and hybrid simulated annealing heuristics for the parallel‐machine total tardiness problem”, Naval Research Logistics, Vol. 44 No. 1, pp. 109-125.

Lee, Z.J., Lee, C.Y. and Su, S.F. (2002), “An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem”, Applied Soft Computing, Vol. 2 No. 1, pp. 39-47.

Merengo, C., Nava, F. and Pozzetti, A. (1999), “Balancing and sequencing manual mixed-model assembly lines”, International Journal of Production Research, Vol. 37 No. 12, pp. 2835-2860.

Meuleau, N. and Dorigo, M. (2002), “Ant colony optimization and stochastic gradient descent”, Artificial Life, Vol. 8 No. 2, pp. 103-121.

Niu, Q., Zhou, T.J. and Wang, L. (2010), “A hybrid particle swarm optimization for parallel machine total tardiness scheduling”, The International Journal of Advanced Manufacturing Technology, Vol. 49 Nos 5/8, pp. 723-739.

Ou, J.W., Zhong, X.L. and Wang, G.Q. (2015), “An improved heuristic for parallel machine scheduling with rejection”, European Journal of Operational Research, Vol. 241 No. 3, pp. 653-661.

Tanaka, S. and Araki, M. (2008), “A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines”, International Journal of Production Economics, Vol. 113 No. 1, pp. 446-458.

Pedemonte, M., Nesmachnow, S. and Cancela, H. (2011), “A survey on parallel ant colony optimization”, Applied Soft Computing, Vol. 11 No. 8, pp. 5181-5197.

Raghavan, N.R.S. and Venkataramana, M. (2009), “Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimization”, The International Journal of Advanced Manufacturing Technology, Vol. 41 Nos 9/10, pp. 986-996.

Rao, R.V., Savsani, V.J. and Vakharia, D.P. (2011), “Teaching–learning-based optimization: a novel method for constrained mechanical design optimization problems”, Computer-Aided Design, Vol. 43 No. 3, pp. 303-315.

Rao, Y.Q., Wang, M.C., Wang, K.P. and Wu, T.M. (2013), “Scheduling a single vehicle in the just-in-time part supply for a mixed-model assembly line”, Computers & Operations Research, Vol. 40 No. 11, pp. 2599-2610.

Zhou, B. and Peng, T. (2017), “Scheduling the in-house logistics distribution for automotive assembly lines with just-in-time principles”, Assembly Automation, Vol. 37 No. 1, pp. 51-63.

Acknowledgements

This work is supported by the National Natural Science Foundation of China (71471135).

Corresponding author

Binghai Zhou can be contacted at: bhzhou@tongji.edu.cn