Transportation and delivery in flow-shop scheduling problems: A systematic review

Contents lists available at ScienceDirect European Journal of Operational Research journal homepage: www.elsevier.com/locate/eor Invited review Transportation and delivery in flow-shop scheduling problems: A systematic review Victor Fernandez-Viagas Industrial Management, School of Engineering, University of Seville, Camino de los Descubrimientos s/n, 41092 Seville, Spain ARTICLE INFO Keywords: Scheduling Flow shop Transport Vehicle Exact delay Time lag Routing Server Distribution Hoist scheduling Coupled operations ABSTRACT This paper presents a literature review of flow-shop scheduling problems with transportation or delivery of jobs. Flow-shop scheduling problems are one of the most widely studied optimisation problems in the literature on Operations Research. Although these have traditionally been studied assuming negligible or constant transport times, this does not correspond to real manufacturing scenarios in the industry. In fact, the extensive automation and synchronisation demanded by Industry 4.0 may well be a driving factor in the growing interest in the literature on flow-shop scheduling problems with transport constraints. Despite this interest, the literature is disjointed, and many terms have been used interchangeably. This review aims to organise the literature on the topic and propose a new notation for these problems. This contribution is expected to help structure advancements in the field, classifying them by problem type. Furthermore, a detailed study is carried out on the complexity and relationship between different variants. This provides a representation of the advances discovered in the literature while also demonstrating new theoretical results, before finally identifying the most promising research directions. 1. Introduction In recent years, factories have undergone a significant shift towards increased automation, a movement propelled by the advancements of Industry 4.0 (Waschneck et al.,2017), including flexible manufacturing cells, conveyor systems, automated vehicles, robots, CNC machines, and more. Despite the great potential shown by Industry 4.0 (see Echchakoui & Barka,2020 for benefits), especially in scheduling (Rossit et al.,2019), a very high investment is required for its complete deployment (Dev et al.,2020). In this situation, precision in transport and scheduling becomes imperative and emerges as a crucial element to achieve flawless synchronisation within factories. All this is compounded by the fact that the globalisation of recent decades has led to manufacturing companies integrating production and distribution areas more closely (Ramesh Kumar & Tiwari,2020). This integration in turn forces companies to produce the right amount of products for the individual customers, sending them to a specific place at the right time (Safaei et al.,2010). The importance of transport and its integration at all decision-making levels of companies have sparked a growing interest in the scheduling literature on transport constraints. Among the wide range of manufacturing layouts (see Hurink & Knust,2005; Lacomme et al.,2013;Li et al.,2023;Su et al.,2023), this survey focuses on the flow-shop scheduling problem (FSP), traditionally one of the most extensively studied problems in operational research. Since the publication of the seminal paper by Johnson (1954), contributions E-mail address: [email protected]. to this problem have pioneered research on scheduling with various constraints and objectives, and many optimisation approaches have their origins in this layout (Fernandez-Viagas et al.,2020). When there is a given set of jobs to be manufactured, flow shop scheduling undertakes the processing of these jobs on several machines, with each job following the same route through all the machines. This review focuses on the problem including the transport of semi-finished or finished jobs, – commonly known as FSP – with transportation or delivery constraints. Here, the challenge is to find sequences of jobs on the individual machines and transporters in order to minimise a given objective function. This problem has many applications in the real world. Notable examples include: the steel ingot teeming, heating and rolling process (Tang et al.,2010;Wang et al.,2022; Yuan et al.,2021); the pipe-making process (Yuan et al.,2020); carassembly business (Fabri et al.,2019); sanitary-ware production and distribution (Rahman et al.,2021); electronic device manufacturing (Tonizza Pereira & Seido Nagano,2022); surface treatment in electroplating plants and aircraft industries (Paul et al.,2007); circuit board manufacturing system (Yih,1994); production of connecting rods for engines (Lu et al.,2017); scheduling barges in seaports (Zhang & van de Velde,2015); semiconductor manufacturing (in burn in operation Behnamian et al.,2012a, or in wafer fabrication process, Geiger et al.,1997); manufacturing of connecting rod forgings (Sekkal & https://doi.org/10.1016/j.ejor.2024.11.034 Received 11 March 2024; Accepted 19 November 2024 European Journal of Operational Research 325 (2025) 1–19 Available online 30 November 2024 0377-2217/© 2024 The Author. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/bync-nd/4.0/ ). V. Fernandez-Viagas Belkaid,2023); and book digitisation service (Villarinho et al.,2021). On occasions, instead of remaining static the machinery is transported elsewhere for use in the task. This phenomenon, known as the routing flow shop scheduling problem, is observed when jobs are too big or heavy. Examples of this include when working with plane or ship components (Averbakh & Berman,1999), when the repair engineers or machines must provide repair services (Yu et al.,2011), and jobs in the construction sector (Chernykh et al.,2023). The first paper to examine the issue of transportation is Mitten (1959). While this paper does not explicitly identify it as pertaining to model transportation in the shop, it addresses the two-machine permutation flow shop with time lags, which can be viewed as the transportation of jobs when considering unlimited capacity (e.g., using a conveyor belt). Since then, numerous contributions have attempted to analyse different aspects relating to transportation constraints in the flow shop. However, despite the growing interest in this type of constraint, the literature remains unclear. Numerous variants of the problem have been studied independently, and different notations have been used for issues that are closely related and even identical. This review aims to consolidate, summarise and structure all these findings relating to the transport of items in the flow shop. Furthermore, under specific conditions, certain related scheduling problems can be viewed as particular instances of the FSP with transport. Thereby, scheduling problems considering, e.g., time lags, setup times, servers, and release times can also be used to model transport in FSP. However, a detailed analysis is required given that the correlation between these problems remains unclear in the literature. To the best of our knowledge, this is the first review that completely addresses transportation in the flow shop scheduling problem. Additionally, this study aims to establish a formal classification of the problem within the scheduling literature. In order to do so, we propose the following contributions: •A new systematic review of the literature, covering all known transport constraints in the flow shop layout. •A classification and summary of papers in tables, and a new notation for different types of transport, (which can be integrated in the 𝛽field of Graham et al.,1979). •An analysis and discussion of the complexity of these types of problems. •An in-depth analysis of the list of problems under consideration, examining scheduling problems and summarising the findings documented in the existing literature. •An in-depth discussion of open research questions in the literature with a view of incorporating them in future research. The paper is thus organised as follows: the description of the problem is presented in Section 2. Section 3presents the methodology proposed to review the literature. The proposed notation of the problem is described in Section 4. The subsequent sections incorporate a comprehensive review of the papers that address the problem, discussing those selected following the methodology featured in Section 3. Furthermore, we provide a theoretical analysis of the problem and a discussion of the literature regarding the complexity of the problem and its equivalence with related scheduling problems. These sections are divided by problem type. Firstly, Section 5presents a discussion of semi-finished job approaches including transportation between stages (Section 5.1); server approaches (Section 5.2); the routing flow shop problem (Section 5.3); and transportation before processing (Section 5.4). This is then followed by a discussion on papers analysing the delivery of final products in Section 6, examining direct delivery (Section 6.1) and integrated routing and scheduling (Section 6.2). Section 7 presents an analysis of mixed approaches, while Section 8presents quantitative analyses and a summary of the main findings. Finally, conclusions are discussed and future lines of research are presented in Section 9. 2. Problem description In the flow shop scheduling problem, there are 𝑛jobs that are processed on 𝑚machines. Each job 𝑗(with 𝑗∈ {1,…, 𝑛}) follows the same route of machines, processing its operation 𝑂𝑖𝑗 on machine 𝑖(with 𝑖∈ {1,…, 𝑚}). This paper specifically addresses the transportation of jobs (or potentially machines) before or after processing a given operation. When referring to the transport process, several terms have traditionally been used in the literature, depending on the specific field addressed in individual papers. A summary is offered here for some of the most common terms: vehicles, agents, servers, transport agents, robotic arms, cranes, robotic transfer devices, robots, transporters, conveyor belts, carriers, material handling devices, cars or (industrial) trucks. For the avoidance of confusion, this paper uses the terms vehicles and transporters to denote the objects which move the products (although in a real scenario these could obviously be a car, truck, robot...). The number of vehicles considered is denoted by 𝜏, while their capacity is denoted by 𝑐. The transport time required to move job 𝑗from machine 𝑖− 1to 𝑖is indicated by 𝑡𝑖𝑗 . Furthermore, the processing time of job 𝑗on machine 𝑖is denoted by 𝑝𝑖𝑗 . The sequence of jobs on machine 𝑖is denoted by 𝛱𝑖= (𝜋𝑖1, 𝜋𝑖2,…, 𝜋𝑖𝑛). The completion time of operation 𝑂𝑖,𝜋𝑖𝑗 is denoted by 𝐶𝑖𝑗 . When clarity can be guaranteed, indices 𝑖[𝑗]are used to denote operation 𝑂𝑖,𝜋𝑖𝑗 , i.e. 𝑝𝑖[𝑗] represents the processing time of this operation. In order to identify the papers in this review, the 𝛼|𝛽|𝛾notation proposed by Graham et al. (1979) has been used, with 𝛼=𝐹𝑚 (corresponding to a flow shop layout). A summary of the abbreviations applied to the fields 𝛽and 𝛾in the reviewed articles, using a notation based on Pinedo (2012) as well as on previous literature reviews (see Komaki et al.,2019;Miyata & Nagano,2019;Rolim & Nagano, 2020;Rossit et al.,2018), can be found in Appendix A. 3. Methodological approach The methodology proposed in this paper is introduced in this section. A systematic review of the literature allows us a comprehensive examination of the issue under consideration, collating the maximum number of contributions. Through this approach, we aim to explore the following research questions: RQ1: How are the different variants of the problem named? RQ2: Which problems have been proved to be NP-hard or to have exact polynomial-time algorithms? RQ3: Which properties have been established? What are the relationships between the problems under consideration and related scheduling problems? RQ4: Which techniques and models have been developed? RQ5: How can each specific transportation constraint be represented in the 𝛼|𝛽|𝛾notation? RQ6: What are the future research lines? A necessary initial step in the methodology proposed is the identification of articles to be reviewed. The two levels of keywords have been established in this phase: •Keyword level 1: flowshop or ‘‘flow shop’’ •Keyword level 2: transportation or travel or routing or delivery or robotic or server or delay or ‘‘time lag’’ or transport These combinations of keywords have been entered in three databases: Scopus, Google Scholar and SpringerLink. Articles meeting the criterion of containing at least one keyword from each level were chosen for inclusion. Furthermore, articles they cite, as well as those citing them, were also examined (snowball search). More than 300 articles were identified in this search. In order to ensure the quality and thematic relevance of the contributions reviewed, results were then refined, filtering the articles according to the exclusion criteria below (see Neufeld et al.,2023;Rolim & Nagano,2020 for similar exclusion and quality criteria): European Journal of Operational Research 325 (2025) 1–19 2 V. Fernandez-Viagas Fig. 1. Proposed methodology. •Criterion E1: Conference papers and chapters are not included. •Criterion E2: Non-English manuscripts are not considered. •Criterion E3: Simulation or different problem layouts, such as distributed (𝛼=𝐷 𝐹𝑚), hybrid (𝛼=𝐻 𝐹𝑚), or assembly flow shop (typically denoted as 𝛼=𝐷 𝑃 𝑚→𝐹𝑚or 𝐴𝐹𝑚) are not included, thus only 𝛼=𝐹𝑚, with 𝑚≥2is considered. •Criterion E4: Only papers in journals published in the first and second quartile according to the Scimago journal ranking (SJR) are included. More specifically, all articles in quartile Q1 or Q2 of SJR, either in the year of publication or in the last rank (i.e., SJR 2022) have been considered. Articles with a year of publication before 1999 are also included if the journal has been in Q1 or Q2 in any year. Following Criteria E1 and E2, 299 papers were selected. This total figure was then reduced to 209, upon excluding papers addressing different layouts (E3). Finally, after applying Criterion E4, 119 articles were selected. Once all the articles are identified and reviewed, their main characteristics are recorded in this paper. Other aspects reviewed in this paper and included in tables are the notation of the problem using 𝛼|𝛽|𝛾 according Graham et al. (1979) (Problem); types of exact methods used to solve the problems under consideration (Exact); type of approximate algorithms used to solve the proposed problem (Approximate); and, finally, additional main contributions of the papers (Other). A comprehensive theoretical analysis is also carried out for the problems under consideration. An initial analysis is conducted to record the complexity of the problems, their properties, and its equivalence with related scheduling problems from the literature. This is then followed by new theorems, proposed to ensure better understanding of the boundary lines of the problems under consideration. An overview of the proposed methodology for this review is presented in Fig. 1. The aim of this methodology is to provide the first literature review of flow shop scheduling problems with transportation. In terms of similar studies in the literature, the recent proposals by Berghman et al. (2023) and Hosseini et al. (2023) are considered the two most closely connected reviews. Despite the significant interest of both these reviews, their scope of study differs greatly. Both address very specific cases of transportation, focusing on scheduling in general (i.e. including single machine, parallel machines, etc.). However, Berghman et al. (2023) address only the specific problem of integrating routing and scheduling, while Hosseini et al. (2023) examine transportation between stages. In fact, of the articles reviewed in this study, only six and 29 are cited in Berghman et al. (2023) and Hosseini et al. (2023), respectively. 4. Proposed notation Different approaches have been considered in the literature to address transport in the flow shop scheduling problem. In this review, for the purposes of classification, we propose the notation 𝑇 𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝜏 (𝑊 𝑥, 𝑌 𝑧)or 𝑇𝜏(𝑊 𝑥, 𝑌 𝑧)(when this does not lead to confusion) to classify them,1and the use of two fields: type of problem (𝑊 𝑥) and type of transporter (𝑌 𝑧). As detailed in the previous section, 𝜏is the number of vehicles considered. Consequently, when several jobs (individually or in batches) can be transported simultaneously (either by considering infinite vehicles or a conveyor belt with infinite capacity), 𝜏, is omitted. The latter is typically denoted in the literature as time lag or delay. 4.1. Type of problem The first field, denoted by 𝑊 𝑥, represents the type of transport taking place. In the primary field 𝑊, a series of problems can be distinguished and divided into transportation of semi-finished and finished jobs: Transportation of semi-finished jobs: In this case, four types of problems can be identified to transport semi-finished jobs (typically) to machines: •Transportation between stages (𝑊=𝑀). There are vehicles (typically denoted agents or robots) that transport jobs between machines. Traditionally, all transporters can be used serve all machines. However, when transporters are intended for a specific subset of machines, the problem is indicated by 𝑊=𝑀𝑎 and the transport can be classified as allocated (Ahmadi-Javid & Hooshangi-Tabrizi,2015). Furthermore, when transporters are guided and can only move along a specific sequence of machines (e.g., first machine 1, then machine 2, ...), this is denoted by 𝑊=𝑀𝑔. •Server case or multi-item hoist scheduling (𝑊=𝑆). In this case, during transportation, neither the vehicle nor the posterior machine can perform any other task, i.e., the machine is blocked. This type of situation tends to arise when the transporter (typically denoted as server in this problem) introduces the job directly into the machine feed. It should be noted that in the server scheduling literature, the setup constraint is equivalent to the transport constraint, but only when setup times are nonanticipatory.2Otherwise, the problem is of different nature, and as such, not considered relevant to this research. •Routing flow shop problem, (𝑊=𝑅). When transportation is not needed between operations of the same jobs, but rather between operations on the same machine, a different problem variant arises. In this case, the machines are transported to the jobs that are fixed. It is generally assumed that the specific routes and thus, travel times, between each job pair are known in advance (i.e. a complete graph is considered). Nevertheless, when a tree graph is considered, the problem is shown as 𝑊=𝑅𝑡. 1Although this notation could be divided into two, 𝑇𝜏and 𝑇(𝑊 𝑥, 𝑌 𝑧), to be entered into the fields 𝛼(machine environment) and 𝛽(job characteristics) of the notation by Graham et al. (1979), respectively, we recommend using the proposed notation directly in field 𝛽for simplification for practitioners and academics. 2A setup is classified as non-anticipatory (or equivalently non-separable) when it cannot be initiated prior to job arrival. Conversely, it is classified as anticipatory (or separable) when it can be started before or after the job arrival. European Journal of Operational Research 325 (2025) 1–19 3 V. Fernandez-Viagas •Transportation of raw materials or transportation before processing and production, denoted 𝑊=𝑃. In this case, vehicles transport raw materials or pre-processing products from providers or other areas of the company. Delivery of final products: In this case, a fleet of transporters (typically denoted by vehicles, cars or trucks) is in charge of delivering the final products to the clients or to the final product buffer. Depending on the number of customers visited for each vehicle and on the delivery dates, the following two approaches can be considered: •Scheduling with direct delivery, 𝑊=𝐷. In this case, each vehicle serves only one customer in each trip. •Integrated Production and Distribution Problem (also denoted as scheduling with vehicle routing or integrated routing and scheduling problem), 𝑊=𝐶. In this problem, there is a routing decision methodology to agree the route for each vehicle to serve customers. Typically, each node in the routing decision problem has been assigned a customer and has specific job demands. In addition, in the secondary field 𝑥, two cases can be identified for each of the previous problem types, that is, 𝑊= {𝑃 , 𝑀 , 𝑆 , 𝑅, 𝐷}: •One-way trip (𝑥=𝑜). Each vehicle transports the job directly to a machine (typically to its buffer). During this time, the previous machine may be processing a different job. Once the job is transported, the vehicle is available to transport a different job. This typical representation of cases incorporates elements such as conveyor belts, where the vehicle takes the following job directly from the same machine, or where the time frames for returning the vehicles (to the starting position or to another machine) are negligible. •Round trip (𝑥=𝑟). This case considers both the time to move the job to a specific machine and the time to return the empty vehicle to its starting position or to another machine. Therefore, vehicle cannot begin its subsequent transport until the arrival time. Note that the machine can start processing its subsequent job after the time of the one-way trip. Furthermore, in transportation from providers (𝑊=𝑃) or to clients (𝑊=𝐷or 𝑊=𝐶), it is implicitly considered in the notation that the Variable Delivery Date (VDD) approach is followed, so that the jobs are delivered at any time a vehicle is available. However, if a Fixed Delivery Date (FDD) approach is assumed (where jobs, individually or in batches, must be delivered only on specific dates or intervals), then 𝑓should be included in field 𝑥. 4.2. Type of transporter The second field, denoted by 𝑌 𝑧, represents the type of transporter considered. The following types can be distinguished in the primary field 𝑌, depending on the number of jobs that are transported: •Vehicles transport jobs individually, 𝑌=𝐼. In this case, several subcases are identified in the secondary field 𝑧, depending on how transport times are considered: –Transport time depends on machines’ or clients’ locations, 𝑧=𝑖(for example, transport times depend on the distances between machines 𝑖and 𝑖+ 1or on the distance between machine 𝑖and the location of its raw material). –Transport time depends on the job transported, 𝑧=𝑗. –Transport time depends on the speed of the transporter, 𝑧=𝑠. –Transport time depends on the actual job being transported as well as the previous job transported, 𝑧=𝑗 𝑘. This means that there is a potentially different transport time when job 𝑗is succeeded by job 𝑘instead of another job. –Transport time depends on the specific vehicle 𝑣or its selected speed (in cases with different speed options for each vehicle), 𝑧=𝑣. •Vehicles move jobs in batches with limited capacity 𝑌=𝐵. In the case of unlimited capacity of vehicles, this is denoted by 𝑌=𝐵∞. In addition, when a specific limited capacity 𝑏is addressed, it is indicated by 𝑌=𝐵𝑏. Regarding the transport time of batches, several specific approaches can be identified in this case: –Transportation times depend on the location of the machines or clients, 𝑧=𝑖. –Transportation times are different for each vehicle 𝑣,𝑧=𝑣. –Transportation times depend on the jobs contained within the batch 𝑗,𝑧=𝑗. –Transportation times depend on the speed of the transporter, 𝑧=𝑠. –Transportation times depend on the size of the batch, 𝑧=𝑐. Obviously, these previous notations in the secondary field 𝑧can be combined, e.g., if the travel times depend on the vehicle and the job, it can be denoted by 𝑧=𝑣𝑗. Furthermore, if 𝑧is omitted, transport times are constant. Finally, it should be noted that when jobs are delivered directly to customers in batches, 𝑇(𝐷 𝑥, 𝐵 𝑧), only jobs belonging to the same order/client can be included within the same batch. The rest of the paper is structured according to the types of problem explained above. 5. Transportation of semi-finished jobs This section presents a comprehensive review of the papers addressing the transportation of semi-finished jobs following the procedure described in Section 3. A series of approaches – transportation between stages (Section 5.1); server approach (Section 5.2); routing flow shop problem (Section 5.3; and transportation of raw materials (Section 5.4) – are discussed. 5.1. Transportation between stages (𝑊=𝑀) This is the most discussed FSP with transportation constraints in the literature. All selected papers considering transport between stages are summarised in Table 1. Most of the contributions address problems, which in many cases have been identified as NP-hard, by applying optimisation methods. In order to analyse the findings of the literature, this section is divided firstly into Section 5.1.1, analysing the theoretical results found in the literature and proposing new results which address the equivalence of these problems with other related scheduling problems, and Section 5.1.2, providing a review of optimisation algorithms and related contributions applied to solve the problem. 5.1.1. Analysis of the problem The transportation between stages has been addressed in the literature considering a limited or unlimited number of vehicles. In the case of the latter, the problem is similar to the classical flow shop with time lags. It should also be noted that, even in the literature, the definition of time lags remains unclear. While the oldest literature on the topic usually considers the time lag as the minimum time between the start (completion) of two consecutive operations of a job (Mitten,1959; Rinnooy Kan,1976), nowadays it is referred to as the minimum time between the completion of the operation on machine 𝑖and the start of the following operation on machine 𝑖+ 1(see e.g. Mkadem et al.,2021; Samarghandi,2019). However, regardless of these definitions, the timelag constraint can be mostly modelled as a transportation constraint, as indicated in the following theorems (all proofs of the theorems included in this paper are included as supplementary material): European Journal of Operational Research 325 (2025) 1–19 4 V. Fernandez-Viagas Table 1 Summary of contributions for transportation between stages. Reference Problem Exact Approximate Other Lan et al. (2024)𝐹2|𝑇1(𝑀 𝑟, 𝐵)|𝐶𝑚𝑎𝑥 PTAA P Boufellouh and Belkaid (2023) 𝐹𝑚|𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔 , 𝑆 𝑖𝑗 𝑘, 𝑚𝑎𝑖𝑛𝑡, 𝑇𝜏(𝑀𝑔𝑟, 𝐼 𝑖𝑗 𝑠)|#(𝐶𝑚𝑎𝑥, 𝑇 𝐸 𝐶)MILP ACA Khatami et al. (2023)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡, 𝑜𝑟𝑑 𝑒𝑟𝑒𝑑|𝐶𝑚𝑎𝑥 DPA, EPA P Khatami et al. (2023)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝐶𝑚𝑎𝑥 EPA P, CA Wang et al. (2022)𝐹2|𝑇1(𝑀 𝑟, 𝐵 𝑖), 𝑝−𝑏𝑎𝑡𝑐 ℎ|𝐶𝑚𝑎𝑥 MILP CH Gnatowski et al. (2022)𝐹𝑚|𝑇1(𝑆 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 MILP TB, CH P Mkadem et al. (2021)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗)|𝐶𝑚𝑎𝑥 B&B P, LB Yuan et al. (2020)𝐹2|𝑇1(𝑀 𝑟, 𝐼 𝑗), 𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔 , 𝑓 𝑎𝑚|𝐶𝑚𝑎𝑥 MILP GA CA Ageev (2020)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡, 𝑡𝑗∈ {𝑡′, 𝑡′′ }|𝐶𝑚𝑎𝑥 PTAA P, LB Samarghandi (2019)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |𝐶𝑚𝑎𝑥 MILP, CP TS P Hamdi and Toumi (2019)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢|∑𝑇𝑗MILP Dhouib et al. (2018)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑤𝑡𝑚𝑎𝑥 𝑗|∑𝑈1 𝑗, 𝐶2 𝑚𝑎𝑥 MILP CH P Wang, Huang, and Li (2018) 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |𝐶𝑚𝑎𝑥 MILP CH P Zhao et al. (2017)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |𝐶𝑚𝑎𝑥 CH, IG Zhao et al. (2017)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |𝐶𝑚𝑎𝑥 CH, IG Ye et al. (2017)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |𝐶𝑚𝑎𝑥 IG Msakni et al. (2016)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢|∑𝐶𝑗B&B IG LB Dong et al. (2016)𝐹2|𝑇1(𝑀 𝑟, 𝐵)|𝐶𝑚𝑎𝑥 PTAA P Liou and Hsieh (2015)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼𝑖𝑗 ), 𝑝𝑟𝑚𝑢, 𝑓 𝑎𝑚, 𝑠𝑖𝑗 𝑘|𝐶𝑚𝑎𝑥 PSO LB Ahmadi-Javid and Hooshangi-Tabrizi (2015) 𝐹𝑚|𝑇𝜏(𝑀𝑎𝑟, 𝐼𝑖𝑗 ), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 MILP ASO LB Zhang and van de Velde (2015) 𝐹2|𝑇(𝑀 𝑜, 𝐼), 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙|𝑤𝑁 DPA CA Zhong and Chen (2015)𝐹2|𝑇1(𝑀 𝑟, 𝐵)|𝐶𝑚𝑎𝑥 CH P Hamdi and Loukil (2015a)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |∑𝑇𝑗MILP DR LB Hamdi and Loukil (2015b)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗)|∑𝑈𝑗DR LB Khalili (2014)𝐹𝑚|𝑇 𝑚− 1(𝑀𝑎𝑟, 𝐼), 𝑠𝑘𝑖𝑝, 𝑝𝑚|∑𝐶𝑗and ∑𝑇𝑗DR, CH, EM, SA Dhouib et al. (2013)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |∑𝑈1 𝑗, 𝐶2 𝑚𝑎𝑥 MILP SA Gupta et al. (2013)𝐹2|𝑇1(𝑀 𝑟, 𝐼 𝑗), 𝑠𝑖𝑗 | 𝐶𝑚𝑎𝑥 and ∑ 𝐹𝑗EPA Behnamian et al. (2012b)𝐹2|𝑇1(𝑀 𝑟, 𝐵), 𝑝−𝑏𝑎𝑡𝑐 ℎ|𝐶𝑚𝑎𝑥 MILP CH LB Behnamian et al. (2012a)𝐹3|𝑇2(𝑀𝑎𝑜, 𝐵 𝑖), 𝑝−𝑏𝑎𝑡𝑐 ℎ|𝐶𝑚𝑎𝑥 MILP CH, GA Khalili and Tavakkoli-Moghaddam (2012) 𝐹𝑚|𝑇 𝑚− 1(𝑀𝑎𝑟, 𝐼), 𝑝𝑟𝑚𝑢, 𝑠𝑘𝑖𝑝|#(𝐶𝑚𝑎𝑥,∑𝑤𝑗𝑇𝑗)EM Gong and Tang (2011)𝐹2|𝑇1(𝑀 𝑟, 𝐵)|𝐶𝑚𝑎𝑥 CH P Tang et al. (2010)𝐹2|𝑇1(𝑀 𝑟, 𝐼)|𝐶𝑚𝑎𝑥 B&B IH LB Naderi, Ahmadi Javid, and Jolai (2010) 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 MILP DR, CH, AIS Naderi, Ahmadi Javid, and Jolai (2010) 𝐹𝑚|𝑇 𝑚− 1(𝑀𝑎𝑟, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 MILP DR, CH, AIS Zhang and Van De Velde (2010) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑟𝑗, 𝑠𝑘𝑖𝑝|𝐶𝑚𝑎𝑥 PTAA Zhang and Van De Velde (2010) 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑠𝑘𝑖𝑝|∑𝐶𝑗PTAA Naderi, Tavakkoli-Moghaddam, and Khalili (2010) 𝐹𝑚|𝑇 𝑚− 1(𝑀𝑎𝑟, 𝐼), 𝑝𝑟𝑚𝑢, 𝑠𝑘𝑖𝑝|𝐶𝑚𝑎𝑥 and ∑𝑤𝑗𝑇𝑗DR, CH, EM, SA Tang and Liu (2009b)𝐹2|𝑇1(𝑀 𝑟, 𝐵), 𝑏𝑎𝑡𝑐 ℎ|𝐶𝑚𝑎𝑥 CH CA Tang and Liu (2009a)𝐹2|𝑇1(𝑀 𝑟, 𝐵), 𝑏𝑎𝑡𝑐 ℎ|𝐶𝑚𝑎𝑥 MILP CH CA Huo et al. (2009)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡|∑𝐶𝑗DR, TS, SA P, CA Fondrevelle et al. (2009)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝐿𝑚𝑎𝑥 B&B CH P, LB Munier-Kordon and Rebaine (2008) 𝐹3|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑝𝑖𝑗 = 1|𝐶𝑚𝑎𝑥 EPA (continued on next page) European Journal of Operational Research 325 (2025) 1–19 5 V. Fernandez-Viagas Table 1(continued). Reference Problem Exact Approximate Other Munier-Kordon and Rebaine (2008) 𝐹4|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑝𝑖𝑗 = 1|𝐶𝑚𝑎𝑥 EPA Rayward-Smith and Rebaine (2008) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑖𝑗 = 1|𝐶𝑚𝑎𝑥 DR P Fondrevelle et al. (2008)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |∑𝑤𝑗𝐶𝑖B&B P, CA Ageev (2008)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝1𝑗=𝑝2𝑗|𝐶𝑚𝑎𝑥 PTAA LB Leung et al. (2007)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡, 𝑠𝑘𝑖𝑝|𝐶𝑚𝑎𝑥 PTAA CA Leung et al. (2007)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡, 𝑠𝑘𝑖𝑝|∑𝐶𝑗EPA PTAA CA Ageev and Baburin (2007)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗 , 𝑛𝑜 −𝑤𝑎𝑖𝑡, 𝑝𝑖𝑗 = 1)|𝐶𝑚𝑎𝑥 PTAA LB Fondrevelle et al. (2006)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |𝐶𝑚𝑎𝑥 B&B CH P, LB, CA Çetinkaya (2006)𝐹2|𝑇1(𝑀 𝑟, 𝐼), 𝑠𝑖𝑗 |𝐶𝑚𝑎𝑥 EPA P Prasad et al. (2006)𝐹𝑚|𝑇(𝑀 𝑓 𝑜, 𝐵 𝑖), 𝑝𝑟𝑚𝑢, 𝑏𝑢𝑓 𝑓 𝑒𝑟, 𝑏𝑎𝑡𝑐 ℎ|#(∑𝐶𝑗, 𝐶𝑏, 𝜎𝐶𝑗)CH, GA Rebaine (2005)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗)|𝐶𝑚𝑎𝑥 P Rebaine (2005)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 P Lee and Strusevich (2005)𝐹2|𝑇1(𝑀 𝑟, 𝐵∞)|𝐶𝑚𝑎𝑥 CH P, CA Brucker et al. (2004) Several problemsaEPA CA Yu et al. (2004)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑖𝑗 = 1|𝐶𝑚𝑎𝑥 P, CA Hurink and Knust (2001)𝐹𝑚|𝑇1(𝑀 𝑜, 𝐼 𝑖𝑗)|𝐶𝑚𝑎𝑥 EPA CA Lee and Chen (2001) Several problemsbEPA CH P, CA Yang and Chern (2000)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑓 𝑎𝑚|𝐶𝑚𝑎𝑥 EPA P Haouari and Ladhari (2000) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑟𝑗|𝐿𝑚𝑎𝑥 B&B CH LB Ganesharajah et al. (1998)𝐹2|𝑇1(𝑀 𝑟, 𝐼 𝑗), 𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔|𝐶𝑚𝑎𝑥 CA Riezebos and Gaalman (1998) 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑟𝑒𝑐 𝑟|𝐶𝑚𝑎𝑥 DR LB Stevens and Gemmill (1997) 𝐹2|𝑇1(𝑀 𝑟, 𝐼)|𝐿𝑚𝑎𝑥 CH Dell’Amico and Vaessens (1996) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝1𝑗=𝑝2𝑗|𝐶𝑚𝑎𝑥 LB, CA Dell’Amico (1996)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗)|𝐶𝑚𝑎𝑥 CH, TS P, LB, CA Yu (1996)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝1𝑗=𝑝2𝑗, 𝑡𝑗∈ 0, 𝑙|𝐶𝑚𝑎𝑥 LB, CA Riezebos et al. (1995)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑟𝑒𝑐 𝑟|𝐶𝑚𝑎𝑥 B&B DR LB Panwalkar (1991)𝐹2|𝑇1(𝑀 𝑟, 𝐼), 𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔|𝐶𝑚𝑎𝑥 EPA Stern and Vitner (1990)𝐹2|𝑇1(𝑀 𝑟, 𝐼 𝑗), 𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔|𝐶𝑚𝑎𝑥 PTAA P, LB Szwarc (1983)𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 LB Maggu et al. (1982)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 EPA Maggu et al. (1981)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 DA P Rinnooy Kan (1976)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 EPA Mitten (1959)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 EPA a𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑖𝑗 =𝑝, 𝑎𝑔 𝑟𝑒𝑒𝑎𝑏𝑙 𝑒|∑𝑤𝑗𝐶𝑗,𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑖𝑗 =𝑝|∑𝐶𝑗,𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑖𝑗 = 1|∑𝑤𝑗𝐶𝑗,𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑖𝑗 = 1, 𝑟𝑗|∑𝐶𝑗. b𝐹2|𝑇𝜏(𝑀 𝑟, 𝐼)|𝛾𝑟,𝐹2|𝑇1(𝑀 𝑟, 𝐼)|𝐶𝑚𝑎𝑥,𝐹2|𝑇 𝜏(𝑀 𝑟, 𝐵)|𝐶𝑚𝑎𝑥 ,𝐹2|𝑇1(𝐷 𝑟, 𝐵)|𝐶𝑚𝑎𝑥, and 𝐹2|𝑇1(𝐷 𝑟, 𝐼)|𝐶𝑚𝑎𝑥 . Theorem 5.1. Let 𝑎be the 𝐹𝑚|𝑙𝑚𝑖𝑛 𝑖𝑗 |𝛾problem, where 𝑙𝑚𝑖𝑛 𝑖𝑗 represents the minimum time lag between the completion time of a job and the start time in the subsequent stage. Let 𝑏be the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗)|𝛾problem, where 𝑡𝑖𝑗 =𝑙𝑚𝑖𝑛 is the transport time between operations 𝑂(𝑖, 𝜋𝑖𝑗 )and 𝑂(𝑖, 𝜋𝑖+1,𝑗 ). Both problems are therefore equivalent. Theorem 5.2. Let 𝑎be the 𝐹𝑚|𝑙𝑆 𝑖𝑗 |𝛾problem, where 𝑙𝑆 𝑖𝑗 is the minimum start time lag between the start times of operations 𝑂(𝑖, 𝜋𝑖𝑗 )and 𝑂(𝑖, 𝜋𝑖+1,𝑗 ). Let 𝑏be the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗)|𝛾problem, with 𝑡𝑖𝑗 =𝑙𝑆 𝑖𝑗 −𝑝𝑖𝜋𝑗as the transport time between operations 𝑂(𝑖, 𝜋𝑖𝑗 )and 𝑂(𝑖, 𝜋𝑖+1,𝑗 ). Both problems are therefore equivalent. Theorem 5.3. Let 𝑎be the 𝐹𝑚|𝑙𝐶 𝑖𝑗 |𝛾problem, where 𝑙𝐶 𝑖𝑗 is the minimum stop time lag between the completion times of operations 𝑂(𝑖, 𝜋𝑖𝑗 )and 𝑂(𝑖, 𝜋𝑖+1,𝑗 ). Let 𝑏be the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗)|𝛾problem, with 𝑡𝑖𝑗 =𝑙𝐶 𝑖𝑗 −𝑝𝑖+1,𝜋𝑗 as the transport time between operations 𝑂(𝑖, 𝜋𝑖𝑗 )and 𝑂(𝑖, 𝜋𝑖+1,𝑗 ). Both problems are therefore equivalent. Theorem 5.4. Let 𝑎be the 𝐹𝑚|𝑙𝑆 𝑖𝑗 , 𝑙𝐶 𝑖𝑗 |𝛾problem, where 𝑙𝑆 𝑖𝑗 and 𝑙𝐶 𝑖𝑗 are the minimum start and stop time lag between the completion times of operations 𝑂(𝑖, 𝜋𝑖𝑗 )and 𝑂(𝑖, 𝜋𝑖+1,𝑗 ), respectively. Let 𝑏be the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗)|𝛾problem, with 𝑡𝑖𝑗 = max{𝑙𝑆 𝑖𝑗 −𝑝𝑖𝜋𝑗, 𝑙𝐶 𝑖𝑗 −𝑝𝑖+1,𝜋𝑗}as the transport time between operations 𝑂(𝑖, 𝜋𝑖𝑗 )and 𝑂(𝑖, 𝜋𝑖+1,𝑗 ). Both problems are therefore equivalent. Theorem 5.5. Let 𝑎be the 𝐹𝑚|𝑙𝑖𝑗 |𝛾problem, where 𝑙𝑖𝑗 is the exact time lag between the completion time of a job and the start time in the subsequent stage. Let 𝑏be the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾problem, with 𝑡𝑖𝑗 =𝑙𝑖𝑗 as the transport time between operations 𝑂(𝑖, 𝜋𝑖𝑗 )and 𝑂(𝑖, 𝜋𝑖+1,𝑗 ). Both problems are therefore equivalent. Theorem 5.6. Let 𝑎be the 𝐹𝑚|𝑙𝑚𝑖𝑛 𝑖𝑗 , 𝑙𝑚𝑎𝑥 𝑖𝑗 |𝛾problem, where 𝑙𝑚𝑖𝑛 𝑖𝑗 and 𝑙𝑚𝑎𝑥 𝑖𝑗 are the minimum and maximum time lag between the completion time of a job and the start time in the subsequent stage, respectively. Let 𝑏be the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡, 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |𝛾problem, with 𝑡𝑖𝑗 =𝑙𝑚𝑖𝑛 𝑖𝑗 as the transport time between operations 𝑂(𝑖, 𝜋𝑖𝑗 )and 𝑂(𝑖, 𝜋𝑖+1,𝑗 ), and 𝑤𝑡𝑚𝑎𝑥 =𝑙𝑚𝑎𝑥 𝑖𝑗 −𝑙𝑚𝑖𝑛 𝑖𝑗 . Then, both problems are equivalent. Both problems are therefore equivalent. European Journal of Operational Research 325 (2025) 1–19 6 V. Fernandez-Viagas Furthermore, the problem is considered equivalent to other related scheduling problems under different conditions. Maggu et al. (1981) have shown that completion times of a schedule in the 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗)|𝛾 problem can be directly computed by solving the 𝐹2∥𝛾problem, with the same schedule, and adding a constant to obtained completion times in this last problem, i.e., both problems are equivalent if the objective function is regular. As result, 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗)|𝐶𝑚𝑎𝑥 and 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 present the same optimal solutions (see Mkadem et al.,2021 for further evidence of this observation). A similar result is found by Lee and Chen (2001) between 𝐹2|𝑇(𝑀 𝑜, 𝐼)|𝛾𝑟and 𝐹2|𝑇(𝑀 𝑜, 𝐵), 𝑝𝑟𝑚𝑢|𝛾𝑟(𝛾𝑟 being any regular function). Regarding the problem with maximum waiting time (i.e. the classical flow shop with minimal and maximal time lags), Samarghandi (2019) establishes an equivalence between the permutation and non-permutation variants when the maximum waiting time for each job 𝑗,𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 , satisfies 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 < 𝑝𝑖𝑘 +𝑝𝑖+1,𝑘 for each 𝑖,𝑗, and 𝑘≠𝑗. In fact, for the two-machine variant of the problem, Dhouib et al. (2018) also prove that every non-permutation solution is unfeasible if max∀𝑗{𝑤𝑡𝑚𝑎𝑥 𝑗}is below min∀𝑗{𝑝1𝑗+𝑝2𝑗+𝑡𝑗}. They also analyse more specific cases of equivalence and the idle time incurred when a non-permutation solution is applied. Recently, Khatami et al. (2023) establish the equivalence between the 𝐹2|𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾 and 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾problems. Regarding other equivalences, the following property states that transport times can be omitted if they are constant and a regular objective function is assumed. Therefore, in the case of constant transport times, this property extends the previous theoretical result found by Maggu et al. (1981) to 𝑖 >2. Theorem 5.7. Let 𝑎be the 𝐹𝑚∥𝛾𝑟problem (if 𝛾𝑟is any regular objective function). Let 𝑏be the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼)|𝛾𝑟problem. 𝑎and 𝑏are therefore equivalent. In cases where the number of vehicles is a finite number, Soukhal et al. (2005) establish that the two-machine problem with no-wait constraint and a single transporter is equivalent to a no-wait three-machine flow shop scheduling problem, while Stern and Vitner (1990) analyse the equivalence of the two-machine scheduling problem considering a blocking constraint. In view of the above, we generalise this last finding by assuming a single transporter between each batch or processing machine. Theorem 5.8. Let 𝑎be the 𝐹2𝑚−1∥𝛾problem. Let 𝑏be the 𝐹𝑚|𝑇𝑚−1(𝑀𝑎𝑜, 𝐼 𝑖𝑗)|𝛾problem where there is a transporter between each pair of sequential machines. Both problems are therefore equivalent. Corollary 5.1. Let 𝑎be the 𝐹2𝑚−1|𝑏𝑎𝑡𝑐 ℎ|𝛾problem where machines 𝑖= 1,3,…,2𝑚− 1are single processing machines and machines 𝑖= 2,4,…,2𝑚− 2are 𝑝-batch processing machines. Let 𝑏be the 𝐹𝑚|𝑇𝑚−1(𝑀𝑎𝑜, 𝐵 𝑖𝑗)|𝛾problem where there is a transporter between each pair of sequential machines. 𝑎and 𝑏are therefore equivalent. As can be observed, many of the variants of the problem are equivalent to the traditional flow shop problem. It is therefore not surprising that many of the results build upon the advances established in the traditional flow shop. This is the case, for example, of the reversibility property, where the same makespan value can be found whether the problem is constructive forward or backward (see Ribas et al.,2010 for more details). This property can be applied, for example, to the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |𝐶𝑚𝑎𝑥 problem (Wang, Huang, & Li, 2018). Regarding other problem properties, Khatami et al. (2023) have established that a permutation schedule is not necessarily an optimal solution for the 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾problem. An examination of more constrained problems can also be found in Fondrevelle et al. (2009), Huo et al. (2009), who study specific properties for the no-wait two machine scheduling problem with 𝑇(𝑀 𝑜, 𝐼 𝑗), and in RaywardSmith and Rebaine (2008), Rebaine (2005), Yu et al. (2004), who analyse properties considering unit processing times and two machines. A summary of the equivalences identified in the literature and in this paper for the FSP considering transportation between stages is presented in Table 2. Finally, in many cases, NP-hardness of the problem has been ascertained. A detailed summary of these cases is presented in Table 3. 5.1.2. Optimisation algorithms 5.1.2.1. Transportation between stages with an unlimited number of transporters. Regarding the literature using optimisation algorithms to solve this type of problem, Maggu et al. (1981,1982), Mitten (1959), Rinnooy Kan (1976) are the first to address the problem of intermediate transportation. Studying the problem with two machines and a permutation constraint, they assume job-dependent transportation times and an unlimited number of transporters and propose exact algorithms based on Johnson (1954). These algorithms also find the optimum when the sum of weighted machine completion times is minimised (Fondrevelle et al.,2008). Munier-Kordon and Rebaine (2008) also propose two exact polynomial algorithms for the threeand four-machine problems, although they require processing times to be units. In cases where processing times are equal for the first and second machine for each job in the two-machine case, Ageev (2008) proposes a 3/2-approximation algorithm and several lower bounds. A 3/2 approximation algorithm and several lower bounds are proposed by Ageev and Baburin (2007) for the no-wait variant of the previous problem with unit processing times. The no-wait variant with transport times taking two values is addressed by Ageev (2020), who proposes a lower bound and a 2-approximation a algorithm. Regarding other constrained problems, Yang and Chern (2000) propose a polynomial exact algorithm for the permutation group scheduling variant. For the two-machine problem with both anticipatory and non-anticipatory sequence-independent setup times, Çetinkaya (2006) proposes a Johnson-based exact algorithm. The two-machine problem with no-wait (exact delays times approach) and missing operations is addressed by Leung et al. (2007), who propose several exact and approximation algorithms for some variants of the problem. Also in regard to minimising total completion times, Msakni et al. (2016) address the permutation two-machine scheduling problem with minimum time lags, proposing a branch-and-bound and an iterated greedy algorithm to solve the problem. The same problem with no-wait constraint (exact delays) is solved in Huo et al. (2009) with the proposal of several simple heuristics and two metaheuristics. Haouari and Ladhari (2000) propose a branch-and-bound algorithm for the 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑟𝑗|𝐿𝑚𝑎𝑥 problem, including a simple heuristic to obtain upper bounds and analysing different lower bounds. The two-machine problem without permutation constraint is addressed by Rayward-Smith and Rebaine (2008) for makespan minimisation and considering unit processing times. They propose two dispatching rules analysing their worst cases. Brucker et al. (2004) successfully prove that several variants of this problem are polynomially solvable (even with 𝑚machines) for different objective functions (total weighted completion times, total weighted number of jobs, and total weighted tardiness). Furthermore, Dell’Amico (1996) solves the problem with non-unit processing times (𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗)|𝐶𝑚𝑎𝑥), with four approximate algorithms, a tabu search metaheuristic, and several lower bounds. Also in relation to this problem, Mkadem et al. (2021) propose a branch-and-bound algorithm, which is compared with the previous exact algorithm in 480 instances. Khatami et al. (2023) prove that the no-wait variant of the previous problem is polynomial and propose several exact algorithms to solve some variants of this problem. Dhouib et al. (2018) consider maximum waiting times instead of the no-wait constraint and propose a new heuristic by taking into account properties of the problem. Furthermore, they propose an MILP model (which can also be applied to the 𝑚-machine problem) which outperformed the permutation MILP model proposed by Dhouib et al. (2013). The two-machine flow shop scheduling problem with time windows and equal travel times is shown to be polynomial by Zhang and van de Velde (2015) for maximisation of the weighted European Journal of Operational Research 325 (2025) 1–19 7 V. Fernandez-Viagas Table 2 Equivalence between problems. Problem A Problem B Reference TSP(a)𝐹2|𝑇1(𝑀 𝑟, 𝐼), 𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔|𝐶𝑚𝑎𝑥 Stern and Vitner (1990) 𝐹2||𝛾𝑟𝐹2|𝑇(𝑀 𝑜, 𝐼𝑗)|𝛾𝑟Maggu et al. (1981) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢|𝛾 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗)|𝐶𝑚𝑎𝑥 Mkadem et al. (2021) 𝐹𝑚||𝛾𝑟𝐹𝑚|𝑇(𝑀 𝑜, 𝐼)|𝛾𝑟Theorem 5.7 𝐹𝑚|𝑙𝑚𝑖𝑛 𝑗|𝛾 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑗)|𝛾Theorem 5.1 𝐹𝑚|𝑒𝑥𝑎𝑐 𝑡−𝑙𝑗|𝛾 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾Theorem 5.5 𝐹𝑚|𝑒𝑥𝑎𝑐 𝑡−𝑙𝑗|𝛾 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾Theorem 5.5 𝐹2|𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾Khatami et al. (2023) 𝐹2|𝑇(𝑀 𝑜, 𝐵), 𝑝𝑟𝑚𝑢|𝛾𝑟𝐹2|𝑇(𝑀 𝑜, 𝐼)|𝛾𝑟Lee and Chen (2001) 𝐹2𝑚−1||𝛾 𝐹𝑚|𝑇𝑚−1(𝑀𝑎𝑜, 𝐼 𝑖𝑗)|𝛾Theorem 5.8 𝐹(2𝑚− 1)|𝑏𝑎𝑡𝑐 ℎ|𝛾(machines 𝑖= 2,4,…are 𝑝-batch) 𝐹𝑚|𝑇𝑚−1(𝑀𝑎𝑜, 𝐵 𝑖𝑗)|𝛾Corollary 5.1 𝐹𝑚|𝑠𝑖𝑗 𝑘|𝛾(non-anticipatory 𝑠𝑖𝑗 𝑘)𝐹𝑚|𝑇(𝑆 𝑜, 𝐼 𝑗 𝑘)|𝛾Theorem 5.9 𝐹𝑚, 𝑆 𝜏|𝑠𝑖𝑗 𝑘|𝛾(non-anticipatory 𝑠𝑖𝑗 𝑘)𝐹𝑚|𝑇𝜏(𝑆 𝑜, 𝐼 𝑖𝑗 𝑘)|𝛾Theorem 5.10 𝐹𝑚|𝑠𝑖𝑗 𝑘|𝛾 𝐹𝑚|𝑅𝑚(𝑅𝑜, 𝐼 𝑗 𝑘)|𝛾Theorem 5.11 𝐹2|𝑅2(𝑅𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢|𝛾 𝐹2|𝑅2(𝑅𝑜, 𝐼 𝑗)|𝛾Theorem (Yu et al.,2011) 𝐹𝑚|𝑟𝑗|𝛾 𝐹𝑚|𝑇(𝑃 𝑜, 𝐼 𝑗)|𝛾Theorem 5.12 𝐹𝑚+1||𝛾 𝐹𝑚|𝑇1(𝑃 𝑟, 𝐼 𝑗)|𝛾Theorem 5.13 𝐹𝑚+1||𝛾 𝐹𝑚|𝑇1(𝑃 𝑜, 𝐼 𝑗)|𝛾Corollary 5.2 𝐻 𝐹𝑚+1 ,(𝑃 𝜏 , 𝐹𝑚)||𝛾 𝐹𝑚|𝑇𝜏(𝑃 𝑟, 𝐼 𝑗)|𝛾Corollary 5.3 𝐹𝑚||𝐿𝑚𝑎𝑥 𝐹𝑚|𝑇(𝐷 𝑜, 𝐼 𝑗)|𝐶𝐷 𝑚𝑎𝑥 Hall (1997) 𝐹𝑚||∑𝐶𝑗𝐹𝑚|𝑇(𝐷 𝑜, 𝐼 𝑗)|∑𝐶𝐷 𝑗Theorem 6.1 𝐹𝑚||∑𝐿𝑗𝐹𝑚|𝑇(𝐷 𝑜, 𝐼 𝑗)|∑𝐿𝐷 𝑗Corollary 6.1 𝐹𝑚|𝑟𝑗|∑𝐹𝑗𝐹𝑚|𝑇(𝐷 𝑜, 𝐼 𝑗), 𝑟𝑗|∑𝐹𝐷 𝑗Corollary 6.2 𝐹𝑚||𝐶𝑚𝑎𝑥 𝐹𝑚|𝑇(𝐷 𝑓 𝑜, 𝐼), 𝑡𝑗= 0|𝐶𝐷 𝑚𝑎𝑥 Hall et al. (2001) 𝐹𝑚||𝐿𝑚𝑎𝑥 𝐹𝑚|𝑇(𝐷 𝑓 𝑜, 𝐼), 𝑡𝑗= 0|𝐿𝐷 𝑚𝑎𝑥 Hall et al. (2001) 𝐹𝑚+1|𝑠𝑚+1,𝑗 |𝛾 𝐹𝑚|𝑇1(𝐷 𝑟, 𝐼 𝑗)|𝛾Theorem 6.2 𝐹𝑚+1||𝛾 𝐹𝑚|𝑇1(𝐷 𝑜, 𝐼 𝑗)|𝛾Corollary 6.3 𝐻 𝐹𝑚+1 ,(𝐹𝑚, 𝑃 𝜏)|𝑠𝑚+1,𝑗 |𝛾 𝐹𝑚|𝑇𝜏(𝐷 𝑟, 𝐼 𝑗)|𝛾Theorem 6.3 𝐻 𝐹𝑚+1 ,(𝐹𝑚, 𝑃 𝜏)||𝛾 𝐹𝑚|𝑇𝜏(𝐷 𝑜, 𝐼 𝑗)|𝛾Corollary 6.4 𝐹3|𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾 𝐹2|𝑇1(𝐷 𝑟, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝛾Soukhal et al. (2005) 𝐹𝑚|𝑇(𝐷 𝑟, 𝐼 𝑗)|𝛾 𝐹𝑚|𝑇(𝐶 , 𝐼 𝑗)|𝛾Theorem 6.4 𝐹𝑚|𝑇(𝐷 𝑟, 𝐵 𝑗)|𝛾 𝐹𝑚|𝑇(𝐶 , 𝐵 𝑗)|𝛾Corollary 6.5 𝐹𝑚||𝐿𝑚𝑎𝑥 𝐹𝑚|𝑇(𝐶 , 𝐼 𝑗)|𝐶𝐷 𝑚𝑎𝑥 Corollary 6.6 aTravelling salesman problem. number of selected jobs. To solve the problem, they propose a Dynamic Programming algorithm. Regarding the permutation problem with 𝑚machines, Szwarc (1983) proposes a lower bound for the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 problem. For both this problem and that with one specific transporter between each two consecutive machines, Naderi, Ahmadi Javid, and Jolai (2010) propose 3 MILP models, an artificial immune system, and adapt two dispatching rules and four constructive heuristics from related scheduling problems. Fondrevelle et al. (2006) also address this problem, although considering minimal and maximal time lags. They propose a branchand-bound algorithm using different lower bounds, which is initialised with several constructive heuristics. Also for this problem, Wang, Huang, and Li (2018) propose an MILP model and a constructive heuristic using its reversibility property. These proposals are compared with the best heuristics of Fondrevelle et al. (2006) and Hamdi and Loukil (2011). In this problem, Zhao et al. (2017) propose an iterated greedy algorithm, which also outperforms the genetic algorithm by Hamdi and Loukil (2011) and a constructive heuristic based on Fondrevelle et al. (2006). They also addressed the non-permutation variant of the problem. In contrast, the permutation variant of the problem with total tardiness minimisation is addressed by Hamdi and Loukil (2015a), Hamdi and Toumi (2019). The former propose and compare an MILP model, three dispatching rules, and several lower bounds for the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢, 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |∑𝑇𝑗problem, while the latter propose different MILP models for the 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢|∑𝑇𝑗 problem. In order to minimise the total number of jobs, Hamdi and Loukil (2015b) propose three dispatching rules and different lower bounds, whereas Fondrevelle et al. (2008) opt for the minimisation of the weighted sum of machine completion times, proposing a branchand-bound algorithm for the 𝑚-machine problem. The aspect of minimisation of maximum lateness is addressed in Fondrevelle et al. (2009). They propose a branch-and-bound algorithm using different lower bounds and initial solutions. The exact algorithm is compared with the proposal of Fondrevelle et al. (2005). In addition, a lexicographic optimisation of the problem is addressed by Dhouib et al. (2013) minimising the number of tardy jobs and the makespan, while also developing an MILP model and several variants of simulated annealing algorithms. Liou and Hsieh (2015) solve the multi-stage flow shop group scheduling with permutation and makespan minimisation by proposing a hybrid metaheuristic that combines both the Particle Swarm Optimisation (PSO) and GA algorithms. A variant of the flow shop with limited intermediate buffer, permutation, batch, and fixed intermediate transport dated is addressed by Prasad et al. (2006). They propose a genetic algorithm to solve both the minimisation of mean completion times of jobs and batches and that of the standard deviation of the completion times, which is tested against several different existing genetic algorithms. A comparison between permutation and European Journal of Operational Research 325 (2025) 1–19 8 V. Fernandez-Viagas Table 3 NP-hard scheduling problems with transportation between stages. Problem Reference Problem Reference 𝐹2|𝑇1(𝑀 𝑟, 𝐵𝑏)|𝐶𝑚𝑎𝑥 (𝑏≥3) (a)Lee and Chen (2001)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡|∑𝐶𝑗Leung et al. (2007) 𝐹2|𝑇1(𝑀 𝑟, 𝐼)|𝐶𝑚𝑎𝑥 (a)Lee and Chen (2001)𝐹2|𝑇(𝑀 𝑜, 𝐼), 𝑛𝑜 −𝑤𝑎𝑖𝑡|∑𝐶𝑗Leung et al. (2007) 𝐹2|𝑇1(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑝𝑖𝑗 =𝑝|𝐶𝑚𝑎𝑥 Hurink and Knust (2001)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑡𝑗∈ {𝑡′, 𝑡′′ }|∑𝑤𝑖𝐶𝑖Fondrevelle et al. (2008) 𝐹2|𝑇1(𝑀 𝑜, 𝐼), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 Hurink and Knust (2001)𝐹2|𝑇1(𝑀 𝑟, 𝐵), 𝑏𝑎𝑡𝑐 ℎ|𝐶𝑚𝑎𝑥 Tang and Liu (2009b) 𝐹2|𝑇1(𝑀 𝑟, 𝐼 𝑗), 𝑓 𝑎𝑚, 𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔|𝐶𝑚𝑎𝑥 Yuan et al. (2020)𝐹3|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑟𝑚𝑢, 𝑛𝑜 −𝑤𝑎𝑖𝑡|𝐶𝑚𝑎𝑥 Khatami et al. (2023) 𝐹2|𝑇1(𝑀 𝑟, 𝐼 𝑗), 𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔|𝐶𝑚𝑎𝑥 Ganesharajah et al. (1998)𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡, 𝑜𝑟𝑑 𝑒𝑟𝑒𝑑|𝐶𝑚𝑎𝑥 Khatami et al. (2023) 𝐹2|𝑇1(𝑀 𝑟, 𝐼), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 Kise et al. (1991b)𝐹2|𝑇2(𝑅𝑡𝑜, 𝐼 𝑗 𝑘)|𝐶𝑡𝑣 𝑚𝑎𝑥 Yu et al. (2011) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝1𝑗=𝑝2𝑗|𝐶𝑚𝑎𝑥 Dell’Amico and Vaessens (1996)𝐹2|𝑇(𝑃 𝑜, 𝐼 𝑗)|𝐶𝐷 𝑚𝑎𝑥 Lenstra et al. (1977) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗)|𝐶𝑚𝑎𝑥 (unary NP-complete) Dell’Amico (1996)𝐹2|𝑇1(𝐷 𝑟, 𝐵𝑏)|𝐶𝑚𝑎𝑥 (4≤𝑏≤𝑛∕2)Lee and Chen (2001) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑚𝑡𝑛|𝐶𝑚𝑎𝑥 (unary NP-complete) Dell’Amico (1996)𝐹2|𝑇1(𝐷 𝑟, 𝐼)|𝐶𝑚𝑎𝑥 (a)Lee and Chen (2001) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑟𝑗, 𝑝𝑖𝑗 = 1|∑𝐶𝑗Brucker et al. (2004)𝐹2|𝑇(𝐷 𝑜, 𝐼 𝑗)|𝐶𝐷 𝑚𝑎𝑥 Lenstra et al. (1977) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑖𝑗 = 1|∑𝑤𝑗𝐶𝑗Brucker et al. (2004)𝐹2|𝑇1(𝐷 𝑟, 𝐵)|𝐶𝑚𝑎𝑥 Pan et al. (2009) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝1𝑗=𝑝2𝑗, 𝑡𝑗∈ {0, 𝑙}|𝐶𝑚𝑎𝑥 Yu (1996)𝐹2|𝑇1(𝐷 𝑟, 𝐵)|∑𝐶𝑗Pan et al. (2009) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑖𝑗 = 1|∑𝐶𝑖[𝑛]Fondrevelle et al. (2008)𝐹2|𝑇1(𝐷 𝑟, 𝐵2𝑗)|𝐶𝑚𝑎𝑥 Soukhal et al. (2005) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑝𝑖𝑗 = 1|𝐶𝑚𝑎𝑥 Yu et al. (2004)𝐹2|𝑇1(𝐷 𝑟, 𝐵2𝑗), 𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔|𝐶𝑚𝑎𝑥 Soukhal et al. (2005) 𝐹2|𝑇(𝑀 𝑜, 𝐼), 𝑤𝑡𝑚𝑎𝑥 |𝐶𝑚𝑎𝑥 Fondrevelle et al. (2006)𝐹2|𝑇1(𝐷 𝑟, 𝐵3)|𝐶𝑚𝑎𝑥 Soukhal et al. (2005) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡, 𝑡𝑗∈ {𝑡′, 𝑡′′ }|𝐶𝑚𝑎𝑥 Leung et al. (2007)𝐹2|𝑇1(𝐷 𝑟, 𝐵3), 𝑝1𝑗=𝑝|𝐶𝑚𝑎𝑥 Yuan et al. (2007) 𝐹2|𝑇(𝑀 𝑜, 𝐼 𝑗), 𝑛𝑜 −𝑤𝑎𝑖𝑡, 𝑝𝑖𝑗 = 1|𝐶𝑚𝑎𝑥 Leung et al. (2007)𝐹2|𝑇1(𝐷 𝑟, 𝐵3), 𝑏𝑙 𝑜𝑐 𝑘𝑖𝑛𝑔|𝐶𝑚𝑎𝑥 Soukhal et al. (2005) aIt is NP-hard even when the travel times in both directions are identical. non-permutation constraints is performed by Rebaine (2005), comparing the worst-case performance ratio between the best solutions of 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 and 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗)|𝐶𝑚𝑎𝑥 either when processing times are unit or the number of machines is two. In relation solely with the non-permutation problem with 𝑚machines, Samarghandi (2019) proposes an MILP model and two constraint programming algorithms to exactly solve small instances of the 𝐹𝑚|𝑇(𝑀 𝑜, 𝐼 𝑖𝑗), 𝑤𝑡𝑚𝑎𝑥 𝑖𝑗 |𝐶𝑚𝑎𝑥 problem, and a Tabu Search metaheuristic for large-sized instances. The latter outperforms the memetic algorithm proposed by Caumond et al. (2008), which is adapted from the jobshop layout. This algorithm is also outperformed by Ye et al. (2017), who propose five versions of the iterated greedy algorithm. Zhang and Van De Velde (2010) propose an approximate algorithm for the problem with missing operations, minimising total completion times, and another that considers release times and makespan minimisation. The problem of allowing multiple operations of a job at the same stage (denoted recirculation) is addressed by Riezebos and Gaalman (1998), Riezebos et al. (1995), who propose several lower bounds and simple constructive heuristics, considering release times. 5.1.2.2. Transportation between stages with a finite number of transporters. Regarding a finite number of transporters, Panwalkar (1991) proposes a Johnson-based exact algorithm for the two-machine problem with constant travel times, blocking, and a single transporter, while Lee and Chen (2001) propose an approximate algorithm and different polynomial exact algorithms for specific variants of the problem. Hurink and Knust (2001) also propose two polynomial exact algorithms for two variants of the two-machine scheduling problem (with constant processing times and binary transportation times, and unit processing times) and for the 𝑚-machine problem with constant processing times with job-independent transportation times. Lee and Strusevich (2005) address the two-machine flow shop with intermediate transportation with non-negligible time to return the transporter to the first machine. Jobs are moved using a transporter with infinite capacity. To solve this problem, the authors propose an approximate algorithm that is at most (3/2) times the optimum. This problem with a batch is addressed by Zhong and Chen (2015), who propose a Johnson-based approximate algorithm whose limits are theoretically analysed. Individual transportation is applied by Tang et al. (2010), who propose a constructive heuristic. Similarly, Gong and Tang (2011) address a related twomachine flow shop, although transporting jobs in batches (with a single transporter with limited capacity), with each job occupying a physical space within the batch. The authors propose two approximate algorithms for the problem and for the specific case where all jobs occupy the same space. This algorithm is outperformed in Dong et al. (2016) by modifying the bin-packing algorithm and the first and last batches of the schedule (where the algorithm solution is at most 11/5 of the optimum). In turn, this algorithm was recently outperformed in Lan et al. (2024) (with at most 5/3 of the optimum) considering identical sizes for all jobs. Tang and Liu (2009b) consider that the second machine is a batch machine and solve this problem with a mathematical model, and a simple heuristic. They also analyse the worst case of the the simple heuristic, comparing it with two lower bounds. A similar research is carried out by Tang and Liu (2009a) considering that the first machine is batch and the second one is a single machine. The last two parallel batch approaches are also addressed by Behnamian et al. (2012b), who propose an MILP model and a heuristic for each of the previous cases. Wang et al. (2022) tackle the two-machine flow shop scheduling problem with a parallel batch machine and a single processing machine, considering transport times between both machines, which can be done in batches. They assume a constant round-trip time as transport time which is the same for the outward and return trips. To solve the problem, they propose an approximate algorithm which is compared with an MILP model. Stern and Vitner (1990) address the two-machine flow shop scheduling problem with non-negligible time to return the transport between stages and with zero intermediate buffer. They develop an approximate polynomial algorithm that reduces the problem to an asymmetric travelling salesman problem, which is then compared to a proposed lower bound of the problem. Yuan et al. (2020) consider the two-machine group scheduling with transportation times between both machines, where some jobs cannot be stored in the buffer (partial blocking of jobs), and the makespan is minimised. They propose both an MILP model and a co-evolutionary genetic algorithm. The genetic algorithm is compared with different variants of the algorithm and with state-of-the-art algorithms for related scheduling problems. The problem with fuzzy data is addressed by Gupta et al. (2013) for two machines and considering setup times, proposing an exact algorithm for both makespan and total flow time as single objectives. In case of other objective functions, Stevens and Gemmill (1997) address the twomachine flow shop scheduling problem with round-trip and constant travel times. In order to minimise maximum lateness, they propose two constructive heuristics, which are compared with the minimum European Journal of Operational Research 325 (2025) 1–19 9 V. Fernandez-Viagas Fig. 4. Proposed contributions and methodologies. relationships of the problems under study with related scheduling problems have also been studied. In light of this review and the points highlighted in the previous section, the following conclusions and future research lines can be identified: •From previous points 3,4,5, and 6, it follows that there is no exhaustive comparison of algorithms. In turn, this conclusion leads to the following lines of research: –An extensive computational evaluation of exact and approximate algorithms is pertinent. –Small, medium, and large-size benchmark instances are needed to compare the proposals. –Future proposals for developing optimisation algorithms should be compared with previous state-of-the art algorithms from the problem under consideration. In case of new proposals for novel scheduling problems, these should be compared with algorithms adapted from related or equivalent scheduling problems under the same conditions, when possible, or with exact approaches designed for the problem (in case of new approximate approaches). •Despite increased interest in the problem in recent years, there are still several problems (see previous points 2,7,10, and 11) which have neither been analysed nor solved. •Almost all papers address problems with transport considering deterministic data. It would be of interest to further analyse these types of problems with stochasticity, especially as regards transport times, a point which, to the best of our knowledge, has not yet been touched upon. •In addition, most papers are focused on traditional evolutionary or non-population-based algorithms. Only a single reference used a reinforcement learning-based method, and none mentioned neural networks or machine learning directly. Further research into the performance of these innovative techniques for the under study would be beneficial. In addition, the following significant challenges are open to future academics and practitioners interested in the problem. •Although a theoretical analysis of the relationship between the problems under consideration and related ones is presented in this paper, this analysis should be empirically extended. That is, complete enumerations and optimal solution analyses are needed to establish other limits for the problems, such as the analysis pinpointing when the integrated routing and scheduling problem is more closely related to the scheduling associate problem or to its equivalent vehicle routing problem. •Despite the importance of speed-up methods in flow-shop-based scenarios (see e.g. Fernandez-Viagas,2022;Fernandez-Viagas et al.,2020;Fernandez-Viagas, Talens, & Framinan,2022;Geng & Li,2023;Taillard,1990;Tao et al.,2023;Wang et al.,2023), we are not aware of any related method for the flow shop problem with transportation. •The technological advances brought about by Industry 4.0 allow real-time information updates to be considered (processing times, due dates, release times, transport times, ...) in the shop (Fernandez-Viagas & Framinan,2022). These new industry 4.0based scenarios (see e.g. Fathollahi-Fard et al.,2024;Ghaleb & Taghipour,2023;Ghaleb et al.,2020;Li & Huang,2021) would be of great interest in the field. •Finally, although many applications in the literature have been solved compared to related scheduling problem, the literature should move towards more realistic applications rather than the current predominant theoretical variants. Therefore, theoretical studies should focus more on traditional problems without many constraints, whereas more constrained problems should be addressed mainly as real-world applications. CRediT authorship contribution statement Victor Fernandez-Viagas: Writing – review & editing, Writing – original draft, Visualization, Validation, Supervision, Software, Resources, Project administration, Methodology, Investigation, Funding acquisition, Formal analysis, Data curation, Conceptualization. Acknowledgements The authors wish to thank the referees for their comments on the earlier versions of the manuscript. This study has been funded by Instituto de Salud Carlos III (ISCIII) through the project ‘‘PI22/01096’’ and co-funded by the European Union. This research was also supported by the European Commission, under the project ExPliCit (ref.101086465 - HORIZON-MSCA-2021-SE-01-01) Appendix A. Supplementary data Supplementary material related to this article can be found online at https://doi.org/10.1016/j.ejor.2024.11.034. References Ageev, A. (2008). A 3/2-Approximation for the proportionate two-machine flow shop scheduling with minimum delays. Journal of Applied and Industrial Mathematics, 2(4), 447–454. Ageev, A. (2020). Approximating the 2-machine flow shop problem with exact delays taking two values. Journal of Global Optimization,76(3), 491–497. Ageev, A. A., & Baburin, A. E. (2007). Approximation algorithms for UET scheduling problems with exact delays. Operations Research Letters,35(4), 533–540. Aguirre, A., Méndez, C., & Castro, P. (2011). A novel optimization method to automated wet-etch station scheduling in semiconductor manufacturing systems. Computers and Chemical Engineering,35(12), 2960–2972. Aguirre, A., Méndez, C., & Castro, P. (2014). A hybrid scheduling approach for automated flowshops with material handling and time constraints. International Journal of Production Research,52(9), 2788–2806. Ahmadi-Javid, A., & Hooshangi-Tabrizi, P. (2015). A mathematical formulation and anarchic society optimisation algorithms for integrated scheduling of processing and transportation operations in a flow-shop environment. International Journal of Production Research,53(19), 5988–6006. European Journal of Operational Research 325 (2025) 1–19 16 V. Fernandez-Viagas Amraoui, A. E., & Elhafsi, M. (2016). An efficient new heuristic for the hoist scheduling problem. Computers & Operations Research,67, 184–192. Averbakh, I., & Berman, O. (1996). Routing two-machine flowshop problems on networks with special structure. Transportation Science,30(4), 303–314. Averbakh, I., & Berman, O. (1999). A simple heuristic for m-machine flow-shop and its applications in routing-scheduling problems. Operations Research,47(1), 165–170. Azad, T., Rahman, H. F., Chakrabortty, R. K., & Ryan, M. J. (2022). Optimization of integrated production scheduling and vehicle routing problem with batch delivery to multiple customers in supply chain. Memetic Computing,14(3), 355–376. Behnamian, J., Fatemi Ghomi, S., Jolai, F., & Amirtaheri, O. (2012a). Minimizing makespan on a three-machine flowshop batch scheduling problem with transportation using genetic algorithm. Applied Soft Computing,12(2), 768–777. Behnamian, J., Fatemi Ghomi, S., Jolai, F., & Amirtaheri, O. (2012b). Realistic twostage flowshop batch scheduling problems with transportation capacity and times. Applied Mathematical Modelling,36(2), 723–735. Berghman, L., Kergosien, Y., & Billaut, J.-C. (2023). A review on integrated scheduling and outbound vehicle routing problems. European Journal of Operational Research, 311(1), 1–23. Bhushan, S., & Karimi, I. (2003). An MILP approach to automated wet-etch station scheduling. Industrial & Engineering Chemistry Research,42(7), 1391–1399. Bhushan, S., & Karimi, I. (2004). Heuristic algorithms for scheduling an automated wet-etch station. Computers and Chemical Engineering,28(3), 363–379. Boufellouh, R., & Belkaid, F. (2023). Multi-objective optimization for energy-efficient flow shop scheduling problem with blocking and collision-free transportation constraints. Applied Soft Computing,148. Brucker, P., Knust, S., Cheng, T., & Shakhlevich, N. (2004). Complexity results for flow-shop and open-shop scheduling problems with transportation delays. Annals of Operations Research,129(1–4), 81–106. Castro, P. M., Aguirre, A. M., Zeballos, L. J., & Méndez, C. A. (2011). Hybrid mathematical programming discrete-event simulation approach for large-scale scheduling problems. Industrial & Engineering Chemistry Research,50(18), 10665–10680. Castro, P. M., Zeballos, L. J., & Méndez, C. A. (2012). Hybrid time slots sequencing model for a class of scheduling problems. AIChE Journal,58(3), 789–800. Caumond, A., Lacomme, P., & Tchernev, N. (2008). A memetic algorithm for the job-shop with time-lags. Computers & Operations Research,35(7), 2331–2356. Çetinkaya, F. C. (2006). Unit sized transfer batch scheduling in an automated twomachine flow-line cell with one transport agent. International Journal of Advanced Manufacturing Technology,29(1–2), 178–183. Chernykh, I., Kononov, A., & Sevastyanov, S. (2023). An exact solution with an improved running time for the routing flow shop problem with two machines. Journal of Scheduling. Chevroton, H., Kergosien, Y., Berghman, L., & Billaut, J.-C. (2021). Solving an integrated scheduling and routing problem with inventory, routing and penalty costs. European Journal of Operational Research,294(2), 571–589. Chevroton, H., Rohmer, S., & Billaut, J.-C. (2021). A production and distribution framework: Manufacturer dominates. Computers & Industrial Engineering,155. Dell’Amico, M. (1996). Shop problems with two machines and Time Lags. Operations Research,44(5), 777–787. Dell’Amico, M., & Vaessens, R. (1996). Flow and open shop scheduling on two machines with transportation times and machine-independent processing times is NP-hard. Materiali Di Discussione,141. Dev, N., Shankar, R., & Swami, S. (2020). Diffusion of green products in industry 4.0: Reverse logistics issues during design of inventory and production planning system. International Journal of Production Economics,223. Dhouib, E., Teghem, J., & Loukil, T. (2013). Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints. International Transactions in Operational Research,20(2), 213–232. Dhouib, E., Teghem, J., & Loukil, T. (2018). Non-permutation flowshop scheduling problem with minimal and maximal time lags: Theoretical study and heuristic. Annals of Operations Research,267(1–2), 101–134. Dong, J., Wang, X., Hu, J., & Lin, G. (2016). An improved two-machine flowshop scheduling with intermediate transportation. Journal of Combinatorial Optimization, 31(3), 1316–1334. Echchakoui, S., & Barka, N. (2020). Industry 4.0 and its impact in plastics industry: A literature review. Journal of Industrial Information Integration,20. Fabri, M., Ramalhinho, H., De Souza, M. C., & Ravetti, M. G. (2019). The Lagrangean relaxation for the flow shop scheduling problem with precedence constraints, release dates and delivery times. Journal of Advanced Transportation,2019. Fathollahi-Fard, A. M., Woodward, L., & Akhrif, O. (2024). A distributed permutation flow-shop considering sustainability criteria and real-time scheduling. Journal of Industrial Information Integration,39, Article 100598. Fernandez-Viagas, V. (2022). A speed-up procedure for the hybrid flow shop scheduling problem. Expert Systems with Applications,187. Fernandez-Viagas, V., & Framinan, J. (2015). A new set of high-performing heuristics to minimise flowtime in permutation flowshops. Computers & Operations Research, 53, 68–80. Fernandez-Viagas, V., & Framinan, J. (2022). Exploring the benefits of scheduling with advanced and real-time information integration in industry 4.0: A computational study. Journal of Industrial Information Integration,27. Fernandez-Viagas, V., Molina-Pariente, J., & Framinan, J. (2020). Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling. European Journal of Operational Research,282(3), 858–872. Fernandez-Viagas, V., Sanchez-Mediano, L., Angulo-Cortes, A., Gomez-Medina, D., & Molina-Pariente, J. M. (2022). The permutation flow shop scheduling problem with human resources: MILP models, decoding procedures, NEH-based heuristics, and an iterated greedy algorithm. Mathematics,10(19). Fernandez-Viagas, V., Talens, C., & Framinan, J. (2022). Assembly flowshop scheduling problem: Speed-up procedure and computational evaluation. European Journal of Operational Research,299(3), 869–882. Fondrevelle, J., Allahverdi, A., & Oulamara, A. (2005). Two-machine, no-wait flowshop scheduling problem to minimize maximum lateness with separate set-up and removal times. International Journal of Agile Manufacturing,8(2), 165–174. Fondrevelle, J., Oulamara, A., & Portmann, M.-C. (2006). Permutation flowshop scheduling problems with maximal and minimal time lags. Computers & Operations Research,33(6), 1540–1556. Fondrevelle, J., Oulamara, A., & Portmann, M.-C. (2008). Permutation flowshop scheduling problems with time lags to minimize the weighted sum of machine completion times. International Journal of Production Economics,112(1), 168–176. Fondrevelle, J., Oulamara, A., Portmann, M.-C., & Allahverdi, A. (2009). Permutation flow shops with exact time lags to minimise maximum lateness. International Journal of Production Research,47(23), 6759–6775. Ganesharajah, T., Hall, N. G., & Sriskandarajah, C. (1998). Design and operational issues in AGV-served manufacturing systems. Annals of Operations Research,76, 109–154. Geiger, C., Kempf, K., & Uzsoy, R. (1997). A tabu search approach to scheduling an automated wet etch station. Journal of Manufacturing Systems,16(2), 102–116. Geng, Y.-D., & Li, J.-Q. (2023). A knowledge-driven multiobjective algorithm for distributed hybrid flowshop with group and carryover setup in glass manufacturing systems. Computers & Industrial Engineering,181, Article 109325. Ghaleb, M., & Taghipour, S. (2023). Dynamic shop-floor scheduling using real-time information: A case study from the thermoplastic industry. Computers & Operations Research,152, Article 106134. Ghaleb, M., Zolfagharinia, H., & Taghipour, S. (2020). Real-time production scheduling in the Industry-4.0 context: Addressing uncertainties in job arrivals and machine breakdowns. Computers & Operations Research,123, Article 105031. Gnatowski, A., Rudy, J. a., & Idzikowski, R. a. (2022). Scheduling disjoint setups in a single-server permutation flow shop manufacturing process. Processes,10(9). Gong, H., & Tang, L. (2011). Two-machine flowshop scheduling with intermediate transportation under job physical space consideration. Computers & Operations Research,38(9), 1267–1274. Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics,5, 287–326. Gu, J., Gu, M., & Gu, X. (2015). A mutualism quantum genetic algorithm to optimize the flow shop scheduling with pickup and delivery considerations. Mathematical Problems in Engineering,2015. Gupta, D., Sharma, S., & Aggarwal, S. (2013). Flow shop scheduling on 2-machines with setup time and single transport facility under fuzzy environment. OPSEARCH, 50(1), 14–24. Hall, L. (1997). Approximation algorithms for scheduling. Approximation Algorithms for NP-Hard Problems, 1–45. Hall, N. G., Lesaoana, M., & Potts, C. N. (2001). Scheduling with fixed delivery dates. Operations Research,49(1), 134–144. Hamdi, I., & Loukil, T. (2011). Minimizing the makespan in the permutation flowshop problem with minimal and maximal time lags. In 2011 international conference on communications, computing and control applications. Hamdi, I., & Loukil, T. (2015a). Minimizing total tardiness in the permutation flowshop scheduling problem with minimal and maximal time lags. Operational Research, 15(1), 95–114. Hamdi, I., & Loukil, T. c. (2015b). Upper and lower bounds for the permutation flowshop scheduling problem with minimal time lags. Optimization Letters,9(3), 465–482. Hamdi, I., & Toumi, S. (2019). MILP models and valid inequalities for the twomachine permutation flowshop scheduling problem with minimal time lags. Journal of Industrial Engineering International,15, 223–229. Haouari, M., & Ladhari, T. (2000). Minimising maximum lateness in a two-machine flowshop. Journal of the Operational Research Society,51(9), 1100–1106. Hosseini, A., Otto, A., & Pesch, E. (2023). Scheduling in manufacturing with transportation: Classification and solution techniques. European Journal of Operational Research. Huo, Y., Li, H., & Zhao, H. (2009). Minimizing total completion time in two-machine flow shops with exact delays. Computers & Operations Research,36(6), 2018–2030. Hurink, J., & Knust, S. (2001). Makespan minimization for flow-shop problems with transportation times and a single robot. Discrete Applied Mathematics,112(1–3), 199–216. Hurink, J., & Knust, S. (2005). Tabu search algorithms for job-shop problems with a single transport robot. European Journal of Operational Research,162(1), 99–111, Logistics: From Theory to Application. European Journal of Operational Research 325 (2025) 1–19 17 V. Fernandez-Viagas Jiang, E. D., & Wang, L. (2019). An improved multi-objective evolutionary algorithm based on decomposition for energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time. International Journal of Production Research,57(6), 1756–1771. Johnson, S. (1954). Optimal twoand three-stage production schedules with setup times included. Naval Research Logistics Quarterly,1(1), 61–68. Jolai, F., & Abedinnia, H. (2013). Consideration of transportation lags in a two-machine flow shop scheduling problem. Scientia Iranica,20(6), 2215–2223. Józefczyk, J., Markowski, M., & Balgabaeva, L. (2014). Routing flow-shop with buffers and ready times-comparison of selected solution algorithms. Management and Production Engineering Review,5(4), 26–35. Kaminsky, P. (2003). The effectiveness of the longest delivery time rule for the flow shop delivery time problem. Naval Research Logistics,50(3), 257–272. Khalili, M. (2014). An electromagnetism-inspired method for a generalized flowshop problem. Manufacturing Review,1. Khalili, M., & Tavakkoli-Moghaddam, R. (2012). A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem. Journal of Manufacturing Systems,31(2), 232–239. Khatami, M., Salehipour, A., & Cheng, T. (2023). Flow-shop scheduling with exact delays to minimize makespan. Computers & Industrial Engineering,183. Kim, M., Jung, J. H., & Lee, I.-B. (1996). Optimal scheduling of multiproduct batch processes for various intermediate storage policies. Industrial & Engineering Chemistry Research,35(11), 4058–4066. Kim, Y.-D., Lim, H.-G., & Park, M.-W. (1996). Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process. European Journal of Operational Research,91(1), 124–143. Kise, H., Shioyama, T., & Ibaraki, T. (1991a). Automated two-machine flowshop scheduling: A solvable case. IIE Transactions (Institute of Industrial Engineers),23(1), 10–16. Kise, H., Shioyama, T., & Ibaraki, T. (1991b). On an automated two-machine flowshop scheduling problem with infinite buffer. The Operations Research Society of Japan, 34(3), 354–361. Komaki, G., Sheikh, S., & Malakooti, B. (2019). Flow shop scheduling problems with assembly operations: A review and new trends. International Journal of Production Research,57(10), 2926–2955. Kumar, H., Kumar, P., & Sharma, M. (2019). A genetic algorithm for a flow shop scheduling problem with breakdown interval, transportation time and weights of jobs. International Journal of Operational Research,35(4), 470–483. Lacomme, P., Larabi, M., & Tchernev, N. (2013). Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles. International Journal of Production Economics,143(1), 24–34. Lan, Y., Yuan, Y., Wang, Y., Han, X., & Zhou, Y. (2024). Flow shop scheduling problems with transportation constraints revisited. Theoretical Computer Science,985. Lee, C.-Y., & Chen, Z.-L. (2001). Machine scheduling with transportation considerations. Journal of Scheduling,4(1), 3–24. Lee, C.-Y., & Strusevich, V. A. (2005). Two-machine shop scheduling with an uncapacitated interstage transporter. IIE Transactions,37(8), 725–736. Lenstra, J., Rinnooy Kan, A., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics,1(C), 343–362. Leung, J. Y.-T., Li, H., & Zhao, H. (2007). Scheduling two-machine flow shops with exact delays. International Journal of Foundations of Computer Science,18(2), 341–359. Levner, E., Kogan, K., & Maimon, O. (1995). Flowshop scheduling of robotic cells with job-dependent transportation and set-up effects. Journal of the Operational Research Society,46(12), 1447–1455. Li, M., & Huang, G. Q. (2021). Production-intralogistics synchronization of industry 4.0 flexible assembly lines under graduation intelligent manufacturing system. International Journal of Production Economics,241, Article 108272. Li, H., Liu, J., Wang, Y., & Zhuang, C. (2023). A multi-objective complex product assembly scheduling problem considering transport time and worker competencies. Advanced Engineering Informatics,58, Article 102233. Liou, C.-D., & Hsieh, Y.-C. (2015). A hybrid algorithm for the multi-stage flow shop group scheduling with sequence-dependent setup and transportation times. International Journal of Production Economics,170, 258–267. Lu, Y. (2017). Industry 4.0: A survey on technologies, applications and open research issues. Journal of Industrial Information Integration,6, 1–10. Lu, C., Gao, L., Li, X., Pan, Q., & Wang, Q. (2017). Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm. Journal of Cleaner Production,144, 228–238. Maggu, P., Das, G., & Kumar, R. (1981). On equivalent-job for job-block in 2 x n sequencing problem with transportation-times. Journal of the Operations Research Society of Japan,24(2), 136–146. Maggu, P., Singhal, M. L., Mohammad, N., & Yadav, S. K. (1982). On n-job, 2-machine flow-shop scheduling problem with arbitrary time lags and transportation times of jobs. Journal of the Operations Research Society of Japan,25(3), 219–227. Mazdeh, M. M., & Rostami, M. (2014). A branch-and-bound algorithm for two-machine flow-shop scheduling problems with batch delivery costs. International Journal of Systems Science: Operations and Logistics,1(2), 94–104. Mitten, L. (1959). Sequencing n jobs on two machines with arbitrary time lags. Management Science,5(3), 293–298. Miyata, H., & Nagano, M. (2019). The blocking flow shop scheduling problem: A comprehensive and conceptual review. Expert Systems with Applications,137, 130–156. Mkadem, M. A., Moukrim, A., & Serairi, M. (2021). Exact method for the two-machine flow-shop problem with time delays. Annals of Operations Research,298(1–2), 375–406. Mohammadi, S., Cheraghalikhani, A., & Ramezanian, R. (2018). A joint scheduling of production and distribution operations in a flow shop manufacturing system. Scientia Iranica,25(2E), 911–930. Msakni, M. K., Khallouli, W., Al-Salem, M., & Ladhari, T. (2016). Minimizing the total completion time in a two-machine flowshop problem with time delays. Engineering Optimization,48(7), 1164–1181. Munier-Kordon, A., & Rebaine, D. (2008). Polynomial time algorithms for the UET permutation flowshop problem with time delays. Computers & Operations Research, 35(2), 525–537. Naderi, B., Ahmadi Javid, A., & Jolai, F. (2010). Permutation flowshops with transportation times: Mathematical models and solution methods. International Journal of Advanced Manufacturing Technology,46(5–8), 631–647. Naderi, B., Tavakkoli-Moghaddam, R., & Khalili, M. (2010). Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan. Knowledge-Based Systems, 23(2), 77–85. Nawaz, M., Enscore, J. E. E., & Ham, I. (1983). A heuristic algorithm for the 𝑚machine, 𝑛-job flow-shop sequencing problem. OMEGA, the International Journal of Management Science,11(1), 91–95. Neufeld, J. S., Schulz, S., & Buscher, U. (2023). A systematic review of multi-objective hybrid flow shop scheduling. European Journal of Operational Research,309(1), 1–23. Pan, J. C.-H., Wu, C.-L., Huang, H.-C., & Su, C.-S. (2009). Coordinating scheduling with batch deliveries in a two-machine flow shop. International Journal of Advanced Manufacturing Technology,40(5–6), 607–616. Panwalkar, S. (1991). Scheduling of a two-machine flowshop with travel time between machines. Journal of the Operational Research Society,42(7), 609–613. Paul, H. J., Bierwirth, C., & Kopfer, H. (2007). A heuristic scheduling procedure for multi-item hoist production lines. International Journal of Production Economics, 105(1), 54–69. Pessoa, L., & Andrade, C. (2018). Heuristics for a flowshop scheduling problem with stepwise job objective function. European Journal of Operational Research,266(3), 950–962. Pinedo, M. (2012). Scheduling: Theory, algorithms and systems. Springer. Porselvi, S., Balaji, A., & Jawahar, N. (2018). Artificial immune system and particle swarm optimisation algorithms for an integrated production and distribution scheduling problem. International Journal of Logistics Systems and Management,30(1), 31–68. Prasad, S. D., Rajendran, C., & Chetty, O. V. K. (2006). A genetic algorithmic approach to multi-objective scheduling in a kanban-controlled flowshop with intermediate buffer and transport constraints. International Journal of Advanced Manufacturing Technology,29(5–6), 564–576. Rahman, H. F., Janardhanan, M. N., Poon Chuen, L., & Ponnambalam, S. (2021). Flowshop scheduling with sequence dependent setup times and batch delivery in supply chain. Computers & Industrial Engineering,158, Article 107378. Rajagopalan, D., & Karimi, I. (1989). Completion times in serial mixed-storage multiproduct processes with transfer and set-up times. Computers and Chemical Engineering,13(1), 175–186. Ramesh Kumar, R. G., & Tiwari, M. K. (2020). Quantitative approaches for the integration of production and distribution planning in the supply chain: A systematic literature review. International Journal of Production Research,58(11), 3527–3553. Ramezanian, R., Mohammadi, S., & Cheraghalikhani, A. (2017). Toward an integrated modeling approach for production and delivery operations in flow shop system: Trade-off between direct and routing delivery methods. Journal of Manufacturing Systems,44, 79–92. Rasti-Barzoki, M., Hejazi, S., & Mazdeh, M. (2013). A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs. Applied Mathematical Modelling,37(7), 4924–4937. Rayward-Smith, V., & Rebaine, D. (2008). Analysis of heuristics for the UET twomachine flow shop problem with time delays. Computers & Operations Research, 35(10), 3298–3310. Rebaine, D. (2005). Flow shop vs. permutation shop with time delays. Computers & Industrial Engineering,48(2), 357–362. Ribas, I., Companys, R., & Tort-Martorell, X. (2010). Comparing three-step heuristics for the permutation flow shop problem. Computers & Operations Research,37(12), 2062–2070. Riezebos, J., & Gaalman, G. (1998). Time lag size in multiple operations flow shop scheduling heuristics. European Journal of Operational Research,105(1), 72–90. Riezebos, J., Gaalman, G., & Gupta, J. (1995). Flow shop scheduling with multiple operations and time lags. Journal of Intelligent Manufacturing,6(2), 105–115. Rinnooy Kan, A. H. G. (1976). Machine scheduling problems: Classification, complexity and computations. The Hague: Martinus Nijhoff. Rolim, G. A., & Nagano, M. S. (2020). Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows: A review. Computers & Industrial Engineering,149, Article 106803. European Journal of Operational Research 325 (2025) 1–19 18 V. Fernandez-Viagas Rossit, D., Tohmé, F., & Frutos, M. (2018). The Non-Permutation Flow-Shop scheduling problem: A literature review. Omega (United Kingdom),77, 143–153. Rossit, D., Tohmé, F., & Frutos, M. (2019). Production planning and scheduling in Cyber-Physical Production Systems: A review. International Journal of Computer Integrated Manufacturing,32(4–5), 385–395. Safaei, A., Moattar Husseini, S., Farahani, R. Z., Jolai, F., & Ghodsypour, S. (2010). Integrated multi-site production-distribution planning in supply chain by hybrid modelling. International Journal of Production Research,48(14), 4043–4069. Samarghandi, H. (2019). Minimizing the makespan in a flow shop environment under minimum and maximum time-lag constraints. Computers & Industrial Engineering, 136, 614–634. Sekkal, D. N., & Belkaid, F. (2023). A multi-objective optimization algorithm for flow shop group scheduling problem with sequence dependent setup time and worker learning. Expert Systems with Applications,233. Soukhal, A., Oulamara, A., & Martineau, P. (2005). Complexity of flow shop scheduling problems with transportation constraints. European Journal of Operational Research, 161(1), 32–41. Stern, H., & Vitner, G. (1990). Scheduling parts in a combined production-transportation work cell. Journal of the Operational Research Society,41(7), 625–632. Stevens, J., & Gemmill, D. (1997). Scheduling a two-machine flowshop with travel times to minimize maximum lateness. International Journal of Production Research, 35(1), 1–15. Su, J., Fu, Y., Gao, K., Dong, H., & Mou, J. (2023). Integrated scheduling problems of open shop and vehicle routing using an ensemble of group teaching optimization and simulated annealing. Swarm and Evolutionary Computation,83, Article 101373. Szwarc, W. (1983). Flow shop problems with time lags. Management Science,29(4), 477–481. Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research,47(1), 65–74. Tang, L., Guan, J., & Hu, G. (2010). Steelmaking and refining coordinated scheduling problem with waiting time and transportation consideration. Computers & Industrial Engineering,58(2), 239–248. Tang, L., & Liu, P. (2009a). Flowshop scheduling problems with transportation or deterioration between the batching and single machines. Computers & Industrial Engineering,56(4), 1289–1295. Tang, L., & Liu, P. (2009b). Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration. Applied Mathematical Modelling,33(2), 1187–1199. Tao, X.-R., Pan, Q.-K., Sang, H.-Y., Gao, L., Yang, A.-L., & Rong, M. (2023). Nondominated sorting genetic algorithm-II with Q-learning for the distributed permutation flowshop rescheduling problem. Knowledge-Based Systems,278, Article 110880. Tonizza Pereira, M., & Seido Nagano, M. (2022). Hybrid metaheuristics for the integrated and detailed scheduling of production and delivery operations in no-wait flow shop systems. Computers & Industrial Engineering,170. Villarinho, P. A., Panadero, J., Pessoa, L. S., Juan, A. A., & Oliveira, F. L. C. (2021). A simheuristic algorithm for the stochastic permutation flow-shop problem with delivery dates and cumulative payoffs. International Transactions in Operational Research,28(2), 716–737. Wang, Y., Han, Y., Wang, Y., Tasgetiren, M. F., Li, J., & Gao, K. (2023). Intelligent optimization under the makespan constraint: Rapid evaluation mechanisms based on the critical machine for the distributed flowshop group scheduling problem. European Journal of Operational Research,311(3), 816–832. Wang, B., Huang, K., & Li, T. (2018). Permutation flowshop scheduling with time lag constraints and makespan criterion. Computers & Industrial Engineering,120, 1–14. Wang, K., Luo, H., Liu, F., & Yue, X. (2018). Permutation flow shop scheduling with batch delivery to multiple customers in supply chains. IEEE Transactions on Systems, Man, and Cybernetics: Systems,48(10), 1826–1837. Wang, C.-N., Porter, G., Huang, C.-C., Nguyen, V., & Husain, S. (2022). Flowshop scheduling with transportation capacity and time consideration. Computers, Materials and Continua,70(2), 3031–3048. Wang, L., Wu, H., Tang, F., & Zheng, D.-Z. (2005). A hybrid quantum-inspired genetic algorithm for flow shop scheduling. 3645, (PART II), (pp. 636–644). Waschneck, B., Altenmüller, T., Bauernhansl, T., & Kyek, A. (2017). Production scheduling in complex job shops from an industrie 4.0 perspective: A review and challenges in the semiconductor industry. In CEUR workshop proceedings. Xin, X., Jiang, Q., Li, S., Gong, S., & Chen, K. (2021). Energy-efficient scheduling for a permutation flow shop with variable transportation time using an improved discrete whale swarm optimization. Journal of Cleaner Production,293. Xin, X., Jiang, Q., Li, C., Li, S., & Chen, K. (2023). Permutation flow shop energyefficient scheduling with a position-based learning effect. International Journal of Production Research,61(2), 382–409. Yagmur, E., & Kesen, S. E. (2020). A memetic algorithm for joint production and distribution scheduling with due dates. Computers & Industrial Engineering,142, Article 106342. Yagmur, E., & Kesen, S. E. (2021). Multi-trip heterogeneous vehicle routing problem coordinated with production scheduling: Memetic algorithm and simulated annealing approaches. Computers & Industrial Engineering,161. Yang, D.-L., & Chern, M.-S. (2000). Two-machine flowshop group scheduling problem. Computers & Operations Research,27(10), 975–985. Ye, S., Zhao, N., Li, K., & Lei, C. (2017). Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags. Computers & Industrial Engineering,113, 160–184. Yih, Y. (1994). An algorithm for hoist scheduling problems. International Journal of Production Research,32(3), 501–516. Yu, W. (1996). The two-machine flow shop problem with delays and the one-machine total tardiness problem (Ph.D. thesis), Technische Universiteit Eindhoven, Mathematics and Computer Science. Yu, W., Hoogeveen, H., & Lenstra, J. K. (2004). Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. Journal of Scheduling, 7(5), 333–348. Yu, W., Liu, Z., Wang, L., & Fan, T. (2011). Routing open shop and flow shop scheduling problems. European Journal of Operational Research,213(1), 24–36. Yuan, S., Li, T., & Wang, B. (2020). A co-evolutionary genetic algorithm for the two-machine flow shop group scheduling problem with job-related blocking and transportation times. Expert Systems with Applications,152. Yuan, S., Li, T., & Wang, B. (2021). A discrete differential evolution algorithm for flow shop group scheduling problem with sequence-dependent setup and transportation times. Journal of Intelligent Manufacturing,32(2), 427–439. Yuan, J., Soukhal, A., Chen, Y., & Lu, L. (2007). A note on the complexity of flow shop scheduling with transportation constraints. European Journal of Operational Research,178(3), 918–925. Zeballos, L. J., Castro, P. M., & Mèndez, C. A. (2011). Integrated constraint programming scheduling approach for automated wet-etch stations in semiconductor manufacturing. Industrial & Engineering Chemistry Research,50(3), 1705–1715. Zhang, X., & van de Velde, S. (2015). Two-machine interval shop scheduling with time lags. Journal of Scheduling,18(4), 359–368. Zhang, X., & Van De Velde, S. (2010). Polynomial-time approximation schemes for scheduling problems with time lags. Journal of Scheduling,13(5), 553–559. Zhao, Y., Deng, Q., Zhang, L., Han, W., & Li, F. (2023). Optimal spare parts productiondistribution scheduling considering operational utility on customer equipment. Expert Systems with Applications,214. Zhao, N., Ye, S., Li, K., & Chen, S. (2017). Effective iterated greedy algorithm for flowshop scheduling problems with time lags. Chinese Journal of Mechanical Engineering (English Edition),30(3), 652–662. Zhong, W., & Chen, Z.-L. (2015). Flowshop scheduling with interstage job transportation. Journal of Scheduling,18(4), 411–422. European Journal of Operational Research 325 (2025) 1–19 19