Hybrid Stage Shop Scheduling Accepted Manuscript Hybrid Stage Shop Scheduling Andrea Rossi, Sauro Soldani, Michele Lanzetta PII: S0957-4174(14)00829-X DOI: http://dx.doi.org/10.1016/j.eswa.2014.12.050 Reference: ESWA 9775 To appear in: Expert Systems with Applications Please cite this article as: Rossi, A., Soldani, S., Lanzetta, M., Hybrid Stage Shop Scheduling, Expert Systems with Applications (2015), doi: http://dx.doi.org/10.1016/j.eswa.2014.12.050 This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain. http://dx.doi.org/10.1016/j.eswa.2014.12.050 http://dx.doi.org/http://dx.doi.org/10.1016/j.eswa.2014.12.050 Revised manuscript 1 Hybrid Stage Shop Scheduling Andrea Rossi(1), Sauro Soldani(2), Michele Lanzetta(3) Department of Civil and Industrial Engineering, University of Pisa, Italy (1) arossi@ing.unipi.it (2) sauroviola@gmail.com (3) lanzetta@unipi.it Corresponding author Department of Civil and Industrial Engineering Largo Lazzarino 56122 Pisa, Italy Tel. +39-050-2218122 Cel. +39-320-4212172 Abstract The proposed Hybrid Stage Shop Scheduling (HSSS) model, inspired from a real case in the high- fashion industry, aims to fully exploit the potential of parallel resources, splitting and overlapping concurrent operations among teams of multifunctional machines and operators on the same job. The HSSS formally extends mixed shop scheduling (a combination of flowshop and open shop), which is able to model routing flexibility, and hybrid shop scheduling, which provides resource flexibility. To also include operational flexibility through alternative plans obtained by reordering operations linked by undefined or arbitrary (immaterial) precedence constraints, the proposed model integrates process planning and group shop scheduling. A mixed integer linear programming model and a theory based on disjunctive graphs have been proposed to explore the composite relations between nodes involving immaterial relations and deploying their routing rules. A constructive O(resources×jobs2) algorithm to generate a feasible plan/schedule in the most general case has been developed and applied to a case study. Keywords: manufacturing systems, planning/scheduling integration, mixed shop scheduling, nonlinear routing, resource flexibility Revised manuscript 2 1 Introduction We consider a rather general model of mixed shop in which a set of operations for a given set of jobs has to be scheduled on a set of machines, which includes two extensions to the standard scheduling problem as defined by Dauzère-Pérès, Roux, and Lasserre (1998): 1. an operation can be processed by one resource chosen in a given set (resource flexibility); for the sake of generality, we use the standard term resource from the scheduling theory instead of machine; 2. the routing of products in the shop floor is not necessarily linear, i.e. an operation can have more than one predecessor and more than one successor on the routing (nonlinear routing). The mixed shop type considered here is a hybrid (or flexible) shop type combination of flowshop and open shop. A hybrid flowshop is a flowline with parallel resources. In a flowshop, the sequence of operations of each job (routing) is linear and predefined; in an open shop the sequence of operations is immaterial (or undefined). In a mixed shop, the set of constraints between operations is partitioned into two sets: flowshop type set and open shop type set (Masuda, Ishii, & Nishida, 1985). 1.1. Integration of process planning and shop scheduling Mixed shop is the paradigm for the integration of process planning and shop scheduling (Tan & Khoshnevis, 2000). Process planning has been defined by the Society of Manufacturing Engineers as the systematic determination of the methods by which a product is to be manufactured economically and competitively. Traditionally, process planning and shop scheduling are applied separately and sequentially. If a single output of process planning (the plan) is considered as the input to flowshop scheduling, routing constraints from planning may create bottleneck situations on some resources while other can be starving. Also the line balancing may be affected. Consequently, the global system performance can be improved by integrating planning and scheduling. However, the integration of process planning and shop scheduling does not consider operations belonging to the set of open shop type but rather the assignment of optimal process plans among a number of (predefined) alternatives. Stecke and Raman (1995) described a scheme for classifying different types of flexibility conventionally associated with the ability to manufacture a variety of part types by flexible manufacturing systems. In this classification operation flexibility assumes that more alternative plans can be generated by the process planner for a given job. Kis (2003) and Leung (2010) modeled an integrated process planning and shop scheduling system by disjunctive AND/OR graphs. The branches of an OR-subgraph constitute a set of alternative subroutes: exactly one of them must be chosen during scheduling. AND/OR graphs are a generalization of the resource Revised manuscript 3 alternatives of individual operations; however, immaterial constraints among operations cannot be considered effectively. Go, Wahab, Rahman, Ramli, and Hussain (2012) and Bentaha, Battaïa, and Dolgui (2014) approached the design of disassembly lines for end-of-life products with the objective to maximize the line profit. An AND/OR graph was used to model the precedence relationships among tasks and subassemblies and the disassembly alternatives. Doh, Yu, Kim, Lee, and Nam (2013) considered alternative machines for each operation (resource flexibility), in addition to specifying multiple process plans alternative operations and their sequence by a network model with AND/OR nodes. Otto and Otto (2014) described a precedence graph approach that is based on learning from past feasible production sequences and forms a sufficient precedence graph that guarantees feasible assembly line balancing in the automotive industry. The assignment of tasks to stations is due to restrictions, which can be expressed in a precedence graph that includes direct and indirect conjunctive precedence relations. Phanden, Jain, and Verma (2013) developed a simulation-based genetic algorithm (GA) to integrate the process planning and scheduling function that can be quickly implemented in a company with existing process planning and scheduling departments. Bensmaine, Dahane, and Benyoucef (2013) proposed a new heuristics to integrate the process planning and scheduling problem for reconfigurable machine tools, each with multiple configurations, and can perform different operations with different capacities. They considered only direct precedence graph relations. 1.2. Mixed and group shop scheduling In order to reduce the gap with real manufacturing systems, the mixed shop scheduling problem has been regarded as a mixture of flow (or job) and open shop scheduling problems, where operations with immaterial precedence constraints are grouped in the route of the related job. In 1997, the group shop scheduling problem was first introduced in the context of a mathematical competition (Whizzkids, 1997). Regarding the group shop scheduling problem, Blum and Sampels (2004) used a disjunctive graph representation for group shop scheduling and applied an ant colony algorithm to tackle the problem complexity. Liu, Ong, and Ng (2005) proposed a tabu search for group shop scheduling and evaluated the algorithm performance on a set of benchmark problems. Ahmadizar and Shahmaleki (2014) considered the stochastic group shop scheduling problem where both release dates and processing times are random variables, normally, exponentially or uniformly distributed. From the literature above, it can be observed that the mixed shop model includes the models on integration of process planning and scheduling and those on group shop scheduling, by allowing alternative plans produced simply reordering operations connected by immaterial constraints (Figure 1). Revised manuscript 4 According to Stecke and Raman (1995), in addition to operation flexibility, routing flexibility is another aspect of the scheduling flexibility related to the ability of generating alternative paths, which can be followed through the system for a given process plan. As discussed by Rossi and Lanzetta (2013), shared buffers between stages allow routing flexibility, by the permutation of job sequences on resources. Figure 2 shows as an (exclusive) OR node (node 0 towards O31 and O32) that can be reworded as a no-exclusive OR by an immaterial relation, which allows more alternative routings for the scheduler module. Revised manuscript 5 FLEXIBILITY PRECEDENCE GRAPH ALTERNATIVE ROUTINGS conjunctive relations deployment O pe ra ti on f le xi bi li ty (a lt er na ti ve p ro ce ss pl an s) R ou ti ng f le xi bi li ty M ix ed s ho p 1 2 4 5 * 3 1 2 4 5 * 3 2 4 5 3 1 1 1 2 4 5 * 3 1 2 * 3 3 2 4 5 2 3 3 2 4 5 1 1 1 1 2 4 3 5 * 1 2 * 3 3 2 4 5 1 2 3 0 2 3 3 2 4 5 1 1 1 1 2 3 Revised manuscript 6 Figure 1. Example of mixed shop precedence graphs achieved by operation and routing flexibility (according to Stecke & Raman, 1995). No-exclusive OR nodes described by immaterial relations give alternative routing for the scheduler module in order to minimize the completion time. Figure 1 about here Revised manuscript 7 As shown by Masuda, Ishii, and Nishida (1985), the mixed shop problem is NP-hard. Relatively few papers were proposed on the subject. Shakhlevich et al. (2000) discussed the complexity of mixed shop problems under various criteria and clarified the boundary between polynomially solvable and NP-hard problems. Blazewicz and Kobler (2002) reviewed the properties of simple precedence graphs for scheduling problems and exhibited several new polynomial cases for various problems on unrelated parallel machines under arbitrary resource constraints. Ferrell, Sale, Sams, and Yellamarju (2000) approached the problem by heuristics and evaluated the performance in a promising set of dispatching rules. Nasiri and Kianfar (2011) proposed a stage shop scheduling, an open job shop scheduling problem where all the operations of the same job with immaterial precedence constraints are grouped in a stage of the job shop-type. Aloulou and Artigues (2010) and Amin-Naseri and Ashfadi (2012) modeled simple or primitive non-linear precedence constraints, in order to split macro operations into micro operations at stage level. Revised manuscript 8 Table 1. Main contributions from the literature to the mixed shop scheduling problem as an integration of alternative nonlinear routing approaches (group shop, AND/OR) Authors Graph type MILP Theory Disjunctive arc Node Flexible or hybrid Nonlinear routing Group shop Mixed shop AND/OR Masuda, Ishii, and Nishida (1985) • • Dauzère-Pérès, Roux, and Lasserre (1998) • • • Kis (2003 ) • Blum and Sampels (2004) • • Liu, Ong, and Ng (2005) • Leung (2010) • Aloulou and Artigues (2010) • • Nasiri and Kianfar (2011) • • Amin-Naseri and Ashfadi (2012) • • • Doh, Yu, Kim, Lee, and Nam (2013) • • • Bensmaine, Dahane, and Benyoucef (2013) • • Ahmadizar and Shahmaleki (2014) • • Otto and Otto (2014) • • Current work • • • • From this literature analysis chronologically synthesized in Table 1, it can be observed that the most recent works (towards the bottom) converge to the generalization of integrated process planning and group shop scheduling. For this purpose, further research for the definition and use of new precedence relations is required. Revised manuscript 9 1.3. From mixed to hybrid shop scheduling Resource flexibility and nonlinear routing allow a higher level of manufacturing flexibility within each stage of the flowshop: multiple resources can process in parallel subparts of the same product (multi-resource systems). Resource flexibility in the standard flowshop model was reviewed by Ribas, Leisten, and Framinan (2010) and Ruiz and Maroto (2005). In recent years, approaches to hybrid flowshops were proposed by Behnamian and Zandieh (2011), considering the minimization of earliness and quadratic tardiness penalties by a discrete colonial competitive algorithm. Rossi, Pandolfi, and Lanzetta (2013) considered a non-permutation hybrid flow shop scheduling problem, with parallel batching machines, parallel batch families and a machine loading system modeled as sequence-independent uniform set-up times, with the purpose of reducing the number of tardy jobs and the makespan. They proposed two dynamic heuristics based on the critical ratio of allowance set-up and processing time in the scheduling horizon. Li, Meng, Liang, and Zhao (2014) proposed a heuristic-search genetic algorithm, which results in lower complexity and higher efficiency for multi-stage hybrid flow shop scheduling with batch processing machines. Amin-Naseri and Ashfadi (2012) considered some primitive non-linear precedence relations in a flexible job shop environment and proposed a local search problem-specific to speed up e genetic algorithm. Rossi (2014) proposed an ant colony optimization approach based on a disjunctive graph model in order to schedule a manufacturing system with resource flexibility, separable sequence dependent/independent setup and transportation times. Benavides, Ritt, and Miralles (2014) proposed an extension to flowshop with heterogeneous resources among stages, to optimize worker assignment to workstations of health care departments, with the objective of minimizing the makespan, while respecting the diverse capabilities and paces of heterogeneous workers. To our knowledge, only Amin-Naseri and Ashfadi (2012) considered some aspects of nonlinear routing with resource flexibility using a genetic algorithm, without exploring the theoretical implications. 1.4. Problem motivation and approach The research was motivated by a real manufacturing case, a high-fashion company based in Florence, Italy, for the production of high-fashion goods by skilled artisans. An operation (e.g. the manual assembly of a woman bag) can be split in a number of micro- operations (e.g. stitching a handle and sewing a slide fastener), which can be performed on the same job in a fixed or arbitrary routing by different resources of the belonging flowshop stage (e.g. by two operators of the assembly shop). Splitting operations of multi-resource systems affects process planning providing further flexibility and increases the number of scheduling alternatives for the Revised manuscript 10 shop system and, potentially, shorter schedules can be obtained. Alternative plans produced simply reordering operations reduce the process planner workload. Generating alternative plans improves machine utilization and line balancing. Figure 2 shows an example problem derived from the examined case represented as a disjunctive graph. The three shaded areas are examples of macro operations that have been split by detailing the sub operations and resources in order to process them in parallel (overlapping) to reduce the makespan. Precedence graphs allow different routings (sequence permutations) by the inclusion of the immaterial precedence arcs in addition to directed (or conjunctive) arcs. As shown in the example, mixed routing can also span across consecutive stages. The most general case, which represents the focus of current paper, is the shaded graph relation O122-O133-O252 in the example. The cited operations represent respectively: gluing the two halves of the bag, stitching a pocket on just one of the two sides, stitching a buckle to both halves, with realistic times indicated. Gluing is on the previous stage because of a precedence constraint. Sequence O122-O133-O252 is potentially shorter versus sequence O122-O252-O133 for the possible parallelization of O122 and O252. Revised manuscript 11 Figure 2. A disjunctive graph modeling a mixed shop for hybrid flowshop scheduling, with processing times t i j k at nodes O i j k for N (=3) jobs on S (=3) stages, with respectively Q1=2 (hybrid), Q2=1, Q3=1 resources. Colored disjunctive arcs represent the candidate resource for the connected nodes (operations). Bottom: the top digraph partially transformed in acyclic digraph by directing disjunctive arcs on two paths starting from node 0 and ending at node * (green and brown) and one ending in O222 (yellow). Figure 2 about here Stage 2 Stage 3 t253 0 O111 O122 resource assignment: resource 1, stage 1 job routing O222 O211 t111 t122 t211 t222 * O34 O143 O252 t321 t332 t343 t143 O133 t133 O242 t242 O232 t232 t311 immaterial routing resource assignment: resource 2, stage 1 resource assignment: resource 1, stage 2 resource assignment: resource 1, stage 3mixed routing O32 O33 O31 24 Stage 2 Stage 3Stage 1 0 O111 O222 O211 19 * O33 O143 O252 O32 O33 O133 O242 O232 O31 20 11 12 3 7 4 26 41 28 37 O122 36 Stage 1 Revised manuscript 12 We propose the hybrid stage shop scheduling (HSSS), a mixed shop model for hybrid flowshop scheduling with unrelated parallel resources per stage. The proposed underlying mixed model, in addition to routing flexibility that emerges with permutations of the operations linked by immaterial relations, allows: (i) splitting operations of the flowshop type set on the same job and assigning them to alternative resources; (ii) overlapping the operations of consecutive stages linked by immaterial routing, yielding shorter schedules. The proposed hybrid stage shop scheduling model completes the mixed stage shop model by Nasiri and Kianfar (2011) and the hybrid stage shop scheduling model by Amin-Naseri and Ashfadi (2012). Extensions include the addition of operation overlapping and splitting within stages and across consecutive stages with the composition of mixed relations, which will be discussed throughout the paper. The proposed model can be applied to Computer Aided Design (CAD), where designers share the same digital model of the product under development (Leu et al., 2013) , in robotic assembly and in disassembly of end of life goods, where operations on subparts can be carried out concurrently, and in train traffic management by railway line branching (Kozan & Liu, 2012). In section 2 we define the hybrid stage shop scheduling problem and its MILP (section 3). In section 4 we describe the model based on digraphs and in section 5 we propose a set of primitive and mixed rules and their combinations, derived from the precedence graph, in order to deploy and explore various alternative routings. The hybrid stage shop scheduling model is based on a digraph, which is a powerful tool to design scheduling optimization (metaheuristics) algorithms. In section 6 a heuristics is presented to obtain a conjunctive graph, which represents a feasible solution of the hybrid stage shop scheduling problem. Also, the computational complexity is evaluated. Application to a case study is discussed in section 7. 2 Hybrid Stage Shop Scheduling (HSSS) In hybrid stage shop scheduling, N jobs have to be scheduled on S stages with R resources in all, in accordance with its nonlinear routing, represented by a precedence graph, which includes conjunctive (directed) and disjunctive precedence constraints (described below) among operations belonging to a set of il operations Oi j k with i=1,..,N, j=1,.., il , k=1,..,S. Each operation Oi j k has to be processed according to its precedence constraint, denoted by a level Li j, for time ti j k with resource flexibility represented by the assignment to a single resource h among a set of alternative identical resources {Qk-1+1,.., Qk} of the stage k (k=1,..,S). Each job i is subject to a release date, ri, an Revised manuscript 13 initial level ijlj Li,..,1min = =Li 1=1. st(Oi j k) and ct(Oi j k) denote respectively the starting and the completion time of an operation, with iCt being the total completion time for each job. No resource can process more than one operation at a time and an operation must be processed by one, and only one, resource; no precedence constraints between operations of different jobs is allowed. All resources are available since the initial time and resource breakdown is not considered. Setup is negligible or is included in the processing time. The handling system offers the flexibility to move a part with negligible transportation time and includes a buffer for each stage. The buffer size of stages k=1 and k=S+1 is N (i.e. the input and output buffers contain up to N jobs). The number of slots of the buffer at stage k, k=2,…,S, each containing a single job, is defined by the following Lemma 1. Lemma 1. The hybrid flowshop scheduling with N jobs and R resources is Bi=+∝ if and only if the shared buffer size for stage k , k=2,…,S is at least: )( 2−−− kk QQN (1) This proof extends the result achieved by Rossi and Lanzetta (2013). In the worst case, the system becomes congested in a single stage. Let k be this stage, with )( 1−− kk QQ the number of its resources. Hence, the number of jobs waiting in the buffer of stage k or in the previous stages is )( 1−−− kk QQN . Similarly, in the previous stage there are )( 21 −− − kk QQ resources. The jobs can wait after processing in the previous stage k-1 before a resource of the stage k will be free. The minimum buffer size for each of the intermediate stages is given by: )()()( 2211 −−−− −−=−−−− kkkkkk QQNQQQQN (2) � Operations of job i are partitioned in k subsets Gi k to be performed by resources of stage k according to the following equations: NilG i S k ki ,..,1 1 ==∑ = (3) zwSzwGG ziwi ≠=∅= ,,..,1,,∩ (4) Revised manuscript 14 The quantity P = mink=1,..,S )( 1−− kk QQ represents the degree of resource flexibility, i.e. the parallelization capability of the system. We define a hybrid stage shop scheduling model with degree of resource flexibility P as P-HSSS model. The assignment of operations to a given resource of current stage is a source of flexibility, in addition to the flexibility represented by sequencing operations on resources. This double source of flexibility increases the problem complexity along with the performance increase. 3 Hybrid stage shop scheduling mixed integer model A mixed integer linear programming (MILP) model for the hybrid stage shop scheduling is described. Decision variable ijkhx 1, if operation j of job i is assigned to resource h in stage k 0, otherwise The objective function selected is the total completion time (makespan) minimization and can be formulated as: maxCMin (5) subject to constraints I.1 to I.15. ∑ ∑ ∑ = += =− ≥ S k Q Qh l j ijhkijki k k i xtCt 1 1 11 Ni ,...,1=∀ (I.1) ∑ += − = k k Q Qh ijhkx 11 1 Ni ,...,1=∀ , ilj ,...,1=∀ , Sk ,...,1=∀ (I.2) ∑ = = S k ijhkx 1 1 , , kk QQh ,...,11 +=∀ − (I.3) ∑ = ≤ il j ijhkx 1 1 , , (I.4) Ni ,...,1=∀ ilj ,...,1=∀ Ni ,...,1=∀ kk QQh ,...,11 +=∀ − Sk ,...,1=∀ Revised manuscript 15 ∑ = ≤ N i ijhkx 1 1 , , (I.5) ⎪⎩ ⎪ ⎨ ⎧ = =ℜ∈ = + 0 1 0 ijhk ijhk ijk x x if if t , , , (I.6) ijhkijkijkijk xtstct =− , , , (I.7) ⎪⎩ ⎪ ⎨ ⎧ =⇒=ℜ∈ ⇒<>− ' '0 ' '' jjLLse jjLLsectst ijij ijijijkkij ≺ ≺ , , (I.8) 0≥ir Ni ∈∀ (I.9) 0≥ijkst , , (I.10) 0≥ijkt , , (I.11) 0≥ijkct , , (I.12) 0≥iCt (I.13) ℵ∈ijL , (I.14) }{ 1,0∈ijhkx , , , (I.15) The constraint equation (I.1) forces the total completion time of job i, to be less or equal to the sum of all processing times affecting job i, indexed by operations and stages. The constraint equation (I.2) ensures that each operation is assigned to exactly one resource. The constraint equation (I.3) ensures that each operation is specific to exactly one stage. The constraint equation (I.4) shows that any operation can (sum equal to 1) or cannot (sum equal to 0) be assigned to a particular pair of job and resource. ilj ,...,1=∀ kk QQh ,...,11 +=∀ − Sk ,...,1=∀ Ni ,...,1=∀ ilj ,...,1=∀ kk QQh ,...,11 +=∀ − Sk ,...,1=∀ Ni ,...,1=∀ ilj ,...,1=∀ kk QQh ,...,11 +=∀ − Sk ,...,1=∀ Ni ,...,1=∀ ilj ,...,1=∀ Sk ,...,1=∀ Ni ,...,1=∀ ilj ,...,1=∀ Sk ,...,1=∀ Ni ,...,1=∀ ilj ,...,1=∀ Sk ,...,1=∀ Ni ,...,1=∀ ilj ,...,1=∀ Sk ,...,1=∀ Ni ,...,1=∀ Ni ,...,1=∀ ilj ,...,1=∀ Ni ,...,1=∀ ilj ,...,1=∀ kk QQh ,...,11 +=∀ − Sk ,...,1=∀ Revised manuscript 16 The constraint equation (I.5) represents the possibility (sum equal to 1) or not (sum equal to 0) that a job involves the use of a resource for a specific operation. The constraint equation (I.6) requires that the processing time of resource h of stage k performing operation j of job i is equal to 0 if the transaction is not assigned to any resource. The constraint equation (I.7) requires that the difference between the completion time and the starting time of a resource busy for an operation of a job be equal to its processing time. The constraint equation (I.8) ensures that the difference between the starting time of a certain operation and the completion time calculated for the immediately preceding operation is greater than 0 if the value of the variable level of the previous operation is smaller compared to the variable level of the following operation. It is worth dwelling on the condition in which it has the same value of the variable level for two successive operations; in this case the order of execution can be chosen arbitrarily: the result can be greater, less or equal to 0. Finally, the constraint equations ranging from (I.9) to (I.15) are simply conditions of existence and non-negativity of the variables used in the model. 4 Hybrid stage shop scheduling disjunctive graph representation The hybrid stage shop scheduling problem can be represented by a weighted disjunctive graph as in Rossi and Lanzetta (2014), applied to the non permutation flowshop scheduling (Figure 2 top): DG = (ℵ, Wℵ, C, D, Eh k) (6) where ℵ is the set of nodes (operations ijkO ) plus the dummy start and finishing nodes 0 and *; WN is the set of weight on nodes, represented by the processing times ijkt ; C is the set of conjunctive (directed) arcs (a,b) between every pair of nodes a and b on a job routing, representing the precedence constraints between the corresponding operations (conjunctive relations, C); it also includes conjunctive arcs between 0 (*) and every first (last) node on a routing; D is the set of disjunctive arcs [a,b] (equal to [b,a]), between every pair of nodes a and b on a job routing with immaterial precedence constraints between the corresponding operations (disjunctive relations, D); Eh k is the h th set (h∈{Qk-1+1,..., Qk}) of disjunctive arcs [u,v] between every pair of nodes u and v belonging to the same stage k; u,v∈Gi k, k=1,..,S; Eh k also includes disjunctive arcs between 0 and u Revised manuscript 17 (v) and between u (v) and * for all u∈Gi k. The sets Eh k are represented by colored disjunctive arcs in Figure 2 top. It can be noticed that the DG includes one kind of conjunctive arc (arrows in the digraph of Figure 2 top) and two kinds of disjunctive arcs: D for nonlinear routing (dashed lines) and Eh k for resource flexibility (colored lines). In general, a P-HSSS problem, i.e. a problem with degree of resource flexibility P, is represented by S stages of P kinds of arcs E*k. The number of disjunctive arcs in the digraph is O(P⋅S⋅N2), because the arcs of E*k connected with at least N nodes are O(N 2) and the total flexibility is obtained by P⋅N2 arcs of E*k (Kacem, Hammadi, & Borne, 2002). Consequently, in the P-HSSS total flexibility is present, but only within each stage. The set D describes nonlinear routing for open and consequently for the mixed shop considered here. D is not required to model linear problems, such as flowshop and hybrid flowshop scheduling. In the next section the interaction between C and D type relations will be discussed. A finite sequence of conjunctive arcs between two nodes is called path. The length of an arc is equal to the processing time of the node at which it ends. The path length is equal to the sum of the lengths of its arcs. A path which starts from 0 and ends at * is the loading sequence on a resource. Figure 2 bottom shows two paths with lengths, respectively, 24+20 (green path) and 19+11 (brown path), which start from 0 and end at *; they are the loading sequences of resources of stage 1. A cycle is a path that starts and ends at the same node. If no cycle is present in a conjunctive graph achieved by directing some disjunctive arcs, the conjunctive graph is acyclic (Figure 2 bottom). In particular, a digraph is an acyclic conjunctive graph. If an acyclic conjunctive graph includes all the nodes, the related loading sequences on the resources are feasible schedules and the makespan is the length of the critical path, i.e. the longest path between the dummy start and finishing nodes. Finally, for each job, the length of the longest path between the dummy start node 0 and a given node is the total completion time ct(Oi j k) of the corresponding operation. 5 Hybrid stage shop scheduling routing rules Hybrid stage shop scheduling is a more general model for mixed shop scheduling and it is more suitable to describe real manufacturing cases, but it requires the definition of new relations among nodes split at the stage level or across consecutive stages. A digraph as defined in (6) includes C and D type primitive relations. By the presence of D type relations, routing is nonlinear. C and D type relations in (6) between nodes involve precedence constraints, which can be described by the Revised manuscript 18 routing rules (feasible sequence of operations for a given job) introduced in this section. The proposed wildcard node mechanism will also be described. The complete set of basic relations includes two primitive C and D type relations defined in (6) listed in Table 2 and five mixed relations introduced in Table 3. The complete set of basic relations between nodes j and j + 1, j=1,…, 1−il , of the same job i and their levels Li j is: (a). Conjunctive relation (C), Li (j+1) = Li j + 1. The routing is linear as in flowshop scheduling (Table 2). (b). Disjunctive relation (D), Li (j+1)=Li j. The routing is immaterial as in open shop scheduling, where a sequence of operations is a job permutation (Table 2). (c). Mixed relation (M). Mixed relations are present, where a disjunctive relation can anticipate, interpose or postpone a direct relation (Table 3). Levels are the mechanism to represent the precedence constraints between operations. Table 2. Primitive relations (2 nodes) and deployment of their routing rules Case Relations Notation Precedence graph Routing deployment #1. Conjunctive (directed) C (1,2) #2. Disjunctive D [1,2] (or [2,1]) Table 2 shows linear and arbitrary relations among operations of the same job and their routing rules. A C relation is a conjunctive arc between a starting and ending node and is represented in round brackets (1,2); the starting node represents the operation processed before in the feasible sequence 1�2, as imposed by the level Li 2 = Li 1+1. A D relation is a disjunctive arc between two nodes; the nodes represent operations processed in an arbitrary order within the feasible sequence; the two feasible sequences are 1�2 and 2�1 associated with a unique level, where Li 2=Li 1. A D relation has no orientation between nodes and is differentiated from a C relation by using square brackets: [1,2] = [2,1]. Both conjunctive and disjunctive (primitive) relations are denoted by { }DC,=Γ . 2 1 Li 1 Li 1+1 1 2 Li 1 Li 1 2 1 1 2 2 1 Revised manuscript 19 Table 3. Mixed relations (3 nodes) and deployment of their routing rules Case Notation Precedence graph Routing deployment #3. M1 #4. M2 #5. M3 #6. M4 Table 3 shows the mixed relations (Mx, x=1,..,4) among nodes. A M relation, yx ∪ , is a union of primitive relations x,y ∈ Γ = {C, D}. M1 and M2 include one disjunctive relation, [2,3], and two conjunctive relations, yielding two feasible routing rules. 1 2 3 Li 1 Li 1+1 Li 1+1 1 2 3 1 3 2 1 2 3 Li 2+1 Li 3=Li 2 Li 2 2 3 1 3 2 1 1 2 3 Li 2 {Li 1,Li 2} Li 1 1 2 3 1 3 2 3 1 2 1 2 3 Li 1 Li 1 Li 1 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Revised manuscript 20 M3 includes two D relations and one C relation, (1,2). The directed arc compels a clockwise path which encompasses a wildcard node. Node 3, belonging to both D relations, [2,3] and [1,3], can be interposed in the sequence compelled by the C relation to obtain feasible routing rules: 1�2�3, 1�3�2 and 3�1�2. M4 includes all three disjunctive arcs (similarly to group shop scheduling); the feasible routing rules are all the six permutations of the three nodes. An instance of the problem can be expressed in compact form by the tuple P-HSSS|ℵα|Cβ|Dχ|Rδ|Nε|Sφ|max Li j γ (7) where quoted symbols α, β, χ, δ, ε, φ and γ are values of the respective parameter (base). An example is the triangular inset of Figure 3 derived from the 2-HSSS|ℵα|C17|D5|R4|N1|S3|max Li j8 case in Figure 2. Figure 3. Examples of precedence relations on 2-HSSS|ℵα|C17|D5|R4|N1|S3|max Li j8: conjunctive relations C ((O111, O122), (O122, O133), etc.) and disjunctive relations D ([O222, O232], [O222, O242], Stage 2 Stage 3 t253 Stage 1 0 O111 O122 resource assignment: resource 1, stage 1job routing: conjunctive relation C O211 t111 t122 t211 t222 * O34 O143 O252 t321 t332 t343 t143 O133 t133 O242 t242 O232 t232 t311 job routing: disjunctive relation D resource assignment: resource 2, stage 1 resource assignment: resource 1, stage 2 resource assignment: resource 1, stage 3 job routing: constrained-disjunctive relation M2 (Nasiri & Kianfar, 2011) O32 O33 O31 job routing: mixed relation M3 within stage 2 (Amin-Naseri & Ashfadi, 2012) job routing: mixed relation M3 across stages 2-3 (proposed) O222 Revised manuscript 21 [O311, O321]) from Table 2; constrained-disjunctive relations M2 and M3 from Table 3 (respectively cases #4. and #5.) in triangular insets. Figure 3 about here 5.1. Properties of basic relations The combination of primitive relations has been shown to yield the mixed relations M1 to M4. Their precedence graph encompasses nonlinear routing; consequently, a digraph (6) can be formed by mixed relations. In this subsection, some properties of primitive and mixed relations are introduced to allow more complex composition and decomposition rules of digraphs (6). Proposition 1. All the introduced relations can be represented by a digraph (6) with maximum level equal to 2. As an example, we consider M3. Its digraph is: DG(M3) = (ℵ, Wℵ, C, D, Eh k) = { } { } { } { } { }( ),]3,2[],3,1[,)2,1(,,,,3,2,1 321 iii ttt where, without loss in generality, the set of the disjunctive arcs of each resource Eh k is not considered. Lemma 2. The union operator ∪ is closed to the set of the primitive relations Γ . For Proposition 1, if Γ∈yx, include an acyclic graph, also yx ∪ includes no cycle on its graph. A cycle breaks the level of the node, which closes the path on itself. Obviously, only a C relation can close a cycle. If x = (a,b) ∈ C and y ∈ Γ, then yx ∪ becomes the mixed relation denoted by, respectively, M1 (if y = (a,c) ∈ C) and M2 or M3 (if y ∈ D) relations. In fact, the level of nodes b and c forces either a disjunctive relation (obtaining the mixed relations M1 and M3) or a conjunctive relation (obtaining the mixed relation M2). Vice versa, if x = (b,a) ∈ C and y ∈ Γ, then becomes, similarly to the previous case, the mixed relation denoted by, respectively, M2 (if y = (a,c) ∈ C) and M1 or M3 (if y ∈ D) relations. yx ∪ Revised manuscript 22 In any case, M1 to M3 relations are disjunctive graphs. Hence, considering the former primitive, i.e. the C relation, the thesis is accomplished. Analogously, if x = [a,b] ∈ C and y ∈ Γ, then becomes the mixed relation denoted by, respectively, M1 (if y = (c,a) ∈ C, M2 (if y = (a,c) ∈ C) and M4 (if y ∈ D). Hence, the thesis is accomplished because M1 and M2 relations are digraphs. � Corollary 1. The level of the wildcard node inherits the levels of the nodes to which it is linked to (through D relations). Corollary 2. The level of all the nodes connected only by D relations is unchanged (i.e. M4). 5.2. Composition and decomposition of basic relations In this subsection, it will be shown how to assemble mixed routing rules to form a nonlinear precedence graph and achieve more complex rules. A list of compositions of mixed relations is shown in Table 4. All possible outcomes of compositions are listed. The same outcome can be obtained by different compositions (not shown). Compositions may involve nodes belonging to the same stage or to two consecutive stages; however, two consecutive stages can be linked by conjunctive arcs only. Decomposition rules can be inferred by following the opposite path. To explain the composition of mixed relations shown in Table 4, case #12. is considered: 33 MM ∪ . Both mixed relations have the same wildcard node 3. From Proposition 1, the two relations can be represented by the digraphs: DG1(M3)= (8) DG2(M3)= { } { } { } { } { }( ),]4,3[],3,2[,)4,2(,,,,4,3,2 432 iii ttt (9) The composite relation is: )3()3( 21 MDGMDG ∪ = { } { } { } { } { }( ),]4,3[],3,2[],3,1[,)4,2(),2,1(,,,,,4,3,2,1 4321 iiii tttt (10) yx ∪ { } { } { } { } { }( ),]3,2[],3,1[,)2,1(,,,,3,2,1 321 iii ttt Revised manuscript 23 which has a node (node 2) with one starting and one ending conjunctive arc. The nodes opposite to node 2 in these two conjunctive arcs have a level reduced by one or increased by one, respectively, if the node is on the conjunctive arc that ends to 2 and if the node is on the conjunctive arc that starts from 2. For Corollary 1 the level of the wildcard node inherits the levels of the nodes to which it is linked to (through D relations): Li 3={Li 1, Li 2= Li 1+1, Li 4= Li 1+2}. As a consequence, the routing rules are obtained by interposing 3 in the sequence compelled by the 2 conjunctive arcs, (1,2) and (2,4): 3�1�2�4, 1�3�2�4, 1�2�3�4, 1�2�4�3. Revised manuscript 24 Table 4. Composition of mixed relations (4 nodes) and deployment of their routing rules Case # Relation Combination of mixed relations Precedence graph Routing deployment #7. 21 MM ∪ 1 2 3 1 3 2 4 4 M1 M2 1 2 3 Li 1 Li 1+1 Li 1+1 4 2 3 L i 2 +1 Li 3=Li 2 Li 2 1 2 3 Li 1 Li 1+2 Li 1+1 4 Li 1+1 1 2 3 Li 1 Li 1+1 4 Li 1 1 3 2 4 1 3 4 2 Revised manuscript 25 #8. 31 MM ∪ M1 M3 1 2 3 1 3 2 4 4 1 2 4 3 #9. 41 MM ∪ 1 1 1 1 1 1 1 M4M1 2 3 4 2 4 3 3 2 4 3 4 2 4 2 3 4 2 1 2 3 Li 1 Li 1+1 Li 1+1 4 2 3 Li 2 {Li 1,Li 2} L i 1 1 2 3 Li 1 Li 1+2 Li 1+1 4 {Li 1+1, Li 1+2} 1 2 3 Li 1 Li 1+1 Li 1+1 4 2 3 L i 1 Li 1 Li 1 1 2 3 Li 1 Li 1+1 Li 1+1 4 Li 1+1 Revised manuscript 26 #10. 12 MM ∪ #11. 23 MM ∪ 1 2 3 1 3 2 4 4 3 1 2 4 M3 M2 4 2 3 L i 2 +1 Li 3=Li 2 Li 2 1 2 3 Li 1 Li 1+1 Li 1+1 1 2 3 Li 1 Li 1+1 4 Li 1 Li 1+1 1 3 2 4 1 3 4 2 4 2 3 Li 2 +1 Li 3=Li 2 Li 2 1 2 3 Li 2 {Li 1,Li 2} Li 1 1 2 3 Li 1 Li 1+2 Li 1+1 4 {Li 1, Li 1+1} Revised manuscript 27 #12. 33 MM ∪ 1 2 3 Li 2 {Li 1,Li 2} Li 1 1 2 3 Li 1 Li 1+1 4 {Li 1, Li 1+1, Li 1+2} Li 1+2 1 2 4 1 2 3 3 4 1 3 2 4 3 1 2 4 1 2 3 Li 1 Li 1+1 4 {Li 1, Li 1+1} { Li 1+1, Li 1+2} 1 2 3 1 3 2 4 4 3 1 2 4 1 3 4 2 Revised manuscript 28 #13. 43 MM ∪ 1 2 3 Li 2 {Li 1,Li 2} Li 1 3 2 Li 2 Li 2 4 Li 2 1 2 3 Li 1 Li 1+1 4 {Li 1, Li 1+1} {Li 1, Li 1+1} 1 2 3 1 2 4 4 3 1 3 2 4 1 3 4 1 4 2 2 3 1 4 3 2 3 1 2 4 3 1 4 2 3 4 1 2 4 1 2 3 4 1 3 2 4 3 1 2 Revised manuscript 29 Composite relations can be recombined into two mixed relations x and y with conjunctive arcs from x to y, which cross the boundaries of the two relations in the x-y direction (by construction), according to the following two alternatives (Table 5): 1. by a C relation, e.g. (3,2) in the precedence graph of row 1 for case #7. in Table 4; 2. by a D relation, e.g. [2,3] in row 2 for all other cases of Table 4 except case #7. (only case #13. is represented). In the first alternative, the combined mixed rule is modeled by two D relations between nodes with the same level. The routing rule of this recombination is unchanged with respect to the original case #7. in Table 4. In the second alternative, the combined mixed rule is modeled by splitting nodes with the same level and by connecting the split nodes by disjunctive arcs. Two mixed relations Mx are created. Each node of the D relation is split into two nodes, the original node and the dummy node, which are connected by a D relation. For example, node 2 is placed facing dummy node 2’ and they are connected by arc [2,2’]. The routing rule of the recombination imposes that only one node, between the original and the dummy node, will be included into the loading sequence of the selected resource. The not selected node will have no connection to the rest of the digraph and will not be considered by the routing rule. In both alternatives, in the combined mixed rule the red arrows cross the boundaries of the two relations from left to right and no arrow is present in the opposite direction in order to process more complex relations which satisfy the properties introduced above. Revised manuscript 30 Table 5. Decomposition rules for the mixed relations of C type (M1 ∪ M2) and of D type (M3 ∪ M3), yielding respectively a D to D relation and two split M3 relations. Case Precedence graph Combined mixed rule #7. 1 2 3 Li 1 Li 1+1 4 D D #12. 1 2 3 Li 1 Li 1+1 { L i 1, Li 1+1 } 2’ 3’ L i 1+1 4 { L i 1 , L i 1 +1 } { L i 1 +1, L i 1 +2 } Splitting operation 2 Splitting operation 3 M3 M3 6 A scheduling heuristic (H•HSSS) This section describes an example heuristic to show the usability of the proposed HSSS model for scheduling purposes. The developed algorithm is a list scheduler heuristic derived from Giffler and Thompson (1960), which was proven to generate a feasible schedule on the digraph, by visiting every node once and 1 2 3 Li 1 Li 1+1 4 Li 1 Li 1+1 1 2 3 Li 1 Li 1+1 4 {Li 1, Li 1+1} { Li 1+1, L Revised manuscript 31 only once. The list scheduler algorithm was originally proposed for classic job shop scheduling. At every step, a node is connected by means of a feasible move to the partially acyclic conjunctive graph, which represents the partial schedule. A feasible move is a disjunctive arc, which can be directed in the partial conjunctive graph without creating a cycle. The following pseudo code produces an acyclic graph, which includes the critical path. Heuristic for hybrid stage shop scheduling (H•HSSS) Input: a weighted digraph DG = (ℵ, WN, C, D, Ehk) O ← {Oi j k ⏐ i=1,..,N, j=1,..,li, k=1,..,S} i. AL1w←{Oi j k ∈O⏐ Oi j k ∩ O = ∅} ii. AL2w←{Oi j k ∈ AL1w | NiLij ,..,1,min = } iii. cti j k =ri, for each Oi j k ∈ AL2w for each k =1 to S do Initialization of Candidate Nodes: build, in two steps, the allowed list ALw for the current iteration w: i. AL1w←{Oi j k ∈ O⏐ Oi j k-1 ∩ O = ∅} ii. AL2w←{Oi j k ∈ AL1w | } for each w =1 to (Σi=1,..,N li) do 1. Initialization of Feasible Moves: mark as a feasible move each disjunctive arc (Oi’ j’ k, Oi j k) of Eh k where Oi j k ∈AL2w and Oi’ j’ k is the last operation of the loading sequence of resource h of the stage k (it creates the possibility for the candidate operation to become the new last operation of that loading sequence); 2. Move Selection: select a feasible move (Oi’ j’ k, Oi j k) of Ehk by directing the related disjunctive arc (Oi’ j’ k =‘dummy 0’,if k =1); 3. Update Routing: if ,*ijij LL = where Oi j* k is in the path which starts from 0 and ends at Oi j k, direct the last disjunctive arc in the path [Oi j* k, Oi j k]∈ D (after this action (Oi j* k, Oi j k) ∈ C) and update 1* += ijij LL ; finally, update the level on all the disjunctive arcs connected to Oi j k (i.e. 1** += ijij LL , if [Oi j k, Oi j** k] ∈ D); NiLij ,..,1,min = Revised manuscript 32 4. Arcs Removal: remove all the remaining disjunctive arcs connected to Oi’ j’ k (i.e. no other operation can be immediately subsequent to Oi’ j’ k in the loading sequence); remove all the remaining disjunctive arcs of Eh’k connected to Oi j k, i.e. h’≠h (i.e. no other loading sequence can include the operation); finally, remove all the remaining disjunctive arcs of D connected to Oi j* k (i.e. the routing must be linear after updating); 5. Computing Length: the length of the arc (Oi’ j’ k, Oi j k) is evaluated as the processing time of node Oi j k; this length is placed on the arc (Oi’ j’ k, Oi j k) and on the arc of the job routing (Oi j* k, Oi j k) which ends at Oi j k; also, the completion time cti j k = max{cti’j* k, cti j* k}+ti j k is placed as a mark of the node Oi j k, if Li j*