1 Introduction

The significance of distributed manufacturing has been recognized by many researchers and industrialists in recent years due to the changes in the mode of today’s production environment. Single factory or centralized production environment in traditional manufacturing systems has been gradually replaced by more flexible distributed settings, including multi-factory networks or multi-cell job shops due to the trend of globalization [1]. The distributed manufacturing enables the enterprises to be closer to their customers and suppliers, to produce and market their products more effectively, to be responsive to market changes more quickly, to achieve better product quality, lower production cost, reduced management risk, and better utilization of production resources [1–4].

The distributed manufacturing takes place in a multi-factory environment including several factories, which may be geographically distributed in different locations or in a multi-cell environment including several independent manufacturing cells located in the same plant [5]. Each factory/cell is capable of manufacturing a variety of product types. In addition, the factories or cells have different production efficiencies, operating costs, production lead times, constraints, etc. [1]. An important issue in dealing with the production in this decentralized manner is the scheduling of manufacturing operations of products (jobs) in the distributed manufacturing system [4, 6].

In this paper, we study the distributed and flexible job-shop scheduling problem (DFJSP) which involves the scheduling of jobs in a distributed manufacturing environment described above, under the assumption that the shop floor of each factory/cell is configured as a flexible job shop (therefore, each factory/cell will be hereafter called flexible manufacturing unit (FMU) [5]). The flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem (JSP), where each operation is allowed to be processed on any among set of available machines; and thus, the scheduling problem is to choose, for each operation, a machine and a starting time at which the operation must be processed [7, 8]. The DFJSP consists of the following two subproblems which can be solved sequentially or simultaneously: (1) the assignment of each job to exactly one FMU (which corresponds to one cell in a multi-cell environment or one factory in a multi-factory setting), and (2) the scheduling of the jobs in each FMU, i.e. solving an FJSP for each FMU. Once a job is assigned to an FMU and started its processing (but not finished), it is usually not possible or uneconomical to transfer this unfinished job to another FMU for the remaining operations [1]. Therefore, we assume that once a job is allocated to an FMU, all its operations have to be processed in the same FMU. We also suppose that all the FMUs belong to the same company. Accordingly, they work cooperatively to define an optimal production plan maximizing the revenue of the company as a whole. The objective is to minimize the makespan, i.e. the overall completion time of all the jobs on all the FMUs. The DFJSP is more complicated than the traditional FJSP in single FMU, because it involves not only the FJSP in each FMU but also the problem in an upper level that is the assignment of the jobs to the FMUs. This problem is strongly NP-hard, since the problem with one FMU, i.e. the FJSP, is already strongly NP-hard [9]. This justifies the need for developing efficient heuristic algorithms to obtain approximate solutions of good quality at little computational cost. These heuristic algorithms are very fast in comparison with the exact methods and the metaheuristic algorithms, and if they have been proved to produce solutions with adequate accuracy, they can be the best approach. Therefore, this paper proposes a powerful heuristic algorithm to solve the problem.

Almost all existing studies in the field of production scheduling deal with the centralized or non-distributed production environments, and only few papers investigate the distributed scheduling problems, especially those involving the DFJSP [6]. Due to the complexity of the distributed scheduling problems mentioned above, approximate algorithms, mainly metaheuristics, have been often used to solve the problem. A review of heuristics developed to solve these problems can be found in references [5, 6]. Wang et al. [10] consider the distributed permutation flow-shop scheduling problem and present an effective estimation of distribution algorithm (EDA) to solve the problem. Just this problem is also examined in [11] and solved by a tabu search algorithm. Jia et al. [4, 12] present a modified genetic algorithm to solve the distributed scheduling problem in a multi-factory network in which each factory is configured as a job shop. Chan et al. [13, 14] consider the DFJSP and present a genetic algorithm with dominated genes (GADG) to solve the problem and demonstrate the performance of the method by using several new DFJSP instances. Also, Chan et al. [1] study a generalized version of the DFJSP in which machine maintenance constraints are considered and it is assumed that the maintenance time is related to the machine age. A mathematical model and a genetic algorithm with dominant genes (GADG) are developed for the problem. For both with and without maintenance constraints, the performance of the presented genetic algorithm is evaluated using some new test instances. Giovanni and Pezzella [5] present an improved genetic algorithm to solve the DFJSP. The proposed approach is compared with other algorithms for distributed scheduling and tested on a large set of DFJSP instances derived from well-known FJSP benchmarks, providing good results. As it can be seen in the above review of literature on the distributed scheduling problems, studies on methods for solving these problems are in the early stage. Almost all the proposed methods are metaheuristic algorithms and very time-consuming in comparison with the heuristic algorithms, because they perform search procedure in a large part of the solution space.

In this study, we present a heuristic method based on a constructive procedure to solve the DFJSP with the objective of minimizing makespan (Sect. 3). The main purpose is to produce reasonable and applicable schedules very quickly. It can also be used to improve the quality of the initial feasible solution of metaheuristics applied to solve the problem, since the choice of a good initial solution is an important aspect of the performance of the algorithms in terms of computation time and solution quality [15–17]. In order to evaluate the performance of the proposed heuristic, we implement it using several benchmark problems and present the results of the computational experiments (Sect. 4). The results show that our novel method can obtain good solutions in very short time. Concluding remarks are given in the last section.

2 Assumptions and notation

The assumptions considered in this paper are as follows:

  1. (1)

    Each FMU can produce all jobs with different efficiencies.

  2. (2)

    For each job, all FMUs have the same number of operations.

  3. (3)

    Jobs are independent of each other.

  4. (4)

    Setup and transportation times are negligible.

  5. (5)

    Preemption is not allowed, i.e. a started operation cannot be interrupted during its processing.

  6. (6)

    Each machine can process at most one operation at the same time.

  7. (7)

    All jobs have equal priorities.

  8. (8)

    Machines never break down and are available throughout the scheduling period.

  9. (9)

    All FMUs, jobs and machines are available at time zero.

The notation used throughout the paper is as follows:

l::

number of FMUs,

n::

number of jobs,

f::

index of FMUs; f=1,…,l,

i,z::

index of jobs; i,z=1,…,n,

m f ::

number of machines in FMU f,

J i ::

number of operations of job i,

maxJ::

maximum number of operations per job (i.e., maxJ=max i J i ),

j::

index of operations; j=1,…,J i ,

k,y::

index of machines; k,y=1,…,m f ,

t fijy ::

processing time (duration) of operation j of job i on machine y of FMU f,

c fij ::

completion time of operation j of job i on FMU f.

A fij ::

set of machines in FMU f which are capable to execute operation j of job i,

N fij ::

number of members of the set A fij ,

\(s'_{\mathit{fij}}\)::

mean processing time of operation j of job i over the machines belonging to the set A fij (i.e., \(s'_{fij}=(\sum_{y \in A_{fij}} t_{fijy} )/N_{fij}\)),

sj fi ::

total mean processing time of job i in FMU f (i.e., \(\mathit{sj}_{fi} = \sum_{j = 1}^{J_{i}} s'_{fij}\)),

sk fy ::

total weighted processing time on machine y of FMU f which is calculated as follows: \(\mathit{sk}_{fy} =\sum_{i = 1}^{n} \sum_{{\scriptstyle j = 1 \atop \scriptstyle ify \in A_{\mathit{fij}}}}^{J_{i}} \frac{t_{\mathit{fijy}}}{N_{fij}}\),

IF f ::

number of jobs assigned to FMU f,

M::

a large number.

3 Proposed heuristic approach

In this section, a heuristic method is presented to solve the problem. This approach is motivated by the idea of developing a constructive heuristic that considers simultaneously many factors affecting the solution quality and intelligently balances their effects in the process of schedule generation, and the observation that it can lead to good results in some preliminary computational experiments on a wide range of difficult scheduling problems.

An outline of the proposed heuristic algorithm is given in Fig. 1.

Fig. 1
figure 1

General outline of the proposed heuristic algorithm

Full size image

The pseudocode of the proposed heuristic is shown in Fig. 2. In this algorithm, each unscheduled operation (i, j) (i.e. operation j of job i) to be scheduled on machine y of FMU f is evaluated by the following criterion, and the unscheduled operation with minimum TC is selected for scheduling.

$$\mathit{TC} = \sum_{r = 1}^{5} w_{r}\times x_{r}\times C_{r} $$

such that,

Fig. 2
figure 2figure 2figure 2

Pseudocode of the proposed heuristic method

Full size image

\(C_{1} =\max(C_{\max_{fy}}, c_{f,i,j-1} ) + t_{\mathit{fijy}}\)

\(C_{2} = \max(0,( c_{f,i,j-1} -C_{\max_{fy}} ))\)

C 3=t fijy

C 4=sk fy /(n+maxJ)

C 5=sj fi

TC is weighted sum of some criteria which are established based on the factors affecting the objective function value. Minimization of TC in the process of schedule generation leads to improvement in solution quality. The w r (r=1,2,…,5) are constants and the x r (r=1,2,…,5) are integer variables used to increase the flexibility and efficiency of criterion TC and they have a significant impact on the performance of the algorithm. The constant weights (w r ) are preliminary estimated weights assigned to criteria according to their importance, and the coefficients x r are variables bounded in a given range and used to refine the TC. \(C_{\max_{fy}}\) is the maximum completion time across all the operations scheduled on machine y of FMU f; that is, \(C_{\max_{fy}}\) is equal to the completion time of the operation situated just before operation j of job i on machine y of FMU f. C 1 and C 2 are applied to decrease \(C_{\max_{fy}}\) and idle times, respectively; clearly, both these objectives affect the main objective function, i.e. C max. For assigning operations to a machine, their processing times are also taken into account by C 3. C 4 and C 5 are used for taking into account the total weighted processing time of machines, and the total mean processing time of jobs, respectively.

Another notation used in the pseudocode of the heuristic is as follows:

TC ∗: denotes the best value of TC. After each operation is scheduled, TC ∗ is reset to M.

L_x r (r=1,2,…,5): lower limit of x r .

U_x r (r=1,2,…,5): upper limit of x r .

To prevent assigning too many jobs to a single FMU and to achieve balanced distribution of the jobs among the FMUs, we use a parameter called MIF which is defined as the maximum number of jobs assigned to a single FMU and calculated as follows:

$$\mathit{MIF} = n / l. $$

Thus, IF f (for f=1,2,…,l) must be less than MIF (IF f <MIF).

The algorithm starts by scheduling the first operation of all jobs, then their second operation, and so on (F2, L19 (i.e. Line 31 of Fig. 2)). For each j (j=1,2,…,maxJ), the algorithm sorts the FMUs in increasing order of their IF f (F2, L26) and, for each FMU f taken in this order (F2, L31), the algorithm sorts the jobs in decreasing order of their sj fi and takes a job i in this order (F2, L35). Therefore, if two unscheduled operations belonging to two different jobs have the same value of TC, then according to this sorting of the jobs, the operation of job with greater sj fi is selected for scheduling sooner than the other operation. Next, if job i is an unassigned job and IF f < MIF, the algorithm evaluates its first operation to be assigned to and scheduled on FMU f. If job i is already assigned to FMU f, then the algorithm evaluates its jth (j>1) operation (if j≤J i and operation j of job i is an unscheduled operation). For evaluating operation j of job i on FMU f, similarly the algorithm first sorts the machines of FMU f in increasing (decreasing) order of their sk fy and, for each machine y taken in this order (F2, L47), evaluates this operation (F2, L54 to L60) to be scheduled on machine y (if machine y is capable of processing this operation, i.e. y∈A fij ). Binary variable x 6 is applied for setting the order of the sorting (i.e. either increasing order or decreasing order): it takes a value of 1 for increasing order and 0 for decreasing one. Sorting the jobs, the machines and the FMUs, described above and done before evaluating them for scheduling, may lead to better solutions. Indeed, in our preliminary computational experiments, we used these sortings of the FMUs, jobs and machines instead of randomly selecting them, and observed that these sortings can lead to better solutions. Specially, the results showed that in most cases, sorting the jobs in decreasing order of their sj fi leads to better solutions in comparison with increasing order. It is because the jobs with larger sj fi which are firstly selected for scheduling have more sensibility and effect on the objective value. In other words, the schedule of these jobs determines the performance of overall schedule of the problem. Therefore, we have used only their decreasing order in the computational experiments. Similarly, the results showed that in most cases, sorting the FMUs in increasing order of their IF f leads to better solutions in comparison with decreasing order. This is because this sorting leads to keep balanced distribution of the jobs among the FMUs. Therefore, we have used only their increasing order in the computational experiments. For the machines however we could not definitely determine their best order (i.e. either increasing or decreasing one), and so the algorithm itself selects the best order for each problem instance. The \(x_{r}^{*}\) (r=1,2,…,6) are the best values of variables x r (i.e. the values corresponding to the best solutions). Indeed, for various values of x r (r=1,2,…,6) (F2, L8 to L12), the algorithm in Fig. 1 is run and a complete schedule is generated. Among all these schedules, the one with minimum makespan is reported as the final solution (F2, L82 to L84). The values of variables x r for this best solution are also reported and denoted by \(x_{r}^{*}\) (see Table 2).

As mentioned earlier, the evaluation of the operations for scheduling them is done using the criterion TC (F2, L54), i.e. the unscheduled operation with minimum TC is selected for scheduling.

4 Computational results

This section describes the computational experiments conducted in order to evaluate the performance of the proposed heuristic method. First, some preliminary experiments have been conducted for the parameter settings. Regarding the test on various values for the parameters of the algorithm and considering the computational results, we use the settings of Table 1 for benchmarking the presented algorithm.

Table 1 Parameter settings for the heuristic
Full size table

The algorithm is coded in C language and run on a Pentium IV, 2.2 GHz and 2.0 GB RAM PC. The computational results of the proposed algorithm are compared to the results of the improved genetic algorithm (IGA) developed by Giovanni and Pezzella [5] which, to the best of our knowledge, is the only contribution containing explicit computational results for the DFJSP. The benchmark problems used are the set of 69 DFJSP instances presented in [5]. They are classified into three categories: DFJSP instances with two, three and four FMUs, where the computational results of them are shown in Tables 2, 3 and 4, respectively. The first three columns refer to the name of the FJSP instance used to derive the DFJSP instance together with the number of jobs and machines. LB stands for the lower bounds computed by [5]. BC max, Av. (C max) and Av. time indicate the best makespan, the average makespan and the average computational time, respectively. The results obtained by the heuristic are shown in the last nine columns. C max and Time represent the makespan value and computational time (in seconds), respectively. The best values of variables x r (i.e. \(x_{r}^{*}\)), r=1,2,…,6, are also reported in the tables. The average value of each variable x r , r=1,2,…,5, can be considered as the relative effect of the corresponding criterion on the quality of solutions. For example, the average value of x 4 is near zero in all three tables which means that the total weighted processing time of machines has little effect on C max. Of course, as it can be seen, the values of each variable x r , r=1,2,…,5, have relatively high variance in all three tables, meaning that they are strongly dependent on the specifications of problem instance under consideration and on the values of other variables x r . The proposed algorithm selects for each instance the best combination of x r values leading to the best result. Average weight of C 5 is negative in all three instance sets, i.e. w 5×x 5<0, which means that it has adverse effect on C max. Average value of x 6 in the tables is nearer to 0 than 1. It is because the machines with larger sk fy which are firstly selected for scheduling have more sensibility and effect on the objective value. RPD is the relative percentage deviation to LB and is calculated as follows:

$$\mathit{RPD} = \frac{C\max_{\mathrm{alg}} - \mathit{LB}}{\mathit{LB}} \times 100, $$

where \(C_{\max_{\mathrm{alg}}}\) is the best makespan obtained by the algorithm. The results show that the heuristic finds the optimal solution (\(C_{\max}^{*} = \mathit{LB}\)) for 46 out of 69 problems, which represents 66.7 % of the problems tested. For some instances (specially those with two FMUs), the gap is large, but it is notable that the lower bounds computed by [5] are poor as stated in this reference. Herein, the heuristic is statistically compared with the method IGA. For each of the three instance sets, a one-way analysis of variance (ANOVA) [18] is performed to test the null hypothesis that the means of the two methods are equal. The results of these ANOVA for DFJSP instances with two, three and four FMUs are presented in Tables 5, 6 and 7, respectively. As it can be seen, in all three instance sets, the difference between the methods is not meaningful at a significance level of 5 %. However, the average computational time for the heuristic over all 69 instances is very low, and only (0.4+0.5+0.8)/3=0.57 seconds (on a Pentium IV, 2.2 GHz) compared to (16.2+27.9+79.6)/3=41.2 seconds (on a 2.0 GHz Intel Core2 processor) for IGA. Differences in the computers used for running the programs make the direct comparison among the running times difficult. However, even accounting for relative differences in the speed between the processors involved, the heuristic is significantly faster than IGA.

Table 2 Computational results for DFJS instances with two FMUs
Full size table
Table 3 Computational results for DFJS instances with three FMUs
Full size table
Table 4 Computational results for DFJS instances with four FMUs
Full size table
Table 5 Results of one-way ANOVA for the methods: IGA and proposed heuristic, and for instances with two FMUs
Full size table
Table 6 Results of one-way ANOVA for the methods: IGA and proposed heuristic, and for instances with three FMUs
Full size table
Table 7 Results of one-way ANOVA for the methods: IGA and proposed heuristic, and for instances with four FMUs
Full size table

5 Conclusion

This paper investigates the distributed and flexible job-shop scheduling problem (DFJSP) with the objective of minimizing the overall completion time (makespan). The main purpose is to produce reasonable schedules very quickly. A simple and easily extendable heuristic based on a constructive procedure is presented. This heuristic uses an accurate, relatively comprehensive and flexible criterion for scheduling job operations and constructing a feasible high-quality solution. In this criterion, several factors affecting the quality of solutions are used, and to each of these factors, two weights (i.e. a constant weight and a variable weight) are assigned. By setting different values to the variable weights, different solutions are generated and evaluated. The proposed algorithm is tested on some problem instances from the literature in order to evaluate its performance. Since the proposed method is a heuristic, its results cannot be compared in a meaningful way with those of the method evaluated (IGA) as it is a metaheuristic based algorithm. Nevertheless, the heuristic is statistically compared with the IGA. For each of the three instance sets (i.e. DFJSP instances with two, three and four FMUs), a one-way ANOVA is performed to test the null hypothesis that the means of the two methods are equal. The results show that, in all three instance sets, the difference between the methods is not meaningful at a significance level of 5 %. However, the solutions of the heuristic are weakly dominated the solutions of the IGA in terms of average RPD. The computational times show the interest of the heuristic, since in a fraction of a second on average, it produces very good solutions. This algorithm has a simple structure, is easy to implement, and requires very little computational effort which makes it preferable over other more complex and time-consuming approaches, even if its results for benchmark instances are so weakly dominated the lower bounds in the literature. The procedure is useful in applications that deal with real-time systems and that involve the generation of initial schedules for local search and metaheuristic algorithms. Further research needs to be conducted in applying other criteria in the TC in order to improve the solution quality and adapt the approach to other objectives and process constraints. Moreover, the performance of the method proposed in this paper can be improved by doing a detailed study on the impact of different values of L_x r , U_x r and w r on the quality of solutions and considering other combinations of values of these variables, which is left as a future research.