Deterministic Assembly Scheduling Problems: A Review and Classification of Concurrent-Type Scheduling Models and Solution Procedures

Deterministic Assembly Scheduling Problems: A Review and Classification of Concurrent-Type Scheduling Models and Solution Procedures∗ Jose M. Framinan†Paz Perez-Gonzalez Victor Fernandez-Viagas Industrial Management, School of Engineering, University of Seville. Camino de los Descubrimientos s/n. 41092 Seville, Spain In memory of Rainer Leisten Abstract Many activities in industry and services require the scheduling of tasks that can be concurrently executed, the most clear example being perhaps the assembly of products carried out in manufacturing. Although numerous scientific contributions have been produced on this area over the last decades, the wide extension of the problems covered and the lack of a unified approach have lead to a situation where the state of the art in the field is unclear, which in turn hinders new research and makes translating the scientific knowledge into practice difficult. In this paper we propose a unified notation for assembly scheduling models that encompass all concurrent-type scheduling problems. Using this notation, the existing contributions are reviewed and classified into a single framework, so a comprehensive, unified picture of the field is obtained. In addition, a number of conclusions regarding the state of the art in the topic are presented, as well as some opportunities for future research. Keywords: Scheduling; Assembly; Review; Order Scheduling; Concurrent Operations; Distributed Flowshop Scheduling; Agile Manufacturing Systems ∗Preprint submitted to European Journal of Operational Research. DOI: https://doi.org/10.1016/j.ejor.2018.04.033 †Corresponding author. Tel. +3495 448 7214; fax: +3495 448 7329. E-mail address: [email protected] 1 1 Introduction In industry and services it is rather a common situation where one activity can start only if a set of previous tasks (sometimes carried out by different resources) have been completed. These tasks may be jointly scheduled in the different resources of the company in order to achieve the desired goals, as individual schedules in these resources would not ensure the necessary synchronisation to efficiently complete the tasks. Arguably the most visible example of this type of problem occurs in the assembly of parts in the manufacturing industry, henceforth the problem is known as the Assembly Scheduling Problem or ASP. Recently, in most industrial sectors, the strategy has changed from the paradigm of mass production to the manufacture of complex products using postponement strategies that usually entail the assembly of customised features, mainly due to the increasing competition among companies, and the increase of customer power. As a result, most companies nowadays focus on manufacturing only the specific parts of their productive processes in which they excel, and on outsourcing/purchasing those components/operations that do not constitute their core-competences. This leads to an increasing prevalence of assembly operations and, as a consequence, the ASP is being considered a very relevant problem by academics and practitioners. Not surprisingly, a huge number of contributions in the area have been produced in the last decades –as our review, with more than 200 papers, can attest–. However, to the best of our knowledge, almost no attempt to review or classify these works has been carried out: we recall only the work by Khodke and Bhongade (2013) where contributions regarding real-time operation of assembly systems are discussed, although it covers a rather limited part of the references discussed here–, and the topic has suffered from this lack of unified approach: Since a unified classification or notation for the different problems does not exist, the same models are given different names in different papers, and the case is not uncommon where some works neglect/ignore the existence of related results that could be applicable/compared. As a result, the-state-of-the-art of some problems and sub-problems remains unclear, which hinders the advance of research results and their applications in practice. In this paper, we aim to tackle these issues by proposing a unified notation for assembly scheduling problems. Using this notation, we review and classify the existing contributions in the area. The goal is to provide a global perspective of the field so the main results can be identified. Furthermore, we also discuss some open problems and possible research avenues. The remainder of the paper is structured as follows: In Section 2 we discuss the background and the research methodology adopted. The formal statement of the problem and the proposed notation are presented in Section 3. In Section 4 we discuss the contributions when the operations take place in dedicated machines. In Section 5 we review the research where flexible machines are employed. The contributions dealing with assembly in several (distributed) factories are reviewed in Section 6, while general layout models are discussed 2 in Section 7. Finally, in Section 8 the main conclusions and future research avenues are presented. 2 Background and Research Methodology Many products are composed of assemblies and sub-assemblies. Commonly cited examples in the ASP literature include fire engine production (Lee et al., 1993), assembly flow shop in the computer industry (Potts et al., 1995), assembly of the body and chassis in the car industry (Fattahi et al., 2013b), circuit board production (Cheng and Wang, 1999), or plastic industry (Allahverdi and Aydilek, 2015), among others. Examples can also be found in services/IT, including distributed database systems (Allahverdi and Al-Anzi, 2006b, 2012), or multi-page invoice printing systems (Zhang et al., 2010). The structure of a product can be depicted using an acyclic direct graph or digraph (Kusiak, 1989) where the nodes represent operations and the arcs the precedence relations between the operations (He and Kusiak, 1998). In this manner, the digraph describes the sequence of operations required to complete a product. In this regard, the classification by Kusiak (1989) distinguishes between simple and complex products, the first one being a product that has at most one assembly operation in each level of assembly. However, note that this operation-oriented description of the manufacturing of a job is, in general, different to the resourceoriented description, since the sequence of operations required for a product may be either performed each one by dedicated resources (i.e. machines), or by flexible resources that may carry out several operations. Since scheduling deals with the allocation of operations to resources across time (see e.g. Framinan et al., 2014), the description of the set of resources that can carry out the different operations –i.e. the machine environment– is a critical data that usually determines the difficulty of the scheduling decisions. In this regard, the classical notation for scheduling problems (Graham et al., 1979) focuses on the machine environment rather than solely on the sequence of operations, and this view will also be adopted in this paper for the proposed notation. In the case of assembly operations, such a view naturally leads to a distinction among scheduling using flexible machines (i.e. machines that can carry out several operations on the jobs) and dedicated machines (i.e. machines that can only carry out one and only one type of operation on the job). This distinction will be employed in this review to classify the contributions. Although we retain the term assembly, the review focuses on scheduling problems where some operations may be performed concurrently (i.e. the existence of a set of operations that can be carried out in parallel to be completed before the starting of another operation), which does not necessarily mean a physical assembly. In this regard, papers related to the so-called order scheduling problem are included as a special case of concurrency of operations. In the standard order scheduling problem, a set of orders composed of jobs have to be scheduled in different (usually dedicated) machines in order to minimise some order-related objective. Clearly, these jobs can be modelled as operations that should be completed so the order (a job, in the ASP 3 terminology) is finished. As a consequence, this type of problems can be regarded as assembly problems where the assembly operation has zero processing times, a connection already remarked by Kyparisis and Koulamas (2002). Furthermore, by focusing on the concurrency of operations, the literature on the so-called distributed assembly flowshop scheduling problem can also be integrated, and some insights derived from this connection are discussed in the conclusions. This focus on scheduling with concurrent operations makes the wide range of literature on assembly lines to be out of the scope, as the specific concurrency problem is not dealt with in these papers. Analogously, papers devoted to planning assembly operations (which do not explicitly consider the detailed capacity of the resources) are not included in the review. Finally, we focus the review on papers assuming a deterministic setting. Although a number of papers address the stochastic counterpart, such distinction is customary in most scheduling research, and trying to integrate stochastic assembly scheduling would produce an exceedingly large review. 3 Problem Statement and Proposed Notation The problem can be formalised as follows: Each job j(j= 1, . . . , n) consists of a chain of operations along sstages ({O1 1,j, . . . , O1 r1,j},{O2 1,j, . . . , O2 r2,j},...,{Os 1,j, . . . , Os rs,j}); operation Ok r,j is the rth concurrent operation that should be performed on job jat stage k(rkindicates the number of operations to be carried out at stage k). If there is only one operation at stage k, then the operation sub-index can be dropped, i.e. Ok jindicates the (only) operation to be performed at stage kon job j, that is Ok j=Ok 1,j. Each operation Ok r,j may have technological constraints that impede the starting of the operation unless a set of operations in the previous stages –denoted by A(Ok r,j)– have been completed. Each operation can be classified either as concurrent or merge type (the latter type indicated by an overline) depending on the cardinality of the set A(Ok r,j). If |A(Ok r,j)| ≤ 1, then Ok r,j is of concurrent type. If |A(Ok r,j)|>1, then Ok r,j is of merge type. The scheduling problem is then completely defined by giving, for each machine i, its processing times for each operation pi(Ok r,j). For simplicity, if there is only one machine at stage k, the processing times are denoted by p(Ok r,j). Although not strictly required, we will assume that each machine belongs only to one stage. Some attempts have been made by several researchers to introduce a notation for these types of scheduling problems (most times just covering a subset of assembly scheduling problems), all of them based on the standard 3-field notation by Graham et al. (1979). Although all these proposals have some merits, they are oriented towards specific problem types and do not cover all the extension of ASP. We therefore propose the following notation: If we consider a single-assembly case –i.e. only one operation of merge type–, these layouts can be noted as 4 α1→α2|β|γ where α1is the machine environment prior to the concurrent operation. In this environment, all operations preceding the concurrent operation are performed. α2is the machine environment of the concurrent and subsequent operations. In this environment, assembly and subsequent operations take place. Note that, although in most models the first stage of the α2layout is the assembly stage, it does not always have to be the case, being an example the papers where the components of a product are grouped together to be firstly transported (first stage of α2) and secondly assembled in further stages (successive stages of α2). However, since the collective transportation of the components of the products requires that all of them have been completed, the entity to be processed in α2is the job (with all its operations). The following values for α1can be identified in the literature: •1: Single machine: In this case, the single machine is a flexible machine capable of carrying out all operations of the job to be later assembled. In some papers, such assembly layout with a flexible machine is denoted as agile manufacturing system. •Pm/Qm/Rm:mparallel machines can carry out each one of the operations of the job. Pm assumes identical machines, whereas Qm assumes related machines. Finally, the unrelated parallel machine case is denoted by Rm. Since the machines are flexible, the number of different operations is not limited to the number of machines. •DPm:mdedicated parallel machines carry out a specific operation of the job. Dedicated in this context means that each machine can carry out one and only one specific type of operation. Therefore, a job consists of, at maximum, moperations before being assembled. •Fm: A flowshop consisting of m(flexible) machines can carry out each one of the operations of the job before its assembly. More specifically, all operations prior to the assembly take place in a m-machine flowshop. •DFm:fdedicated m-machine flowshops carry out each one of the operations of the job. In other words, each set of operations prior to the assembly takes place in one specific flowshop layout. Since each flowshop is dedicated to one specific type of operation, the product is composed of, at maximum, fcomponents to be assembled. •PFm:fflexible m-machine flowshops in parallel are able to carry out each one of the operations prior to the assembly of the job. More specifically, the machine environment is composed of f(possibly different) m-machine flowshops, each one capable to carry out all operations of the jobs to be assembled. Therefore, in this case the number of components of the product is not limited to f. 5 (a) DPm →0 layout (b) DPm →1 layout (c) DPm →Pm layout (d) DPm →Fm layout (e) DPm →HFm layout (f) DFm →1 layout Figure 1: Several layouts for the case with dedicated machines prior to the assembly operations. •HFm: The operations prior to the assembly of the jobs take place in a flexible m-stage hybrid flowshop before the assembly. More specifically, all components of the products can be manufactured in the hybrid flowshop. Clearly, the previous values of the α1parameter can also be identified for α2. In addition, α2= 0 means that the processing times of the assembly operation are zero. This may serve to model the order scheduling problem (see Section 4.1). In this problem, a number of orders –each one composed of up to mdifferent products– have to be scheduled in mmachines, where each machine can manufacture only an specific product. Clearly, the order is only completed when all products forming the order have been completed, henceforth it can be seen as an assembly operation with zero-assembly times. Figures 1 and 2 show some samples of the typical layouts, while instance problems for the main layouts and Gantt charts of a sample schedule are provided in the additional on-line material. Regarding the different constraints that may appear in the βfield, we adopt the standard notation trying to make it as clear as possible. Henceforth, the constraints should be interpreted as they apply to some jobs/stages/machines of the process, but not necessarily in all stages/machines. For instance, recrc in the 1→1|recrc|Cmax problem indicates that some jobs –but not all– visit at least one machine –but not all– more than once. Finally, regarding the γfield, the standard notation is adopted, using the extension by T’Kindt and Billaut (2006) for the multicriteria case. A full description of the three fields is given as additional on-line material. 6 (a) 1 →1 layout (b) 1 →Pm layout (c) Pm →1 layout (d) Fm →1 layout (e) PFm→1 layout (f) HFm →A(1) layout Figure 2: Several layouts for the flexible machine case Note that the proposed notation can also model multi-assembly layouts by nesting concurrency arrows in parenthesis: In this manner, the complex layout in Figure 3 can be noted as (((DPm →1, Fm)→Pm),1) → Fm|β|γ. Although we seldom make use of this extended notation in this paper, we believe that this ability to be extended to complex layouts is another interesting feature of the proposed notation. Finally, note that some of the simple layouts described before, such as DP m or DFm, could be denoted also as (1,...,1) →α2, or as (Fm, . . . , Fm)→α2, respectively. However, we believe that DPm and DFm provide a more compact notation and will be used henceforth. Equipped with this notation, we will review the existing contributions in the following sections. Since most of them focus on single-assembly layouts, and given the fact that assembly problems are quite different conceptually depending on whether the operations prior to assembly take place in dedicated machines, or not, Section 4 is devoted to single-assembly scheduling problems with dedicated machines in the α1field. Section 5 is devoted to scheduling problems with flexible machines in the α1field. Section 6 is devoted to distributed assembly problems, and Section 7 discusses general assembly models. To facilitate the study of the different contributions, Tables 1 to 6 are provided as summaries of the different layouts, noting the main focus of the references. The abbreviations used in these tables are: 7 Figure 3: A complex assembly shop layout CA Analysis of the Complexity of the Problem DR Dominance Rules LB Development of Lower Bounds for the problem PP Problem Properties (other than dominance rules/lower bounds) DP Dynamic Programming BB Development of a Branch & Bound procedure PA Proposal of Polynomial-Time Algorithms IP Development of an Integer Programming (Not Linear) model MILP Development of a MILP model QM Development of a quadratic model CH Proposal of Constructive Heuristics MH Proposal of Meta-Heuristics 4 Assembly scheduling with dedicated machine Although different dedicated layouts can be employed to carry out the operations prior to the assembly of the jobs, we are only aware of contributions dealing with dedicated machines in parallel, i.e. the DPm →α2 layout. In this setting, r1the number of concurrent operations in the first stage is assumed to be m. The following subsections discuss the related contributions. 4.1 Order scheduling: DPm →0layout The main contributions regarding this layout –depicted in Figure 1a– are summarised in Table 1. Depending on the objective, the problems have different complexity (see Leung et al., 2005a for a review of the complexity 8 Problem∗Reference Analysis Exact Approximate DP m →0||Cmax Wagneur and Sriskandarajah (1993) CA Leung et al. (2006b) CA CH DP m →0|| PCjWagneur and Sriskandarajah (1993) CA Roemer and Ahmadi (1997) CA Roemer (2006) CA Leung et al. (2005b) PP CH Framinan and Perez-Gonzalez (2017b) CH, MH DP 2→0|| PwjCjSung and Yoon (1998) CA CH DP m →0|| PwjCjWang and Cheng (2003) CH Ahmadi et al. (2005) CA, LB CH Garg et al. (2007) CA CH Wang and Cheng (2007) CH Leung et al. (2007a) CH Leung et al. (2008b) PP CH Wang et al. (2013) QM Shi et al. (2017) QM DP m →0|rj|PwjCjGarg et al. (2007) CA CH DP m →0||Lmax Wagneur and Sriskandarajah (1993) CA DP m →0|| PTjWagneur and Sriskandarajah (1993) CA Lee (2013) PP BB CH Framinan and Perez-Gonzalez (2018) CH, MH DP m →0|learning −eff.|PTjXu et al. (2016) DR BB MH DP m →0|| PUjWagneur and Sriskandarajah (1993) CA Leung et al. (2006b) PP BB CH Lin and Kononov (2007) CA CH DP m →0|| PwjUjLin and Kononov (2007) CA CH DP m →0||(PCA j,PCB j) Lin et al. (2017) DR BB MH DP 2→0||Cost function Li and Ou (2007) CH DP 2→0||Cost function Li and Vairaktarakis (2007) CH DP m →0||F(f1(C1),...,F(fn(Cn)) Cai and Zhou (2004) PP DP Table 1: Summary of contributions in Section 4.1 (∗Notation is described in the additional on-line material) of some of the problems). For makespan minimisation without additional constraints, the problem has been shown to be polynomial by Wagneur and Sriskandarajah (1993), being the makespan value independent of the schedule. The total completion time objective has received a lot of attention: The problem has been first addressed by Wagneur and Sriskandarajah (1993), who showed it to be NP-hard, although their proof contained a flaw and its complexity was not confirmed until Roemer and Ahmadi (1997). Other contributions regarding the complexity of the problem for the weighted case are Ahmadi et al. (2005) and Roemer (2006). Also for the weighted case, the NP-hardness of the specific case of m= 2 was independently established by Sung and Yoon (1998). Regarding exact procedures, Wang et al. (2013) and Shi et al. (2017) propose a quadratic formulation of the weighted case. With respect to approximate procedures, different constructive heuristics have been proposed by Leung et al. (2005b) and by Framinan and Perez-Gonzalez (2017b), the latter being the best procedure with regard to approximate methods. Approximate solutions for the weighted version of the problem are given by Wang and Cheng (2003); Ahmadi et al. (2005); Garg et al. (2007); Leung et al. (2007a); Wang and Cheng (2007) and Leung et al. (2008b), although only the paper by Ahmadi et al. (2005) addresses a computational experience to test the performance of the proposed heuristics, which are not compared with other available heuristics. The rest of the papers are devoted to establishing the worst-case performance of 9 after the assembly of the product. The literature on the so-called Differentiation Scheduling Problem (DSP) is relatively abundant, although this problem is usually treated in isolation of the previous assembly problem and, to the best of our knowledge, the only reference addressing scheduling problems in this layout is Xiong et al. (2015), who propose an MILP model as well as some constructive heuristics and metaheuristics. 5 Assembly scheduling with flexible machines In this section we review the problems involving machines capable of performing multiple operations. Depending on the layout, a solution would be given by solving an integrated assignment and scheduling problem. As in Section 4, in the next subsections we discuss a number of cases depending on the layout for the operations prior to the assembly. Furthermore, we present some results not provided in the literature in order to contribute to the classification of these types of problems. 5.1 Single machine prior to assembly: 1→α2layout When a single machine is used for operations prior to the assembly, the possibility of performing these operations in a concurrent manner is not available, so they all have to be sequenced on this machine. Depending on the number of machines used for assembly in the second stage, some results can be stated regarding the properties of different scheduling problems. Therefore, we first present the general results. Theorem 5.1. In a 1→1layout, for a given sequence of jobs Π := (π1, . . . , πn)in the second (assembly) stage, the best value of any regular objective function f(Cj)is obtained if all operations in the first stage of each job in Πare carried out consecutively. Proof. Without loss of generality, we assume the following sequence of jobs on the second machine: (1,2, . . . , j, . . . , n). Let us assume that on the first machine, not all rjoperations of job jare carried out one after another, but the l-th operation of job j+1 is carried out after the k−1-th operation of job jand before the k-th operation of job j, i.e. the sequence of operations on the first machine is ...,O1 k−1,j, O1 l,j+1, O1 k,j, . . .. We prove the theorem by contradiction, showing that it is not possible to obtain lower values of the completion times of jand j+ 1 than those obtained if all operations of jare carried out one after another (i.e. in a batch). Let S1be the starting time of the first operation of jin the first stage. Then Cj,1the completion time of all operations of job jon the first machine is: Cj,1=S1+X u<k p(O1 uj) + p(O1 l,j+1) + X u≥k p(O1 uj) = S1+ rj X u=1 p(O1 uj) + p(O1 l,j+1) 16 And Cj+1,1the completion time of all operations of job j+ 1 on the first machine: Cj+1,1=Cj,1+X u6=l p(O1 u,j+1) = S1+ rj X u=1 p(O1 uj) + rj+1 X u=1 p(O1 u,j+1) Regarding the second machine: Cj=Cj,2= max{S1+p(¯ O2 j−1); Cj,1}+p(¯ O2 j) = S1+ max{p(¯ O2 j−1); rj X u=1 p(O1 uj) + p(O1 l,j+1)}+p(¯ O2 j) And, for job j+ 1: Cj+1 =Cj+1,2= max{Cj;Cj+1,1}+p(¯ O2 j+1) In contrast, if all operations of job jare carried out in a batch and are immediately followed by the operations of job j+ 1, then on the first machine we have: C∗ j,1=S1+ rj X u=1 p(O1 uj) and C∗ j+1,1=C∗ j,1+ rj+1 X u=1 p(O1 u,j+1) = S1+ rj X u=1 p(O1 uj) + rj+1 X u=1 p(O1 u,j+1) = Cj+1,1 The completion times on the second machine would be: C∗ j=C∗ j,2= max{S1+p(¯ O2 j−1); C∗ j,1}+p(¯ O2 j) = S1+ max{p(¯ O2 j−1); rj X u=1 p(O1 uj)}+p(¯ O2 j) and C∗ j+1 =C∗ j+1,2= max{C∗ j;C∗ j+1,1}+p(¯ O2 j+1) = max{C∗ j;Cj+1,1}+p(¯ O2 j+1) As it can be seen, C∗ j≤Cj(indeed C∗ j< Cjunless operation lof job j+ 1 in the first stage takes zero time units to complete, i.e. p(O1 l,j+1) = 0), and, as a consequence, C∗ j+1 ≤Cj+1. In addition, the completion times of the rest of the jobs do not change, therefore any regular objective function would yield a lower value for C∗than for C. This proves that there is no advantage in considering not to carry out all operations of the same job in a batch at the first stage. 17 From Theorem 5.1, two corollaries follow: Corollary 5.1.1. For any regular objective f(Cj), the 1→1||f(Cj)problem is equivalent to the F2||f(Cj) problem, where pjk the processing times of job jon kmachine of the latter problem are given by: pj1= rj X u=1 p(O1 uj) and pj2=p(O2 1j) Proof. Trivial from Theorem 5.1. Corollary 5.1.2. For any regular objective f(Cj), the 1→0||f(Cj)problem is equivalent to the 1||f(Cj) problem, where pjthe processing times of each job in the latter problem are given by: pj= rj X u=1 p(O1 uj) Proof. Trivial from Theorem 5.1. The corollaries also serve to establish the connection between the flexible and dedicated machines assembly settings, as it can be seen in Figure 4. We are not aware of contributions explicitly addressing the results in the theorem and corollaries. However, some specific cases have been mentioned regarding Corollary 5.1.1: Cheng and Wang (1999) state that, for the makespan objective and the assembly scheduling problem with two components for each job, the problem can be solved by Johnson’s algorithm if there is no commonality of the components. Also Property 2 in Liao et al. (2015) states that the 1 →1|BSj|Cmax problem is equivalent to F2||Cmax if setup times are zero. Due to the high number of works analysing the 1 →α2setting, the existing contributions have been divided depending on the layout of the assembly stages. These are discussed in the next sections and are summarised in Table 4. 5.1.1 No assembly stage: 1→0layout As it can be seen from Figure 4, many standard settings in the 1 →0 layout are polynomially solvable as it is equivalent to the single machine case if a regular objective is considered and no additional constraints are assumed. Therefore, existing contributions focus on problems with specific constraints, most of them related to the existence of the requirement of batch-processing certain types of components, which excludes the possibility of carrying out all operations of a job consecutively and therefore Theorem 5.1 may not be applicable. 18 Figure 4: Complexity depending on the layout (non-assembly layouts in grey boxes). To the best of our knowledge, the first reference on this layout is Liao and Chuang (1996), who consider the problem with setup times and an -constrained approach where the objectives are the minimisation of the set-up times subject to a maximum number of tardy jobs, or a maximum tardiness. A number of problem properties and B & B algorithms are presented. A specific case of this layout is addressed by Gerodimos et al. (2000): In their problem, each job is composed of two components (standard and customised), with the standard component being processed in batches. There are setup times for changing from a standard component to a customised one, and between customised components of different products. Furthermore, there is a batch availability constraint. The authors show this setting to be NP-hard for the number of late jobs, a problem for which they develop dynamic programming procedures. A version with more than two components is presented in Gerodimos et al. (1999), where the complexity of the problem for maximum lateness and for the weighted sum of tardy jobs are established. Additionally, in the case where the operations of jobs belonging to the same family have to be sequenced together –a constraint that the authors label as group technology– is studied. Another specific problem within this layout is presented in Shi et al. (2018), where orders composed of several products belonging to different product families have to be processed in batches and there are incompatible job families, i.e. products from different families cannot be in the same batch. The problem is shown to be solvable for the makespan case, whereas for the weighted total completion time the authors 19 Problem∗Reference Analysis Exact Approximate 1→0|BSsd|(T S, Tmax) Liao and Chuang (1996) PP BB 1→0|BSsd|(T S, PUj) Liao and Chuang (1996) PP BB 1→0|BS, ba, nc = 2|Lmax Gerodimos et al. (2000) PP DP 1→0|BS, ba, nc = 2|PUjGerodimos et al. (2000) PP,CA DP 1→0|BS|Lmax Gerodimos et al. (1999) PP, CA 1→0|BS|PwjUjGerodimos et al. (1999) PP, CA DP 1→0|BS|PCjNg et al. (2002) CA Erel and Ghosh (2007) CA DP 1→0|BS, group −technology|PCjGerodimos et al. (1999) PP, CA DP Ng et al. (2002) CA Hazir et al. (2008) MILP MH 1→0|BS|GP (Cmax, T CC) Gupta et al. (1997) PP, CA PA 1→0|BS|GP (T CC, Cmax) Gupta et al. (1997) PP, CA PA 1→0|p−batch, incompt|Cmax Shi et al. (2018) PP PA 1→0|p−batch, incompt|PwjCjShi et al. (2018) PP CH 1→1|n= 1, recrc −sas|Cmax Kusiak (1989) PP, CA 1→1|n= 1, recrc −sas, product −batch|Cmax Kusiak (1989) CH 1→1|recrc −sas|Cmax Kusiak (1989) PP, CA 1→1|recrc −sas, product −batch|Cmax Kusiak (1989) CH 1→1|BS, ba, nc = 2|Cmax Cheng and Wang (1999) PP, CA DP (special cases) Lin and Cheng (2002) CA 1→1|BS, nc = 2|Cmax Cheng and Wang (1999) PP, CA DP (special cases) Lin and Cheng (2002) CA 1→1|deteriorating, BS|Cmax Jung and Kim (2016) MILP 1→1|pm, deteriorating, BS|Cmax Jung and Kim (2016) MILP 1→1|BS|Cmax Liao et al. (2015) MILP CH 1→1|BS|Cmax Jung et al. (2017) MILP MH 1→1|BScomponent, product −batch|PCjYokoyama (2004) PP CH 1→P m|n= 1, recrc −sas|Cmax He and Babayan (2002) CA MILP 1→P m|complex|Cmax He and Babayan (2002) MILP CH Gaafar and Masoud (2005) MH Liao and Liao (2008) BB MH Gaafar et al. (2008) MH Teymourian et al. (2016) MH Table 4: Summary of contributions in Section 5.1 (single machine processing).(∗Notation is described in the additional on-line material). propose a constructive heuristic. The NP-hardness of the problem with total completion time assuming setup times among families of products is established by Ng et al. (2002) and Erel and Ghosh (2007) independently. The latter authors also propose a dynamic programming algorithm. Finally, Hazir et al. (2008) propose an MILP and several metaheuristics for this problem. The problems 1 →0|BSj|GP(Cmax, TCC) and 1 →0|BSj|GP(TCC, Cmax) where T CC denotes the total carrying costs are addressed by Gupta et al. (1997), who study their complexity, derive some properties and propose some constructive heuristics. A specific case of this problem that will not be treated here is given by the so-called multiple orders per job scheduling problem (see e.g. Laub et al., 2007). This problem arises in the semiconductor manufacturing and TFT-LCD industries, where a number of orders –possibly belonging to different customers– should be grouped together in special transfer facilities (FOUPs) to be processed as a batch (either p-batch or s-batch). Therefore, the problems of simultaneously grouping the orders into FOUPs and scheduling them have to be 20 addressed. Although this problem is a particular case of the order scheduling problem, in view of its very specific features, it is not addressed here and the reader is referred to e.g Mason and Chen (2010) for a recent paper on the topic. 5.1.2 Single machine for assembly: 1→1layout All except one of the references involve the makespan as objective (see Table 4). To the best of our knowledge, the first reference on this layout is Kusiak (1989), who addresses the problems of scheduling a single product, and several products with or without batches. The jobs may require several steps of manufacturing and assembly, which can be modelled with recirculation constraints, i.e.: the 1 →1|recrc −sas|Cmax or 1 → 1|recrc −sas, product −batch|Cmax problems. For the problem without batches, Kusiak (1989) develops an optimal algorithm. In the light of Theorem 5.1, this algorithm is an extension for the recirculation case of the well-known Johnson’s algorithm for the F2||Cmax problem, although we are not aware that this aspect is mentioned by the author. For the problems with batches, the author proposes some constructive heuristics. Cheng and Wang (1999) address the scheduling of jobs consisting of two components, a unique component for each product and a common component for all products, the latter being produced in batches with a setup time. The authors show that the problem is NP-hard, and identify properties to reduce the search space, as well as specific cases of the problem that are polynomially solvable. Lin and Cheng (2002) develop further results on the complexity of these problems and prove that they are strongly NP-hard. Jung and Kim (2016) propose MILP models and constructive heuristics for the problems with makespan objective with/without preventive maintenance activities, batch setups and deterioration rates. Liao et al. (2015) propose an MILP model and some properties for the problem based on Jonhson’s algorithm for the 1 →1|BS|Cmax problem, also addressed by Jung et al. (2017) when the number of components of the jobs is dynamic, constant setup times, and product batches. An MILP model and a genetic algorithm are proposed. Finally, Yokoyama (2004) addresses the problem with completion time as objective in the case of setups in the manufacturing machine, i.e. the 1 →1|BScomponent, product −batch|PCjproblem. This author analyses some properties of the problem and proposes a constructive heuristic. 5.1.3 Parallel machines for assembly: 1→Pm layout Note that, for this layout, it is not possible to establish that carrying out all operations of a job consecutively in the first machine will produce better schedules for a regular objective function. We are only aware of papers studying the makespan objective in this layout (see Table 4). This problem is NP-hard (see Figure 4 and note that Pm||Cmax is already NP-hard). He and Babayan (2002) are the first to analyse the problem 21 of single and n-job scheduling with and without multiple assembly operations (which involves recirculation and precedence constraints). They show that the single-job problem with simple assembly is polynomially solvable, and show some equivalences among the other problems, proposing an MILP model, a lower bound, and some constructive heuristics. Some metaheuristics for this problem are proposed by Gaafar and Masoud (2005), which are outperformed by Liao and Liao (2008). These authors also propose a B & B algorithm for the problem. Independently, Gaafar et al. (2008) and Teymourian et al. (2016) propose additional metaheuristics. It is relevant to mention that only partial comparisons among these metaheuristics have been carried out, so the state-of-the-art regarding approximate methods for the problem is unclear. 5.2 Parallel machines prior to assembly: Pm/Rm/Qm →α2layout In view of the existing contributions (summarised in Table 5), we discuss the cases where there is no processing at the assembly stage in Section 5.2.1 , whereas the rest of the cases are discussed in Section 5.2.2. Problem∗Reference Analysis Exact Approximate P2→0|| PCjYang (2005) CA Yang and Posner (2005) PP CH P m →0|p−batch, incompt|Cmax Shi et al. (2018) PP CH P m →0|| PCjBlocher and Chhajed (1996) PP, CA MILP CH Yang (2005) CA Yang and Posner (2005) PP CH P m →0|pj= 1|PCjBlocher and Chhajed (1996) CA Yang (2005) CA P m →0|pj= 1|Lmax Yang (2005) CA P m →0|pj= 1|PwjCjYang (2005) CA P m →0|| PwjCjLeung et al. (2006a) CH Leung et al. (2008b) CH P m →0|prmpt|PwjCjLeung et al. (2008a) CA CH P m →0|p−batch, incompt|PwjCjShi et al. (2018) MILP MH P m →0||Lmax Su et al. (2013) CH Rm →0|split|PCjXu et al. (2015) PP MILP CH Qm →0|| PwjCjLeung et al. (2007b) CH Qm →0|pmtn|PwjCjLeung et al. (2007b) CH Rm →0|dj=d|PUjNg et al. (2003) CA Rm →0|dj=d|PwjUjNg et al. (2003) CA CH P m →1|recrc|Cmax He et al. (2001) MILP P m →1|recrc −complex|Cmax MILP CH Rm →1|BSsd|Cmax Kheirandish et al. (2015) MILP MH Qm →1||Cmax Koulamas and Kyparisis (2007) PP CH P m →P m||Fl(JIT, mean longest waiting duration) Chen et al. (2015) MILP MH Rm →DF 2|STsd|Fl(PwjE2 j,PwjT2 j,PUj, Cmax) Dalfard et al. (2011) MILP MH Table 5: Summary of contributions in Section 5.2 (parallel flexible machines). (∗Notation is described in the additional on-line material). 5.2.1 Flexible Order scheduling: Pm/Rm/Qm →0layout The complexity of a number of problems in the Pm →0 layout is established by Yang (2005), some of them with specific constraints (see Table 5). His results prove that most of the problems are NP-hard even for 22 2 machines and unit processing times, with the exception of the maximum lateness and sum of completion times for unit processing times. The first reference for the problem with total completion time objective is by Blocher and Chhajed (1996), who present some properties of the problem (such as an optimal procedure for the pj= 1 case), an MILP model, and propose constructive heuristics. Yang and Posner (2005) present some heuristics for the Pm →0|| PjCjproblem, together with their worst case bounds. Xu et al. (2015) address the Rm →0|| PCj problem where each component can be split arbitrarily into continuous sublots. Several problem properties and heuristics with their worst case bounds are presented. Leung et al. (2007b) address the Qm →0|| PwjCj with and without preemption, proposing some heuristics and giving their worst case. Leung et al. (2006a, 2008b) propose several heuristics for the Pm →0|| PjwjCj. Leung et al. (2008a) study the same problem where preemption is allowed. The complexity of the problem is analysed, and some heuristics are presented. For the specific problem of parallel batch machines with incompatible product families, Shi et al. (2018) study the objectives of makespan and weighted total completion time minimisation. A constructive heuristic based on some problem properties is proposed for the first objective, whereas a MILP model and a metaheuristic are presented for the second. Regarding due-date related objectives, Su et al. (2013) address the problem for the maximum lateness, presenting a set of constructive heuristics together with their worst case lower bounds. Ng et al. (2003) address the Pm →0|| PwjUjproblem when dj=dand pij ∈ {0,1}. They show that the problem is NP-hard even when wj= 1. They propose an approximate algorithm with its worst case lower bound. 5.2.2 One or more machines for assembly: Pm/Rm/Qm →α2layout (α26= 0) The contributions on this layout are rather scarce as compared with other problem types (see summary in Table 5). Regarding the case with a single machine for assembly, the Pm →1|recrc|Cmax problem has been first addressed by He et al. (2001), who analyse the cases of single and multiple job product with simple/complex assembly. They propose MILP models, some equivalence properties, and constructive heuristics. Without recirculation, Kheirandish et al. (2015) address the Rm →1|BSsd, product−batch|Cmax problem, for which the authors formulate an MILP model and a metaheuristic. Finally, an asymptotically optimal heuristic for the Qm →1||Cmax problem is given by Koulamas and Kyparisis (2007). With respect to the case where the assembly takes place in parallel machines, Chen et al. (2015) propose an MILP model and a metaheuristic for the case where orders are composed of several jobs (which in turn are composed of several components), with the bi-objective of the weighted mean tardiness and earliness, and the mean longest waiting time of the order. Dalfard et al. (2011) address the Rm →DF2|STsd|Fl(PwjT2 j,PwjE2 j, Cmax,PUj) problem. An MILP 23 model and metaheuristics are proposed for the problem. 5.3 Flowshop-type prior to assembly: Fm/PFm/HFm →α2layout Problem∗Reference Analysis Exact Approximate F2→1|| PwjCjYokoyama and Santos (2005) PP BB F2→1|prmu|PwjCjYokoyama and Santos (2005) PP BB F m →1|recrc −complex, prmu, ba|PwjCjYokoyama (2001) BB F m →1|prmu, product-batch, BSij |PCjYokoyama (2008) PP, LB BB CH P F m →1|prmu|Cmax Hatami et al. (2013) MILP MH Hatami et al. (2014b) CH Li et al. (2015) MH P F m →1|prmu, STsd|Cmax Hatami et al. (2014a) CH Hatami et al. (2015b) CH, MH HF 2, P m, P m →1||Cmax Fattahi et al. (2013b) PP MILP CH Shan et al. (2014) MILP Komaki et al. (2016) PP MILP CH, MH HF 2,1, P m →P m|BSij , product −batch|Cmax Fattahi et al. (2013a) PP MH HF 2, P m, P m →1|BSij |Cmax Fattahi et al. (2014) BB MH HF 2, Qm, 1→DP 2|STsd, product −batch|Cmax Nikzad et al. (2015) MILP MH HF m, P m1...PmS→P mA|recrc −complex|Cmax Mahdavi et al. (2011) MILP CH, MH Table 6: Summary of contributions in Section 5.3 (flowshop-type layout prior to assembly). (∗Notation is described in the additional on-line material). This layout corresponds to Figure 2d in the case of a flowshop, to Figure 2e in the case of a parallel flowshop, and to Figure 2f in the case of a hybrid flowshop. These types of problems are NP-complete for any objective even for the F2→1 layout, as the latter can be seen as a generalisation of the three-machine flowshop (see Figure 4). In Table 6 we summarise the main contributions. Regarding the flowshop layout in the α1field, to the best of our knowledge, the problem has been addressed only by Yokoyama (2001), Yokoyama and Santos (2005) and Yokoyama (2008). In Yokoyama and Santos (2005), the authors propose a B & B procedure for the F2→1|| PwjCjproblem with and without the permutation constraint. Yokoyama (2008) addresses the Fm →1|prmu, product −batch, BSij |PCj problem, deriving some approximate procedures and lower bounds. Finally, Yokoyama (2001) addresses a specific case of Fm →1|recrc −complex, prmu, ba|PwjCjusing a B & B procedure. Regarding the case of the parallel flowshop in the α1field, perhaps the best-known case is the PFm→1 layout, which is also called distributed assembly scheduling problem. The problem has been addressed just for the makespan objective, Hatami et al. (2013) and Hatami et al. (2014b) being the first works describing the problem and proposing an MILP and a metaheuristic, and constructive heuristics respectively. Li et al. (2015) address the same problem and propose a genetic algorithm that compares favourably to the constructive heuristics by Hatami et al. (2014b). Finally, constructive heuristics and metaheuristics for the PFm → 1|prmu, STsd|Cmax are proposed in Hatami et al. (2014a) and in Hatami et al. (2015b) respectively. Finally, regarding the hybrid flowshop, to the best of our knowledge, it has been addressed first by Fattahi et al. (2013b), who tackle the HF2, Pm1, . . . , PmS→1||Cmax problem. These authors propose an 24 MILP model and constructive heuristics. However, the MILP model contains a mistake which is fixed by Shan et al. (2014). The heuristics proposed by Fattahi et al. (2013b) are outperformed by a metaheuristic proposed by Komaki et al. (2016), who also propose some constructive heuristics for the problem. Two extensions of the previous problem are presented by Fattahi et al. (2013a) and Fattahi et al. (2014). The first reference proposes metaheuristics for the case with machine dependent setups and product-batch restrictions, whereas in the second reference a branch and bound and a metaheuristic are proposed for the problem with machine dependent setups. The HF2, Qm, 1→DP2|STsd, product −batch|Cmax problem is studied by Nikzad et al. (2015), who propose an MILP model and several metaheuristics. Finally, a multi-level assembly case is addressed by Mahdavi et al. (2011), where the authors process the components of a product in a hybrid flowshop followed by several stages of subassemblies and assemblies with the objective of makespan minimisation. This problem can be regarded as HFm →1|recrc|Cmax to model the recirculation required in the assembly stage. The problem is modelled using an MILP, and some heuristics and metaheuristics are proposed. 6 Distributed assembly scheduling In this section we review the contributions related to scheduling jobs using different assembly layouts. Note that here distributed has a different meaning than in the so-called distributed assembly flowshop layout, as in the latter case the assembly operation is not distributed at all. Therefore, in this problem there are several identical ffactories, each one consisting of an assembly layout, so the problem is to schedule all jobs in these settings, which includes the assignment of jobs to the factories and the scheduling of these jobs within the factories. Using the notation proposed in Section 3, the layout of this type of problem can be denoted as (α1→α2)→0, where the term within parentheses indicates the layout of each identical factory. To the best of our knowledge, the only type of problem addressed is to schedule jobs over distributed factories consisting of dedicated parallel machines and a single assembly stage. More specifically, the (DPm → 1) →0 layout has been addressed for the following objectives: •Makespan: This objective was first addressed by Deng et al. (2016), proposing an MILP model for the problem and a metaheuristic (Memetic algorithm). •Total Completion Time. This problem is addressed by Xiong et al. (2014), who present several metaheuristics for the problem with setups, i.e. the (DPm →1) →0|BSj|PCjproblem. •Biobjective: Xiong and Xing (2014) address the (DPm →1) →0|BSj|Fl(Cmax,PCj) problem, proposing a genetic algorithm and a variable local search. However, these algorithms are not compared 25 Haouari, M. and Daouas, T. (1999). Optimal scheduling of the 3-machine assembly-type flowshop. RAIRO Recherche Operationnelle, 33(4):439–445. Hariri, A. and Potts, C. (1997). A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational Research, 103(3):547–556. Hatami, S., Ebrahimnejad, S., Tavakkoli-Moghaddam, R., and Maboudian, Y. (2010). Two meta-heuristics for three-stage assembly flowshop scheduling with sequence-dependent setup times. International Journal of Advanced Manufacturing Technology, 50(9-12):1153–1164. Hatami, S., Ruiz, R., and Andres-Romano, C. (2013). The distributed assembly permutation flowshop scheduling problem. International Journal of Production Research, 51(17):5292–5308. Hatami, S., Ruiz, R., and Andres-Romano, C. (2014a). Simple constructive heuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times. In Proceedings- 2014 International Conference on Control, Decision and Information Technologies, CoDIT2014, pages 19–23. Hatami, S., Ruiz, R., and Andres-Romano, C. (2015a). The distributed assembly parallel machine scheduling problem with eligibility constraints. International Journal of Production Management and Engineering, 3(1):13–23. Hatami, S., Ruiz, R., and Andres-Romano, C. (2015b). Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times. International Journal of Production Economics, 169:76–88. Hatami, S., Ruiz, R., and Andres-Romano, C. (2016). Heuristics for a distributed parallel machine assembly scheduling problem with eligibility constraints. In Proceedings of 2015 International Conference on Industrial Engineering and Systems Management, IEEE-IESM2015, pages 145–153. Hatami, S., Ruiz, R., and Romano, C. (2014b). Two simple constructive algorithms for the distributed assembly permutation flowshop scheduling problem. In Hernandez, C., Lopez-Paredes, A., and Perez- Rios, J. M., editors, Managing Complexity, pages 139–145. Springer. Hazir, ¨ O., G¨unalay, Y., and Erel, E. (2008). Customer order scheduling problem: A comparative metaheuristics study. International Journal of Advanced Manufacturing Technology, 37(5-6):589–598. He, D. and Babayan, A. (2002). Scheduling manufacturing systems for delayed product differentiation in agile manufacturing. International Journal of Production Research, 40(11):2461–2481. He, D., Babayan, A., and Kusiak, A. (2001). Scheduling manufacturing systems in an agile environment. Robotics and Computer-Integrated Manufacturing, 17(1-2):87–97. He, D. and Kusiak, A. (1998). Designing an assembly line for modular products. Computers and Industrial Engineering, 34(1):37–52. Hwang, F. and Lin, B. (2012). Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence. Journal of the Operational Research Society, 63(6):839–845. Jung, S. and Kim, B. (2016). Novel mathematical models for two-stage assembly flow shop scheduling problem with deterioration and preventive maintenance activities. ICIC Express Letters, Part B: Applications, 7(11):2477–2482. Jung, S., Woo, Y.-B., and Kim, B. (2017). Two-stage assembly scheduling problem for processing products with dynamic component-sizes and a set up time. Computers and Industrial Engineering, 104:98–113. Karuno, Y. and Nagamochi, H. (2002). A better approximation for the two-stage assembly scheduling problem with two machines at the first stage. Lecture Notes in Computer Science, 2518 LNCS:199–210. 32 Kheirandish, O., Tavakkoli-Moghaddam, R., and Karimi-Nasab, M. (2015). An artificial bee colony algorithm for a two-stage hybrid flowshop scheduling problem with multilevel product structures and requirement operations. International Journal of Computer Integrated Manufacturing, 28(5):437–450. Khodke, P. and Bhongade, A. (2013). Real-time scheduling in manufacturing system with machining and assembly operations: A state of art. International Journal of Production Research, 51(16):4966–4978. Kolisch, R. and Hess, K. (2000). Efficient methods for scheduling make-to-order assemblies under resource, assembly area and part availability constraints. International Journal of Production Research, 38(1):207– 228. Komaki, G. and Kayvanfar, V. (2015). Grey wolf optimizer algorithm for the two-stage assembly flowshop scheduling problem with release time. Journal of Computational Science, 8:109–120. Komaki, G., Teymourian, E., and Kayvanfar, V. (2016). Minimising makespan in the two-stage assembly hybrid flow shop scheduling problem using artificial immune systems. International Journal of Production Research, 54(4):963–983. Komaki, G., Teymourian, E., Kayvanfar, V., and Booyavi, Z. (2017). Improved discrete cuckoo optimization algorithm for the three-stage assembly flowshop scheduling problem. Computers and Industrial Engineering, 105:158–173. Koulamas, C. and Kyparisis, G. (2001). The three-stage assembly flowshop scheduling problem. Computers and Operations Research, 28(7):689–704. Koulamas, C. and Kyparisis, G. (2007). A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines. European Journal of Operational Research, 182(2):945–951. Kovalyov, M., Potts, C., and Strusevich, V. (2004). Batching decisions for assembly production systems. European Journal of Operational Research, 157(3):620–642. Kusiak, A. (1989). Aggregate scheduling of a flexible machining and assembly system. IEEE Transactions on Robotics and Automation, 5(4):451–459. Kyparisis, G. and Koulamas, C. (2002). Assembly line scheduling with concurrent operations and parallel machines. INFORMS Journal on Computing, 14(1):68–80. Laub, J., Fowler, J., and Keha, A. (2007). Minimizing makespan with multiple-orders-per-job in a twomachine flowshop. European Journal of Operational Research, 182(1):63–79. Lee, C.-Y., Cheng, T., and Lin, B. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science, 39(5):616–625. Lee, I. S. (2013). Minimizing total tardiness for the order scheduling problem. International Journal of Production Economics, 144(1):128–134. Lee, J.-Y. and Bang, J.-Y. (2016). A two-stage assembly-type flowshop scheduling problem for minimizing total tardiness. Mathematical Problems in Engineering, 2016:6409321. Leung, J., Li, H., and Pinedo, M. (2005a). Order scheduling models: An overview. Multidisciplinary Scheduling: Theory and Applications, pages 37–53. Leung, J. Y.-T., Lee, C., Ng, C., and Young, G. (2008a). Preemptive multiprocessor order scheduling to minimize total weighted flowtime. European Journal of Operational Research, 190(1):40–51. Leung, J. Y. T., Li, H., and Pinedo, M. (2005b). Order Scheduling in an Environment with Dedicated Resources in Parallel. Journal of Scheduling, 8(5):355–386. 33 Leung, J. Y.-T., Li, H., and Pinedo, M. (2006a). Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel. Naval Research Logistics, 53(4):243–260. Leung, J. Y.-T., Li, H., and Pinedo, M. (2006b). Scheduling orders for multiple product types with due date related objectives. European Journal of Operational Research, 168(2):370–389. Leung, J. Y. T., Li, H., and Pinedo, M. (2007a). Scheduling orders for multiple product types to minimize total weighted completion time. Discrete Applied Mathematics, 155(8):945–970. Leung, J. Y. T., Li, H., and Pinedo, M. (2008b). Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time. Annals of Operations Research, 159(1):107–123. Leung, J. Y.-T., Li, H., Pinedo, M., and Zhang, J. (2007b). Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines. Information Processing Letters, 103(3):119–129. Li, C.-L. and Ou, J. (2007). Coordinated scheduling of customer orders with decentralized machine locations. IIE Transactions (Institute of Industrial Engineers), 39(9):899–909. Li, C.-L. and Vairaktarakis, G. (2007). Coordinating production and distribution of jobs with bundling operations. IIE Transactions (Institute of Industrial Engineers), 39(2):203–215. Li, X., Zhang, X., Yin, M., and Wang, J. (2015). A genetic algorithm for the distributed assembly permutation flowshop scheduling problem. In 2015 IEEE Congress on Evolutionary Computation, CEC2015- Proceedings, pages 3096–3101. Liao, C.-J. and Chuang, C.-H. (1996). Sequencing with setup time and order tardiness trade-offs. Naval Research Logistics, 43(7):971–984. Liao, C.-J., Lee, C.-H., and Lee, H.-C. (2015). An efficient heuristic for a two-stage assembly scheduling problem with batch setup times to minimize makespan. Computers and Industrial Engineering, 88:317– 325. Liao, C.-J. and Liao, C.-C. (2008). An ant colony optimisation algorithm for scheduling in agile manufacturing. International Journal of Production Research, 46(7):1813–1824. Lin, B. and Cheng, T. (2002). Fabrication and assembly scheduling in a two-machine flowshop. IIETransactions (Institute of Industrial Engineers), 34(11):1015–1020. Lin, B., Cheng, T., and Chou, A. (2006). Scheduling in an assembly-type production chain with batch transfer. Omega, 35(2):143–151. Lin, B. and Kononov, A. (2007). Customer order scheduling to minimize the number of late jobs. European Journal of Operational Research, 183(2):944–948. Lin, W.-C., Yin, Y., Cheng, S.-R., Cheng, T., Wu, C.-H., and Wu, C.-C. (2017). Particle swarm optimization and opposite-based particle swarm optimization for two-agent multi-facility customer order scheduling with ready times. Applied Soft Computing Journal, 52:877–884. Liu, C.-H. (2009). Lot streaming for customer order scheduling problem in job shop environments. International Journal of Computer Integrated Manufacturing, 22(9):890–907. Maboudian, Y. and Shafaei, R. (2009). Modeling a bi-criteria two stage assembly flow shop scheduling problem with sequence dependent setup times. In IEEM2009 - IEEE International Conference on Industrial Engineering and Engineering Management, pages 1748–1752. Mahdavi, I., Komaki, G., and Kayvanfar, V. (2011). Aggregate hybrid flowshop scheduling with assembly operations. In 2011 IEEE 18th International Conference on Industrial Engineering and Engineering Management, IEandEM2011, number PART 1, pages 663–667. 34 Maleki-Daronkolaei, A. and Seyedi, I. (2013). Taguchi method for three-stage assembly flow shop scheduling problem with blocking and sequence-dependent set up times. Journal of Engineering Science and Technology, 8(5):603–622. Maleki-Darounkolaei, A., Modiri, M., Tavakkoli-Moghaddam, R., and Seyyedi, I. (2012). A three-stage assembly flow shop scheduling problem with blocking and sequence-dependent set up times. Journal of Industrial Engineering International, 8(1):1–7. Mason, S. and Chen, J.-S. (2010). Scheduling multiple orders per job in a single machine to minimize total completion time. European Journal of Operational Research, 207(1):70–77. Mozdgir, A., FatemiGhomi, S., Jolai, F., and Navaei, J. (2013a). Two-stage assembly flow-shop scheduling problem with non-identical assembly machines considering setup times. International Journal of Production Research, 51(12):3625–3642. Mozdgir, A., Ghomi, S., Jolai, F., and Navaei, J. (2013b). Three meta-heuristics to solve the no-wait two-stage assembly flow-shop scheduling problem. Scientia Iranica, 20(6):2275–2283. Navaei, J., FatemiGhomi, S., Jolai, F., and Mozdgir, A. (2014). Heuristics for an assembly flow-shop with non-identical assembly machines and sequence dependent setup times to minimize sum of holding and delay costs. Computers and Operations Research, 44:52–65. Navaei, J., FatemiGhomi, S., Jolai, F., Shiraqai, M., and Hidaji, H. (2013). Two-stage flow-shop scheduling problem with non-identical second stage assembly machines. International Journal of Advanced Manufacturing Technology, 69(9-12):2215–2226. Navaei, J., Mozdgir, A., and Hidaji, H. (2010). Two-stage assembly flow-shop scheduling problem with bi-objective of number of tardy and makespan minimization. In Proceedings of the 2010 International Conference on Artificial Intelligence, ICAI2010, volume 2, pages 704–709. Nejati, M., Mahdavi, I., Hassanzadeh, R., and Mahdavi-Amiri, N. (2016). Lot streaming in a two-stage assembly hybrid flowshop scheduling problem with a work shift constraint. Journal of Industrial and Production Engineering, 33(7):459–471. Ng, C., Cheng, T., and Yuan, J. (2002). Strong np-hardness of the single machine multi-operation jobs total completion time scheduling problem. Information Processing Letters, 82(4):187–191. Ng, C., Cheng, T., and Yuan, J. (2003). Concurrent open shop scheduling to minimize the weighted number of tardy jobs. Journal of Scheduling, 6(4):405–412. Nikzad, F., Rezaeian, J., Mahdavi, I., and Rastgar, I. (2015). Scheduling of multi-component products in a two-stage flexible flowshop. Applied Soft Computing Journal, 32:132–143. Perez-Gonzalez, P. and Framinan, J. (2014). A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems. European Journal of Operational Research, 235(1):1–16. Pongcharoen, P., Hicks, C., Braiden, P., and Stewardson, D. (2002). Determining optimum genetic algorithm parameters for scheduling the manufacturing and assembly of complex products. International Journal of Production Economics, 78(3):311–322. Potts, C., Savast’janov, S., Strusevich, V., Van Wassenhove, L., and Zwaneveld, C. (1995). The two-stage assembly scheduling problem: Complexity and approximation. Operations Research, 43(2):346–355. Roach, A. and Nagi, R. (1996). A hybrid GA - SA algorithm for Just-in-Time scheduling of multi-level assemblies. Computers and Industrial Engineering, 30(4):1047–1060. Roemer, T. and Ahmadi, R. (1997). The complexity of scheduling customer orders. In INFORMS Conference 1997, Dallas. 35 Roemer, T. A. (2006). A note on the complexity of the concurrent open shop problem. Journal of Scheduling, 9(4):389–396. Seidgar, H., Kiani, M., Abedi, M., and Fazlollahtabar, H. (2014). An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flowshop problem. International Journal of Production Research, 52(4):1240–1256. Seidgar, H., Zandieh, M., and Mahdavi, I. (2016). Bi-objective optimization for integrating production and preventive maintenance scheduling in two-stage assembly flowshop problem. Journal of Industrial and Production Engineering, 33(6):404–425. Shan, H., Chung, T.-P., and Hu, L. (2014). A note on “A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem”. International Journal of Advanced Manufacturing Technology, 74(5-8):819–822. Shi, Z., Huang, Z., and Shi, L. (2018). Customer order scheduling on batch processing machines with incompatible job families. International Journal of Production Research, 56(1-2):795–808. Shi, Z., Wang, L., Liu, P., and Shi, L. (2017). Minimizing completion time for order scheduling: Formulation and heuristic algorithm. IEEE Transactions on Automation Science and Engineering, 14(4):1558–1569. Shoaardebili, N. and Fattahi, P. (2015). Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints. International Journal of Production Research, 53(3):944–968. Shokrollahpour, E., Zandieh, M., and Dorri, B. (2011). A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flowshop problem. International Journal of Production Research, 49(11):3087–3103. Su, L.-H., Chen, P.-S., and Chen, S.-Y. (2013). Scheduling on parallel machines to minimise maximum lateness for the customer order problem. International Journal of Systems Science, 44(5):926–936. Sun, X., Morizawa, K., and Nagasawa, H. (2003). Powerful heuristics to minimize makespan in fixed 3- machine, assembly-type flowshop scheduling. European Journal of Operational Research, 146(3):498–516. Sung, C. and Juhn, J. (2009). Makespan minimization for a 2-stage assembly scheduling problem subject to component available time constraint. International Journal of Production Economics, 119(2):392–401. Sung, C. and Kim, H. (2008). A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times. International Journal of Production Economics, 113(2):1038–1048. Sung, C. S. and Yoon, S. H. (1998). Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines. International Journal of Production Economics, 54(3):247–255. Tajbakhsh, Z., Fattahi, P., and Behnamian, J. (2014). Multi-objective assembly permutation flow shop scheduling problem: A mathematical model and a meta-heuristic algorithm. Journal of the Operational Research Society, 65(10):1580–1592. Teymourian, E., Kayvanfar, V., Komaki, G., and Khodarahmi, M. (2016). An enhanced intelligent water drops algorithm for scheduling of an agile manufacturing system. International Journal of Information Technology and Decision Making, 15(2):239–266. Tian, Y., Liu, D., Yuan, D., and Wang, K. (2013). A discrete PSO for two-stage assembly scheduling problem. International Journal of Advanced Manufacturing Technology, 66(1-4):481–499. T’Kindt, V. and Billaut, J.-C. (2006). Multicriteria Scheduling - Theory, Models and Algorithms (2. ed.). Springer. 36 Torabzadeh, E. and Zandieh, M. (2010). Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop. Advances in Engineering Software, 41(10-11):1238–1243. Tozkapan, A., Kirca, O., and Chung, C.-S. (2003). A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem. Computers and Operations Research, 30(2):309–320. Wagneur, E. and Sriskandarajah, C. (1993). Openshops with jobs overlap. European Journal of Operational Research, 71(3):366–378. Wang, F., Jia, Z., Liu, W., and Zhao, G. (2011). Genetic algorithms with a new repair operator for assembly job shop scheduling. International Journal of Industrial Engineering: Theory Applications and Practice, 18(7):377–385. Wang, G. and Cheng, T. (2003). Customer order scheduling to minimize total weighted completion time. Proc. 1st Multidisciplinary Conf. Scheduling Theory Appl, pages 409–416. Wang, G. and Cheng, T. (2007). Customer order scheduling to minimize total weighted completion time. Omega, 35(5):623–626. Wang, K., Ma, W., Luo, H., and Qin, H. (2016). Coordinated scheduling of production and transportation in a two-stage assembly flowshop. International Journal of Production Research, 54(22):6891–6911. Wang, L., Shi, Z., and Shi, L. (2013). A novel quadratic formulation for customer order scheduling problem. In IEEE International Conference on Automation Science and Engineering, pages 576–580. Wong, T., Chan, F., and Chan, L. (2009). A resource-constrained assembly job shop scheduling problem with lot streaming technique. Computers and Industrial Engineering, 57(3):983–995. Wu, C.-C., Chen, J.-Y., Lin, W.-C., Lai, K., Liu, S.-C., and Yu, P.-W. (2018). A two-stage three-machine assembly flow shop scheduling with learning consideration to minimize the flowtime by six hybrids of particle swarm optimization. Swarm and Evolutionary Computation. Xiong, F. and Xing, K. (2014). Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time. International Journal of Production Research, 52(9):2743–2766. Xiong, F., Xing, K., and Wang, F. (2015). Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time. European Journal of Operational Research, 240(2):338–354. Xiong, F., Xing, K., Wang, F., Lei, H., and Han, L. (2014). Minimizing the total completion time in a distributed two stage assembly system with setup times. Computers and Operations Research, 47:92–105. Xu, J., Wu, C.-C., Yin, Y., Zhao, C., Chiou, Y.-T., and Lin, W.-C. (2016). An order scheduling problem with position-based learning effect. Computers and Operations Research, 74:175–186. Xu, X., Ma, Y., Zhou, Z., and Zhao, Y. (2015). Customer Order Scheduling on Unrelated Parallel Machines to Minimize Total Completion Time. IEEE Transactions on Automation Science and Engineering, 12(1):244– 257. Yan, H.-S., Wan, X.-Q., and Xiong, F.-L. (2014). A hybrid electromagnetism-like algorithm for two-stage assembly flow shop scheduling problem. International Journal of Production Research, 52(19):5626–5639. Yang, J. (2005). The complexity of customer order scheduling problems on parallel machines. Computers and Operations Research, 32(7):1921–1939. Yang, J. and Posner, M. E. (2005). Scheduling Parallel Machines for the Customer Order Problem. Journal of Scheduling, 8(1):49–74. 37 Yokoyama, M. (2001). Hybrid flow-shop scheduling with assembly operations. International Journal of Production Economics, 73(2):103–116. Yokoyama, M. (2004). Scheduling for two-stage production system with setup and assembly operations. Computers and Operations Research, 31(12):2063–2078. Yokoyama, M. (2008). Flow-shop scheduling with setup and assembly operations. European Journal of Operational Research, 187(3):1184–1195. Yokoyama, M. and Santos, D. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times. European Journal of Operational Research, 161(3):754–770. Zhang, Y., Zhou, Z., and Liu, J. (2010). The production scheduling problem in a multi-page invoice printing system. Computers and Operations Research, 37(10):1814–1821. 38