Victor Yaurima3, Félix F. González-Navarro1 and Pedro Flores Perez4

The scheduling problem in manufacturing systems, where the product components are processed by means of lot units (pallets, containers, boxes) of many identical items, has been recently subject of intense research in modern industry. Most of the common examples in production per lots can be found in serial production like digital devices manufacturing, assembly lines, and information service facilities. The lot processing and the use of batch

One of the most popular machine environments in scheduling is Hybrid Flow Shop (namely in the following as HFS), in which *n* jobs must be processed in series of *m* stages optimizing a given objective function, and at least one stage has parallel machines. In a traditional scheduling problem, a job is indivisible, and it cannot be transferred to the next machine before its processing is finished (Marimuthu et al. 2009; Potts & Baker 1989). On the contrary, the division of jobs into sublots in many situations is permissible and desirable in order to accelerate manufacturing or respect just-in-time (JIT) system through parallel processing. It is known that the HFS problem with *m* = 2 (HFS2) is NP-hard even if one of two stages contains a single machine (Gupta & Tunc, 1998). A HFS with lot processing has additional difficulties such as differences in sublot finish times on machine, unknown lot (sublot) sizes, setup times through lot sequencing, uneven lot sizes under customer request that lead to the demand splitting and allocation problem, etc. These kinds of problems possess a high computational complexity; therefore most of published literature is dedicated

Lot processing programming has differences in comparison with traditional job scheduling. On the one hand the job notation depends on the problem assumptions and requires an explicit interpretation; for the other hand one lot as well as one customer's demand can be considered as a job. The theoretical and practical interest on this issue represent models where job splitting is permitted -i.e. one job is allowed to split into sublots to process in parallel on the same or on various machines-. In many models, the sublot size is not clearly

machines for parallel execution are typical for modern manufacturing systems.

to simple flow shop or two-stage HFS machine environment.

**1. Introduction**

Then it is estimated the cost of crashing time for each activity, which is possible (cost slope). By using a linear programming formulation the critical activities are determined. Assigning some budget to activities that can be crashed by time, causes to reduce the completion time of all the project or makespan, this by itself causes better use of the resources specially machinery and manpower, which by itself increase productivity.

In addition to above, the important subject in this research is ability to sensitivity analysis. So that, by assigning different budgets, it can be obtained different completion time. Thereupon we can select the optimum completion time considering to corresponding budget.

For further research it is suggested to apply linear programming technique to determine makespan subject to budget limitation in some other systems like parallel flow shop.

#### **9. Acknowledgement**

The author is very grateful to Dr. Hojjati who reviewed this chapter and gave some helpful comments.

#### **10. References**

## **Lot Processing in Hybrid Flow Shop Scheduling Problem**

Larysa Burtseva1, Rainier Romero2, Salvador Ramirez1, Victor Yaurima3, Félix F. González-Navarro1 and Pedro Flores Perez4 *1Autonomous University of Baja California, Mexicali, 2Polytechnic University of Baja California, Mexicali, 3CESUES Superior Studies Center, San Luis Rio Colorado, Sonora, 4Univesity of Sonora, Hermosillo, Sonora, Mexico*

#### **1. Introduction**

64 Production Scheduling

Then it is estimated the cost of crashing time for each activity, which is possible (cost slope). By using a linear programming formulation the critical activities are determined. Assigning some budget to activities that can be crashed by time, causes to reduce the completion time of all the project or makespan, this by itself causes better use of the resources specially

In addition to above, the important subject in this research is ability to sensitivity analysis. So that, by assigning different budgets, it can be obtained different completion time. Thereupon

For further research it is suggested to apply linear programming technique to determine

The author is very grateful to Dr. Hojjati who reviewed this chapter and gave some helpful

Al-Dulaomi, B. & A.Ali, H. (2008). A Novel Genetic Algorithm Approach for Solving Flow

Brah, S.A. & Hunsucker, J.H. (1991). Branch and Bound Method for the Flow Shop with Multiple Processors. *European Journal of Operational Research*, No.51, pp. 88-91. Campbell, H.G.; Dudeck, R.A. & Smith, M.L. (1970). A Heuristic Algorithm for the n Job, m Machine Sequencing Problem. *Management Science*, No.16, pp. 630-637. French, S. (1982). Sequencing and Scheduling: An Introduction to the Mathematics of the Job

Gowrishankar, K. (2001). Flow Shop Scheduling Algorithms for Minimizing the Completion

Hojjati, S.M.H. & Sahraeyan, A. (2009). Minimizing Makespan Subject to Budget Limitation

Khodadadi, A. (2011). Solving Constrained Flow-Shop Scheduling Problem with Three

Linn, R. & Zhang, W. (1999). Hybrid Flow Shop Scheduling: A Survey. *Proceedings of International Conference on Computer and Industrial Engineering 37*, pp. 57-61. Pan, J.C.H; Chen, J.S. & Chao, C.M. (2002). Minimizing Tardiness in a Two-Machine Flow

Seda, M. (2007). Mathematical Models of Flow Shop and Job Shop Scheduling Problems.

Wang, H.; Chow, F. & Wu, F. (n.d.). A Simulated Annealing for Hybrid Flow Shop

Zijm, W.H.M. & Nelissen, E. (1990). Scheduling a Flexible Machining Centre. *Proceedings of Conference on Engineering Costs and Production Economics 19*, pp. 249-258.

Havill, J. & Mao, W. (2002). On-line Algorithms for hybrid Flow Shop Scheduling.

*Industrial Engineering 39*, Troyes, France, July 6-8, 2009.

Shop. *Computer and Operations Research*, Vol. 29, pp. 869-885.

*Manufacturing Technology*, Vol.53, No. 5, pp.761-776.

*World Academy of Science, Engineering and Technology*, pp. 122-127.

Shop Problem. *International Journal of Computer Science and Network Security*, Vol. 8,

Time Variance and the Sum of Squares of Completion Time Deviation from a Common Due Date. *European Journal of Operational Research*, Vol. 132, pp. 643-665.

in Hybrid Flow Shop. *Proceedings of International Conference on Computer and*

Machines. *International Journal of Academic Research*, Vol. 3, No. 1, January, 2011, pp.

Scheduling with Tasks to Minimize Makespan. *International Journal of Advanced*

we can select the optimum completion time considering to corresponding budget.

makespan subject to budget limitation in some other systems like parallel flow shop.

machinery and manpower, which by itself increase productivity.

**9. Acknowledgement**

No.9, pp. 229-235.

Shop. Harwood, Chi Chester.

comments.

**10. References**

38-40.

The scheduling problem in manufacturing systems, where the product components are processed by means of lot units (pallets, containers, boxes) of many identical items, has been recently subject of intense research in modern industry. Most of the common examples in production per lots can be found in serial production like digital devices manufacturing, assembly lines, and information service facilities. The lot processing and the use of batch machines for parallel execution are typical for modern manufacturing systems.

One of the most popular machine environments in scheduling is Hybrid Flow Shop (namely in the following as HFS), in which *n* jobs must be processed in series of *m* stages optimizing a given objective function, and at least one stage has parallel machines. In a traditional scheduling problem, a job is indivisible, and it cannot be transferred to the next machine before its processing is finished (Marimuthu et al. 2009; Potts & Baker 1989). On the contrary, the division of jobs into sublots in many situations is permissible and desirable in order to accelerate manufacturing or respect just-in-time (JIT) system through parallel processing. It is known that the HFS problem with *m* = 2 (HFS2) is NP-hard even if one of two stages contains a single machine (Gupta & Tunc, 1998). A HFS with lot processing has additional difficulties such as differences in sublot finish times on machine, unknown lot (sublot) sizes, setup times through lot sequencing, uneven lot sizes under customer request that lead to the demand splitting and allocation problem, etc. These kinds of problems possess a high computational complexity; therefore most of published literature is dedicated to simple flow shop or two-stage HFS machine environment.

Lot processing programming has differences in comparison with traditional job scheduling. On the one hand the job notation depends on the problem assumptions and requires an explicit interpretation; for the other hand one lot as well as one customer's demand can be considered as a job. The theoretical and practical interest on this issue represent models where job splitting is permitted -i.e. one job is allowed to split into sublots to process in parallel on the same or on various machines-. In many models, the sublot size is not clearly

Lot Processing in Hybrid Flow Shop Scheduling Problem 67

The HFS where there are parallel machines at certain stages is very common in industries, which have the same technological route for all products as a sequence of stages. HFSs have important applications in flexible manufacturing systems (FMS), such as electronics and furniture manufacturing, process industries such as chemical, textile, metallurgical, semiconductors, printed circuit board assembly lines, pharmaceutical, oil, food, automobile manufactures, steel making systems, etc. –see, e.g., Tang et al. (2002), Jin et al. (2002), Mathirajan & Sivakumar (2006) and Yaurima et al. (2009)–. Therefore, HFS scheduling has attracted interest by scientific community, being reflected in literature contributions dealing with this particular problem; however the issue of lot processing in this type of shops has

Let's establish some typical assumptions for a HFS scheduling problem with lot processing: • There are *k* stages of processing which occur in a linear order: 1…*k*. Each stage has a predetermined number of parallel machines. However, the number of machines varies

• A job represents the processing of entire lot of identical pieces, or a demand to produce

• Each job visits the stages in unidirectional order. Any stages may be skipped for a

• The lot size and the unit processing time on every machine are known in advance and are constant. The sublots belonging to the same lot may have different processing times,

• Sublots which do not have in-between setup time, form a production batch and are processed together without requiring any machine adjustment. Sublots belonging to different batches may need an essential setup time. A batch machine can process several

• All sublots contained in the same batch, start and complete at the same time.

• Buffers are located between stages to store intermediate products and are mentioned

the shop configuration, including the shop type and machine environment per stage. The

represents the number of stages in the shop. In this case, a HFS is denoted as FH in the

α

authors as Potts and Kovaliov (2000), denotes a flow shop with bath processing as *F*

parallel machines, *Q* uniform parallel machines, *R* unrelated parallel machines, and *D* dedicated parallel machines –see Błażewich et al. (2007) and Pinedo (2008) for in-depth definitions–. The notation *D* refers to an environment where the jobs to be processed are

α1, α2, α3, and α

, named Graham's triplet and recently actualized in (Ruiz &

2 is major that one. In the notation

4 describe the type and the number of the machines respectively, of the

1 indicates the considered shop. The parameter

α

α

α1α2 (α3α4 (1),

> α3α4(*k*), the

3 = ∅. Several

; there

4, and positioned as

3∈{∅, *P*, *Q*, *R*, *D*}, where *P* indicates identical

field denotes

α

α2

α1

a several quantity of identical pieces, which are processed in lots.

sublots simultaneously as long as machine capacity is not exceed.

Vazquez-Rodriguez, 2010), is used to describe different HFS variants. The

α

known in advanced for each machine. A single machine is denoted as

are no other specific symbols reported in literature for another shop types.

α

Interruptions in a sublot and batch processing generally are not allowed.

particular job but the process flow for all jobs is the same.

not gained sufficient attention.

from stage to stage.

a consequence of different sizes.

α*|*β|γ

2)). Here, parameter

field is decomposed into four parameter

position and the parameter value of

machine set environments for the stage *k*.

when they are limited.

The three-field notation

α3 and α

α3α4(2), …,α3α4 ( α

parameters

evident and must be optimized. When a sublot requires a considerable setup time on machine, the complexity of the problem become increased. The sublots grouping is another important aspect of the lot processing.

The scheduling theory offers two concepts to describe and to solve problems that involve treatment of lots: lot streaming and job batching. These concepts commonly appear together when jobs are allowed to be split. In this chapter, both topics and other relevant problems are discussed in context of HFS machine environment. A solution on a real manufacturing problem is described, where they are involved demand partitioning, lot splitting and batching sublots applied to a HFS2 problem with identical parallel machines at the first stage, and dedicated machines at the second stage.

The following contribution is organized as follows:

#### **2. Particularities of HFS with lot processing**

The HFS scheduling problem is a generalization of the classical flow shop problem by permitting multiple parallel processors in a stage toward to increase the overall capacities or to balance the capacities of the stages, or either to eliminate or to reduce the impact of bottleneck stages on the shop floor capacities (Morita & Shio, 2005). However, the number of variations of this problem is enormous. The HFS differs from the flexible flow line (Kochhar & Morris, 1987) and the flexible flow shop (Santos et al., 1995) problems. In a flexible flow line as well as in a flexible flow shop, available machines in each stage are identical. The HFS does not have this restriction. Some stages may have only one machine, but at least one stage must have a group of machines in parallel. These machines can be identical or generally different. The flow of products is unidirectional. In a classical HFS, each job is processed by at most one machine at each stage and at only one machine at a time. One machine processes no more than one job at each time. The time processing at the stages is known for each job.

66 Production Scheduling

evident and must be optimized. When a sublot requires a considerable setup time on machine, the complexity of the problem become increased. The sublots grouping is another

The scheduling theory offers two concepts to describe and to solve problems that involve treatment of lots: lot streaming and job batching. These concepts commonly appear together when jobs are allowed to be split. In this chapter, both topics and other relevant problems are discussed in context of HFS machine environment. A solution on a real manufacturing problem is described, where they are involved demand partitioning, lot splitting and batching sublots applied to a HFS2 problem with identical parallel machines at the first

• Section 2 introduces the HFS scheduling problem. Some properties and assumptions with certain particularities are discussed and referenced to representative and original

• In Section 3, four major concepts are explained in an in-depth fashion: The Group technology, which embodies jobs or demands according to similar attributes, is aimed to achieve high-volume production efficiency; the batch modeling, where its main definitions are explained and discussed, as long as known scientific papers; and Burn-in operations, a batch processing submodel commonly solicited in semiconductor manufacturing, representing one of the most complex problems in industry; and the Cell architectures that addressed the optimization problem –i.e. minimize production costs and maximize productivity– by the proper arrangement of resources.

• Lot streaming concept is discussed in Section 4. It is a technic that describes how a job

• A real manufacturing problem is analyzed in Section 5. A real example in electronic components manufacturing is presented; where the concepts described in this chapter are applied in order to show their usability, in theoretical and practical modeling

The HFS scheduling problem is a generalization of the classical flow shop problem by permitting multiple parallel processors in a stage toward to increase the overall capacities or to balance the capacities of the stages, or either to eliminate or to reduce the impact of bottleneck stages on the shop floor capacities (Morita & Shio, 2005). However, the number of variations of this problem is enormous. The HFS differs from the flexible flow line (Kochhar & Morris, 1987) and the flexible flow shop (Santos et al., 1995) problems. In a flexible flow line as well as in a flexible flow shop, available machines in each stage are identical. The HFS does not have this restriction. Some stages may have only one machine, but at least one stage must have a group of machines in parallel. These machines can be identical or generally different. The flow of products is unidirectional. In a classical HFS, each job is processed by at most one machine at each stage and at only one machine at a time. One machine processes no more than one job at

important aspect of the lot processing.

context.

stage, and dedicated machines at the second stage. The following contribution is organized as follows:

scientific contributions in this field of research.

Additionally, the setup time treatment issue is discussed.

• Finally, some conclusions in Section 6 are written.

**2. Particularities of HFS with lot processing**

each time. The time processing at the stages is known for each job.

must be split to process and to improve the scheduling result.

The HFS where there are parallel machines at certain stages is very common in industries, which have the same technological route for all products as a sequence of stages. HFSs have important applications in flexible manufacturing systems (FMS), such as electronics and furniture manufacturing, process industries such as chemical, textile, metallurgical, semiconductors, printed circuit board assembly lines, pharmaceutical, oil, food, automobile manufactures, steel making systems, etc. –see, e.g., Tang et al. (2002), Jin et al. (2002), Mathirajan & Sivakumar (2006) and Yaurima et al. (2009)–. Therefore, HFS scheduling has attracted interest by scientific community, being reflected in literature contributions dealing with this particular problem; however the issue of lot processing in this type of shops has not gained sufficient attention.

Let's establish some typical assumptions for a HFS scheduling problem with lot processing:

The three-field notation α*|*β|γ , named Graham's triplet and recently actualized in (Ruiz & Vazquez-Rodriguez, 2010), is used to describe different HFS variants. The α field denotes the shop configuration, including the shop type and machine environment per stage. The α field is decomposed into four parameter α1, α2, α3, and α4, and positioned as α1α2 (α3α4 (1), α3α4(2), …,α3α4 ( α2)). Here, parameter α1 indicates the considered shop. The parameter α2 represents the number of stages in the shop. In this case, a HFS is denoted as FH in the α1 position and the parameter value of α2 is major that one. In the notation α3α4 (*k*), the parameters α3 and α4 describe the type and the number of the machines respectively, of the machine set environments for the stage *k*. α3∈{∅, *P*, *Q*, *R*, *D*}, where *P* indicates identical parallel machines, *Q* uniform parallel machines, *R* unrelated parallel machines, and *D* dedicated parallel machines –see Błażewich et al. (2007) and Pinedo (2008) for in-depth definitions–. The notation *D* refers to an environment where the jobs to be processed are known in advanced for each machine. A single machine is denoted as α3 = ∅. Several authors as Potts and Kovaliov (2000), denotes a flow shop with bath processing as *F* ; there are no other specific symbols reported in literature for another shop types.

Lot Processing in Hybrid Flow Shop Scheduling Problem 69

An example of another classification scheme with explicit number of batch processing

two-machine flow shop, where the first machine is a classical machine, and the second is a batch machine that process up to two jobs simultaneously. Another example is the problem 1|*sfg*|Σ*Cj*, which denotes the total completion time minimization on a single (classical) machine, where there are job families and sequence-dependent family setup times (Potts & Kovaliov, 2000). It must be noted that due to the novelty of this class of models and scarcity of related work, there exist a lack of conventional notations for the scheduling problems

The manufactured products on a plant frequently have technical similarities; therefore can be sorted out into groups according to their design or manufacturing attributes, such as part shape, size, surface texture, material type, raw material estate. The technical similarities of the products within a group permit reduce essentially the number of setups on a machine. Consequently, manufacturing time is decreased and machine usage time is improved.

This idea was adapted as Group Technology (GT). The GT is an approach solicited in manufacturing and engineering management, that in general aims to achieve the efficiency of high-volume production by exploiting similarities of different products and activities in their production/execution (Cheng et al., 2008). The concept of GT is based on the simplification and standardization process, and according to Burbidge (1975) appeared at the beginning of 20th century. Numerous manufacturing companies have taken advantage of GT to improve the productivity and competitiveness –see Wemmerlov & Hyer (1989), Tatikonda & Wemmerlov (1992), Hadjinicola & Kumar (1993) and Gunasekaran et al. (2001)–. The first publications on scheduling in GT environments are trace back to Petrov

The GT originally emerged as a single machine concept that was created to reduce setup times (Mitrofanov, 1966). Then it was extended to the HFS problem with setup times dependent on the job sequence (Li, 1997). Andrés et al. (2005) introduced the concept of *coefficient of similarity* between each of the products, whose original rol was as parameter, allowing products to be grouped through a heuristic method; and contrary to the basic concept of *exploiting similarities* (taken from the GT philosophy). The first approach allows design engineers to retrieve existing drawings to support the design standardization of new parts and make an accurate cost estimation. The second one produces improvements to the control process, reduction of the setup time and standardized process plans (Kusiak, 1987). From the GT paradigm, two important concepts arise, product family and batch. The jobs are supposed to be partitioned into *F* families, *F* ≥ 1. A *batch* is a set of jobs of the same family that can be processed jointly (Brucker, 2004). Batching occurs only if setup costs or times are not negligible and several jobs of the same family have to be produced. The processing time depends only on the family of the batch. When the processing is performed in batches of identical items (lots), the processed operations are executed simultaneously. Thus, the completion time of all the jobs in a batch is the finishing time of the last job in the batch. Once the processing a batch is started, it cannot be interrupted, nor can other jobs be

2|*b*1 = 1; *b*2 = 2|*C*max, which denotes the *makespan* minimization in a

machines is problem *F*

with lot processing.

(1966).

**3. Batch processing 3.1 Group technology**

The parameter β –when used– lists the shop properties, which enumerate specific constraints and assumptions of the problem. The most common model properties associated with a HFS problem with lot processing are listed in Table 1.

Table. 1 Model properties associated with a HFS problem.

Finally, the γ field provides the criterion to be minimized. The most solicited Criterion to be minimized in a HFS scheduling problem, is the completion time. This particular objetive function takes place when the last job leaves the system, and is labeled as *makespan* or *Cmax*. Another common objetive functions are, among others:

Continuing with the context to the task at hand, the triplet (2) (1) (1) (1) (1) (2) (2) max 2( )| , , , , , | *j fg fi FH RM lot p p batch s split s C* = denotes the problem of scheduling jobs in a two-stage HFS with one batch machine on the first stage and unrelated parallel machines on the second. There exist, on the first stage, a few conditions that must present: lot processing, equal processing times of lots, batching of lots and sequence-dependent family setup time. Lot streaming into sublots and sequence independent setup times are presented on the second stage. The goal is to achieve a *makespan* minimum.

An example of another classification scheme with explicit number of batch processing machines is problem *F* 2|*b*1 = 1; *b*2 = 2|*C*max, which denotes the *makespan* minimization in a two-machine flow shop, where the first machine is a classical machine, and the second is a batch machine that process up to two jobs simultaneously. Another example is the problem 1|*sfg*|Σ*Cj*, which denotes the total completion time minimization on a single (classical) machine, where there are job families and sequence-dependent family setup times (Potts & Kovaliov, 2000). It must be noted that due to the novelty of this class of models and scarcity of related work, there exist a lack of conventional notations for the scheduling problems with lot processing.

#### **3. Batch processing**

68 Production Scheduling

constraints and assumptions of the problem. The most common model properties associated

*Batch* (Batch processing) A machine is able to process up to b jobs continuously without any setup. *bk = mk* The mk batch processing machines at the stage k.

without any setup in between.

*R* (Removal time) Machines become free only after the setup of the job has

been removed.

job *j*) That is the priority factor of the jobs in the system.

minimized in a HFS scheduling problem, is the completion time. This particular objetive function takes place when the last job leaves the system, and is labeled as *makespan* or *Cmax*.

Continuing with the context to the task at hand, the triplet

max 2( )| , , , , , | *j fg fi FH RM lot p p batch s split s C* = denotes the problem of scheduling jobs in a two-stage HFS with one batch machine on the first stage and unrelated parallel machines on the second. There exist, on the first stage, a few conditions that must present: lot processing, equal processing times of lots, batching of lots and sequence-dependent family setup time. Lot streaming into sublots and sequence independent setup times are presented on the second stage. The goal is to achieve a

–when used– lists the shop properties, which enumerate specific

The jobs belong to different job families. Jobs from the same family are processed on a machine one after another

A job (lot) splits into several parts (sublots) so that their operations may be overlapped. In case of shop with lot

The setup time of machine depend only on the job to

The setup time of machine to process job (batch) belonged to the family g depends on the previous job (batch) family

processing this parameter refers lot streaming.

field provides the criterion to be minimized. The most solicited Criterion to be

The parameter

*Fmls* (Job families)

*ssi* (Sequence-independent

*sfg* (Sequence-dependent family setup times)

γ

*makespan* minimum.

1. *F*max as maximum flow time. 2. *L*max as maximum lateness. 3. *T*max as maximum tardiness. 4. *E*max maximum earliness.

*wj* (Weight or importance of

*split*

setup times)

Finally, the

β

**Property Description**

*lot* Lot processing.

with a HFS problem with lot processing are listed in Table 1.

*prmp* The preemptions of jobs are allowed.

process.

*f*.

Table. 1 Model properties associated with a HFS problem.

Another common objetive functions are, among others:

(2) (1) (1) (1) (1) (2) (2)

#### **3.1 Group technology**

The manufactured products on a plant frequently have technical similarities; therefore can be sorted out into groups according to their design or manufacturing attributes, such as part shape, size, surface texture, material type, raw material estate. The technical similarities of the products within a group permit reduce essentially the number of setups on a machine. Consequently, manufacturing time is decreased and machine usage time is improved.

This idea was adapted as Group Technology (GT). The GT is an approach solicited in manufacturing and engineering management, that in general aims to achieve the efficiency of high-volume production by exploiting similarities of different products and activities in their production/execution (Cheng et al., 2008). The concept of GT is based on the simplification and standardization process, and according to Burbidge (1975) appeared at the beginning of 20th century. Numerous manufacturing companies have taken advantage of GT to improve the productivity and competitiveness –see Wemmerlov & Hyer (1989), Tatikonda & Wemmerlov (1992), Hadjinicola & Kumar (1993) and Gunasekaran et al. (2001)–. The first publications on scheduling in GT environments are trace back to Petrov (1966).

The GT originally emerged as a single machine concept that was created to reduce setup times (Mitrofanov, 1966). Then it was extended to the HFS problem with setup times dependent on the job sequence (Li, 1997). Andrés et al. (2005) introduced the concept of *coefficient of similarity* between each of the products, whose original rol was as parameter, allowing products to be grouped through a heuristic method; and contrary to the basic concept of *exploiting similarities* (taken from the GT philosophy). The first approach allows design engineers to retrieve existing drawings to support the design standardization of new parts and make an accurate cost estimation. The second one produces improvements to the control process, reduction of the setup time and standardized process plans (Kusiak, 1987).

From the GT paradigm, two important concepts arise, product family and batch. The jobs are supposed to be partitioned into *F* families, *F* ≥ 1. A *batch* is a set of jobs of the same family that can be processed jointly (Brucker, 2004). Batching occurs only if setup costs or times are not negligible and several jobs of the same family have to be produced. The processing time depends only on the family of the batch. When the processing is performed in batches of identical items (lots), the processed operations are executed simultaneously. Thus, the completion time of all the jobs in a batch is the finishing time of the last job in the batch. Once the processing a batch is started, it cannot be interrupted, nor can other jobs be

Lot Processing in Hybrid Flow Shop Scheduling Problem 71

The different jobs can be batched together but the processing time of the batch is given by the longest processing time among all jobs in the batch. The BPMs are encountered in many different environments such as chemical processes performed in tanks or kilns and burn-in operations in semiconductor industry. Problems related with scheduling BPMs has been received much attention in scheduling literature in recent years –see Lee et al. (1992), Uzsoy (1994), Li (1997), Brucker et al. (1998), Lee & Uzsoy (1999), Damodaran & Srihari (2004), Mathirajan & Sivakumar (2006), Damodaran et al. (2007) and Manjeshwar et al. (2009)–. Results of these researches are relevant to the HFS, although refer to the single BPM, parallel BPMs, or flow shop BPMs. Uzsoy (1994) described an application for burn-in operations in semiconductor manufacturing. In papers of Damodaran et al. (2007), Liao & Huang (2008), Manjeshwar et al. (2009), it have been provided applications of BPMs in the chemical treatment stage in rim (for bike) manufacturing facilities and in chambers for the environmental stress screening in the printed circuit board assembly environment,

The main classification of BPMs is related with *incompatible job families* vs. *compatible job families* (Perez et al., 2005). In the first model, only products belonging to the same family may be processed simultaneously. Uzsoy (1995), Kempf et al. (1998), Dobson and Nambimadon (2001) developed deterministic algorithms to schedule BPMs with incompatible job families. In the second model, it is assumed that products belonging to alternative families may be processed simultaneously –see Lee et al. (1992) where it is modeled burn-in oven as BPM–. Due to the complexity of BPM problems, scheduling

Quard and Kuhn (2007) investigate a s-batch scheduling problem for a HFS. Each job belongs to a specific product type. Setup costs are incurred when changing a machine of one product. On each stage, all jobs have the same process time. The objective is to minimize setup costs and the mean flow time. A target number of setups –i.e. parallel machines– for each product type and product type sequence are calculated for scheduling all production stages. The main focus of this paper is to derive the analogy of the scheduling problem to a two-dimensional packing problem and the development of a solution procedure that uses this analogy to solve the original HFS scheduling problem. Genetic algorithms are used as a

Xuan and Tang (2007) addressed the *s*-stage HFS problem of scheduling *n* jobs with s-batch processing at the last stage, and reduced to a two-stage HFS. The objective is to minimize a given criterion with respect to the completion time. When the jobs are grouped at the stage *s*, each batch *l* has a given size *bl* –i.e. consists of *bl* jobs–. The batch size can be different for all batches. All the jobs from the same batch must be processed on a machine at stage *s*  consecutively while satisfying given precedence constraints among the jobs within this batch. Each job *j* has a weight and the waiting of job processing between two adjacent stages causes a penalty cost. A sequence-independent setup time is considered separate from the processing time before the first job of batch *l* starts processing. It could be anticipatory, meaning that the setup of the next batch can start as soon as a machine becomes free to

respectivelly.

The two important decisions made on BPMs are:

• Scheduling the batches to improve a performance measure.

research almost focus on single and parallel BPMs (Perez et al., 2005).

• Grouping part families into batches, and

framework to incorporate these ideas.

added into the batch. The motivation for batching jobs is to gain in efficiency: the processing jobs in a batch maybe cheaper or faster than to individual processing (Potts & Kovaliov, 2000). The term of *family* denotes initial job partitioning, while the term of batch is used to denote a part of the solution. The task to calculate the *batch size* is to decide how many units must be processed consecutively. In Liu & Chang (2000) is indicated that batch sizes must be optimized, because the processing in large batches may increase the machine utilization and reduce the total setup time. However, large batch processing increases the flow time. Therefore, a tradeoff between flow time and machine utilization by selecting batch size and scheduling comes into discussion. According to the GT, no family can be split, only a single batch can be formed for each family.

Many publications use the term batch to denote the initial job partitioning and they use different names like sub-batch, lot, sublot, etc., to denote a set of jobs of the same family processed consecutively on the same machine.

#### **3.2 Batch models**

Batch setup models are partitioned into *batch availability* and *job availability* models (Potts & Kovaliov, 2000). According to the batch availability model, all the jobs of the same batch become available for processing and leave the machine together. For example, this situation occurs if the jobs in a batch are placed on a pallet, and the pallet is only moved from the machine when all of these jobs are processed. An alternative assumption is job availability (usually known in the literature as item availability), in which a job becomes available immediately after its processing is completed and completion times are independent of other jobs in the batch.

The processing time of a batch is calculated according to Lushchakova & Strusevich (2010) as follows:

When jobs sizes are considered, the case is usually called *a problem with bounded batches* if the total sizes of the jobs, contained in a batch, must not exceed the capacity of the batch, i.e. *b* > *n*. As far as each job may have a different size, the number of jobs in each batch may be different. On the other hand, if any number of jobs is allowed to be inserted in a batch, it is an called *unbounded batch*, respectively, *b* ≤ *n*. In this case batches are not restricted in processing any number of jobs (Yazdani & Jolai, 2010).

When one batch is completed, the recourse has to be adjusted for the next batch. Time needed for the setup activities depends on the families of both adjacent batches. A batch is called *feasible* if it can be processed without any tool switches.

#### **3.3 Batch processing machines**

In literature, parallel batching scheduling is known as batch processor scheduling or scheduling of *batch processing machine* (BPM). A BPM processes several jobs simultaneously. 70 Production Scheduling

added into the batch. The motivation for batching jobs is to gain in efficiency: the processing jobs in a batch maybe cheaper or faster than to individual processing (Potts & Kovaliov, 2000). The term of *family* denotes initial job partitioning, while the term of batch is used to denote a part of the solution. The task to calculate the *batch size* is to decide how many units must be processed consecutively. In Liu & Chang (2000) is indicated that batch sizes must be optimized, because the processing in large batches may increase the machine utilization and reduce the total setup time. However, large batch processing increases the flow time. Therefore, a tradeoff between flow time and machine utilization by selecting batch size and scheduling comes into discussion. According to the GT, no family can be split, only a single

Many publications use the term batch to denote the initial job partitioning and they use different names like sub-batch, lot, sublot, etc., to denote a set of jobs of the same family

Batch setup models are partitioned into *batch availability* and *job availability* models (Potts & Kovaliov, 2000). According to the batch availability model, all the jobs of the same batch become available for processing and leave the machine together. For example, this situation occurs if the jobs in a batch are placed on a pallet, and the pallet is only moved from the machine when all of these jobs are processed. An alternative assumption is job availability (usually known in the literature as item availability), in which a job becomes available immediately after its processing is completed and completion times are independent of

The processing time of a batch is calculated according to Lushchakova & Strusevich (2010)

• In Serial batching, also known as *s-batch* or "sum-batch", the processing time of a batch

• In Parallel batching, also known as *p-batch* or "max-batch", the processing time of a

When jobs sizes are considered, the case is usually called *a problem with bounded batches* if the total sizes of the jobs, contained in a batch, must not exceed the capacity of the batch, i.e. *b* > *n*. As far as each job may have a different size, the number of jobs in each batch may be different. On the other hand, if any number of jobs is allowed to be inserted in a batch, it is an called *unbounded batch*, respectively, *b* ≤ *n*. In this case batches are not restricted in

When one batch is completed, the recourse has to be adjusted for the next batch. Time needed for the setup activities depends on the families of both adjacent batches. A batch is

In literature, parallel batching scheduling is known as batch processor scheduling or scheduling of *batch processing machine* (BPM). A BPM processes several jobs simultaneously.

batch can be formed for each family.

**3.2 Batch models**

other jobs in the batch.

as follows:

processed consecutively on the same machine.

is equal to the total processing times of its jobs.

processing any number of jobs (Yazdani & Jolai, 2010).

**3.3 Batch processing machines**

called *feasible* if it can be processed without any tool switches.

batch is equal to the largest processing time of its jobs.

The different jobs can be batched together but the processing time of the batch is given by the longest processing time among all jobs in the batch. The BPMs are encountered in many different environments such as chemical processes performed in tanks or kilns and burn-in operations in semiconductor industry. Problems related with scheduling BPMs has been received much attention in scheduling literature in recent years –see Lee et al. (1992), Uzsoy (1994), Li (1997), Brucker et al. (1998), Lee & Uzsoy (1999), Damodaran & Srihari (2004), Mathirajan & Sivakumar (2006), Damodaran et al. (2007) and Manjeshwar et al. (2009)–. Results of these researches are relevant to the HFS, although refer to the single BPM, parallel BPMs, or flow shop BPMs. Uzsoy (1994) described an application for burn-in operations in semiconductor manufacturing. In papers of Damodaran et al. (2007), Liao & Huang (2008), Manjeshwar et al. (2009), it have been provided applications of BPMs in the chemical treatment stage in rim (for bike) manufacturing facilities and in chambers for the environmental stress screening in the printed circuit board assembly environment, respectivelly.

The two important decisions made on BPMs are:

The main classification of BPMs is related with *incompatible job families* vs. *compatible job families* (Perez et al., 2005). In the first model, only products belonging to the same family may be processed simultaneously. Uzsoy (1995), Kempf et al. (1998), Dobson and Nambimadon (2001) developed deterministic algorithms to schedule BPMs with incompatible job families. In the second model, it is assumed that products belonging to alternative families may be processed simultaneously –see Lee et al. (1992) where it is modeled burn-in oven as BPM–. Due to the complexity of BPM problems, scheduling research almost focus on single and parallel BPMs (Perez et al., 2005).

Quard and Kuhn (2007) investigate a s-batch scheduling problem for a HFS. Each job belongs to a specific product type. Setup costs are incurred when changing a machine of one product. On each stage, all jobs have the same process time. The objective is to minimize setup costs and the mean flow time. A target number of setups –i.e. parallel machines– for each product type and product type sequence are calculated for scheduling all production stages. The main focus of this paper is to derive the analogy of the scheduling problem to a two-dimensional packing problem and the development of a solution procedure that uses this analogy to solve the original HFS scheduling problem. Genetic algorithms are used as a framework to incorporate these ideas.

Xuan and Tang (2007) addressed the *s*-stage HFS problem of scheduling *n* jobs with s-batch processing at the last stage, and reduced to a two-stage HFS. The objective is to minimize a given criterion with respect to the completion time. When the jobs are grouped at the stage *s*, each batch *l* has a given size *bl* –i.e. consists of *bl* jobs–. The batch size can be different for all batches. All the jobs from the same batch must be processed on a machine at stage *s*  consecutively while satisfying given precedence constraints among the jobs within this batch. Each job *j* has a weight and the waiting of job processing between two adjacent stages causes a penalty cost. A sequence-independent setup time is considered separate from the processing time before the first job of batch *l* starts processing. It could be anticipatory, meaning that the setup of the next batch can start as soon as a machine becomes free to

Lot Processing in Hybrid Flow Shop Scheduling Problem 73

When separable setup/removal times are not negligible in the scheduling problem, they should be explicitly treated. In many real-life industrial problems such as surface mount technology or printed circuit board manufacturing, job setup is not part of processing time and the required time is sequence-dependent. Cheng et al. (2000) presents an interesting

The separable setup times could be *anticipatory* (*detached*) or *non-anticipatory* (*attached*). A setup is anticipatory if it can be started before the corresponding job or batch becomes available on the machine. In such a situation, the idle time of a machine can be used to complete the setup of a job on a specific machine. Otherwise, a setup is non-anticipatory, and the setup operations start only when the job arrives at a machine as long as the setup is attached to the job. Furthermore, setup time of a job at a specific machine could be

The setup may reflect the need to change a tool or to clean the machine. As in a family scheduling model, the jobs are partitioned into families according to their similarity, so that no setup is required for a job if it belongs to the same family of the previously processed job. However, a setup time is required at the start of the schedule and on each occasion when the machine switches from processing jobs in one family to jobs in another family. In such model, a batch is a maximal set of jobs that are scheduled contiguously on a machine and

The next setup analysis is proposed in the paper of Potts & Kovalyov (2000). Let {1, . . . , *n*} denote the set of jobs to be processed and *pj* is the processing time of job *j*, *j* = 1, . . . , *n*. Other parameters include a release date *rj*, a deadline *dj* , a due date *dj*, and a weight *wj*. The jobs are partitioned into *F* families. Let *nj* denote the number of jobs in family *f*, *f* = 1, ..., *F* . No setup is required between jobs of the same family. However, the *family setup time* on machine *i* when a job of family *g* is immediately preceded by a job of a different family *f* is *sifg*, or *si*0*g* if there is no preceding job. If, for each *g*, occurs that *sifg* = *si*0*g*= *sig* for all *f* ≠ *g*, then the setup times on machine *i* are *sequence independent*; otherwise, they are *sequence dependent*. If, for each machine *i*, *sifg* = *sfg* for all families *f* and *g* including the case *f* = 0, then the setup times are *machine independent*; otherwise, they are *machine dependent*. For the case of a single machine, setup times are, by definition, machine independent. Further, the reasonable assumption is that the *triangle inequality* holds for each machine *i*, which means that *sifh* ≤ *sifg* + *sigh*, for all distinct families *f*, *g* and *h*, including the case *f* = 0. Unless stated otherwise, the setups are assumed to be *anticipatory*, which means that a setup on a machine does not require the presence of any job. When there are release dates and for shop problems, sometimes the setups allow to be *non-anticipatory*, which means that the setup preceding the processing of some batch cannot start on the current machine before all jobs of this batch are

The minor and mayor setups implementation in a two-stage HFS problem with part family and batch production is proposed in Li (1997). Sequence independent bath setups are considered in Quard & Kuhn (2007), Xuan & Tang (2007). Sequence dependent bath setups

The concept of batch processing is arisen from burn-in operation in semiconductor manufacturing industries which represent today one of the most complex industrial

dependent on the job immediately preceding that job or be independent of it.

released and have completed their processing on any previous machine.

are included in the problem described by Luo et al. (2009).

review of flow shop scheduling research with setup times.

share a setup.

**3.5 Burn-in operation**

process the batch. Transportation times are also considered separate from the processing time. This paper establishes an integer programming model and proposes a batch decoupling based Lagrangian relaxation algorithm for this problem solution.

A two-stage HFS scheduling problem in a metal-working company is studied by Luo et al. (2009). The first stage consists of multiple parallel bounded-batch machines with job availability model, and the second stage has only one machine. The setup time is separated from job processing time and depends upon preceding job. A blocking environment exists between two stages with no intermediate buffer storage. Preventive maintenance and machine breakdown are presented. Two types of machine unavailability namely deterministic and stochastic case are identified in this problem. The former occurs on a stage two machine with the start time and the end time known in advance. The latter occurs on one of the parallel BPM in stage one and a real-time rescheduling will be triggered. Minimizing the makespan is considered as the objective to develop the optimal scheduling algorithm. A genetic algorithm is used to obtain a near- optimal solution. The computational results with actual data are favorable and superior over the results from existing manual schedules.

A two-stage HFS with several identical bounded p-batch processing machines is considered in the paper of Bellanger & Oulamara (2009). The problem is motivated by the scheduling of tire in the manufacturing industry. A compatibility relation is defined between each pair of tasks, so that an undirected compatibility graph is obtained which turns out to be an interval graph. The goal is to make batching and sequencing decisions in order to minimize the makespan. Since the problem is NP-hard, several heuristics are developed along with their worst cases analysis. The case in which tasks have the same processing time on the first stage also is considered, and a polynomial time approximation scheme (PTAS) algorithm is presented.

The review described in the above lines, shows that scientific literature in this addressed problem has small number of contributions. One of the main factors that could lead to this condition is that the BPM entails a high computational complexity. Then only one or two stages shops are investigated.

#### **3.4 Setup time treatment**

The structure of the breakdown time when a job belongs to a machine includes three phase as follows (Cheng et al., 2000):

The setup time is defined as the time required to shifting from one job to another on a given machine. There are separable and non-separable from the process operation. The *nonseparable* setup times are either included in the processing times or are negligible, and hence are ignored. There exist some situations in which the non-separable setup and removal operations must be modeled and closely coordinated. Such situations are common in automatic production systems which involve intermediate material handling devices, like automatic guided vehicles and robots, loading and unloading (Crama, 1997; Kim et al., 1997). The *separable* setup times are not part of processing operation.

72 Production Scheduling

process the batch. Transportation times are also considered separate from the processing time. This paper establishes an integer programming model and proposes a batch

A two-stage HFS scheduling problem in a metal-working company is studied by Luo et al. (2009). The first stage consists of multiple parallel bounded-batch machines with job availability model, and the second stage has only one machine. The setup time is separated from job processing time and depends upon preceding job. A blocking environment exists between two stages with no intermediate buffer storage. Preventive maintenance and machine breakdown are presented. Two types of machine unavailability namely deterministic and stochastic case are identified in this problem. The former occurs on a stage two machine with the start time and the end time known in advance. The latter occurs on one of the parallel BPM in stage one and a real-time rescheduling will be triggered. Minimizing the makespan is considered as the objective to develop the optimal scheduling algorithm. A genetic algorithm is used to obtain a near- optimal solution. The computational results with actual data are

A two-stage HFS with several identical bounded p-batch processing machines is considered in the paper of Bellanger & Oulamara (2009). The problem is motivated by the scheduling of tire in the manufacturing industry. A compatibility relation is defined between each pair of tasks, so that an undirected compatibility graph is obtained which turns out to be an interval graph. The goal is to make batching and sequencing decisions in order to minimize the makespan. Since the problem is NP-hard, several heuristics are developed along with their worst cases analysis. The case in which tasks have the same processing time on the first stage also is considered, and a polynomial time approximation scheme (PTAS) algorithm is

The review described in the above lines, shows that scientific literature in this addressed problem has small number of contributions. One of the main factors that could lead to this condition is that the BPM entails a high computational complexity. Then only one or two

The structure of the breakdown time when a job belongs to a machine includes three phase

1. Sequence independent/dependent setup time that is independent/dependent on the

3. Removal time that is independent/dependent on the job that had just been processed. The setup time is defined as the time required to shifting from one job to another on a given machine. There are separable and non-separable from the process operation. The *nonseparable* setup times are either included in the processing times or are negligible, and hence are ignored. There exist some situations in which the non-separable setup and removal operations must be modeled and closely coordinated. Such situations are common in automatic production systems which involve intermediate material handling devices, like automatic guided vehicles and robots, loading and unloading (Crama, 1997; Kim et al.,

1997). The *separable* setup times are not part of processing operation.

decoupling based Lagrangian relaxation algorithm for this problem solution.

favorable and superior over the results from existing manual schedules.

presented.

stages shops are investigated.

as follows (Cheng et al., 2000):

job to be processed. 2. Processing time of the job.

**3.4 Setup time treatment**

When separable setup/removal times are not negligible in the scheduling problem, they should be explicitly treated. In many real-life industrial problems such as surface mount technology or printed circuit board manufacturing, job setup is not part of processing time and the required time is sequence-dependent. Cheng et al. (2000) presents an interesting review of flow shop scheduling research with setup times.

The separable setup times could be *anticipatory* (*detached*) or *non-anticipatory* (*attached*). A setup is anticipatory if it can be started before the corresponding job or batch becomes available on the machine. In such a situation, the idle time of a machine can be used to complete the setup of a job on a specific machine. Otherwise, a setup is non-anticipatory, and the setup operations start only when the job arrives at a machine as long as the setup is attached to the job. Furthermore, setup time of a job at a specific machine could be dependent on the job immediately preceding that job or be independent of it.

The setup may reflect the need to change a tool or to clean the machine. As in a family scheduling model, the jobs are partitioned into families according to their similarity, so that no setup is required for a job if it belongs to the same family of the previously processed job. However, a setup time is required at the start of the schedule and on each occasion when the machine switches from processing jobs in one family to jobs in another family. In such model, a batch is a maximal set of jobs that are scheduled contiguously on a machine and share a setup.

The next setup analysis is proposed in the paper of Potts & Kovalyov (2000). Let {1, . . . , *n*} denote the set of jobs to be processed and *pj* is the processing time of job *j*, *j* = 1, . . . , *n*. Other parameters include a release date *rj*, a deadline *dj* , a due date *dj*, and a weight *wj*. The jobs are partitioned into *F* families. Let *nj* denote the number of jobs in family *f*, *f* = 1, ..., *F* . No setup is required between jobs of the same family. However, the *family setup time* on machine *i* when a job of family *g* is immediately preceded by a job of a different family *f* is *sifg*, or *si*0*g* if there is no preceding job. If, for each *g*, occurs that *sifg* = *si*0*g*= *sig* for all *f* ≠ *g*, then the setup times on machine *i* are *sequence independent*; otherwise, they are *sequence dependent*. If, for each machine *i*, *sifg* = *sfg* for all families *f* and *g* including the case *f* = 0, then the setup times are *machine independent*; otherwise, they are *machine dependent*. For the case of a single machine, setup times are, by definition, machine independent. Further, the reasonable assumption is that the *triangle inequality* holds for each machine *i*, which means that *sifh* ≤ *sifg* + *sigh*, for all distinct families *f*, *g* and *h*, including the case *f* = 0. Unless stated otherwise, the setups are assumed to be *anticipatory*, which means that a setup on a machine does not require the presence of any job. When there are release dates and for shop problems, sometimes the setups allow to be *non-anticipatory*, which means that the setup preceding the processing of some batch cannot start on the current machine before all jobs of this batch are released and have completed their processing on any previous machine.

The minor and mayor setups implementation in a two-stage HFS problem with part family and batch production is proposed in Li (1997). Sequence independent bath setups are considered in Quard & Kuhn (2007), Xuan & Tang (2007). Sequence dependent bath setups are included in the problem described by Luo et al. (2009).

#### **3.5 Burn-in operation**

The concept of batch processing is arisen from burn-in operation in semiconductor manufacturing industries which represent today one of the most complex industrial

Lot Processing in Hybrid Flow Shop Scheduling Problem 75

synchronization machinery and parts. Some aspects of those architectures affect the

In several flexible cell architectures each part is mounted on a fixed position in the cell and does not move until the processing machine –i.e. a robot– has completed all the required operations. A FMS recourse (machining center, robot, numerical control center, etc.) needs a certain time to switch the operating mode before the recourse can start (Co et al., 1990; Agnetis et al., 1993; Samaddar et al., 1999; Agnetis et al., 2003). There are generally two different types of setups. One setup occurs when a finished part is removed and replaced with a new part (*part replacement*). Another setup occurs when the machine switches from one operation type to another (*tool switch*). The part replacement setup usually makes more

Part replacement may be executed in two different ways named FMS *management policies*

• *Batching replacement*. All parts (up to a total *k*) currently being processed must be completed before new parts are loaded. A setup occurs whenever a new set of parts is loaded (*batch setup*), and another setup occurs at each tool switch (*tool setup*). Parts

• *Flexible replacement*. Part replacement takes places when it is completed. These setups

• Scheduling of the tools (and therefore the robot moves) required by program execution

The *tool schedule* is the sequence of tools (possibly repeated) loaded by the machine when processing a given batch. The total time required to process a batch is given by the total duration of the operations, plus the *total tool switching time*, which must be minimized. The length of a tool schedule is the length of the shortest tool schedule for that batch. Hence, for each batch, the scheduling subproblem consists of finding the batch length and the

Agnetis et al. (2003) provide two illustrative examples of a tool schedule problem for a

**Example 1.** There are three tools *a*, *b*, *c*, and a batch *B* consisting of three parts of program *P*1 = *abac*, *P*2 = *bacb*, and *P*3 = *abcb*. For instance, the tool schedule *abcabc* allows to complete *P*1 and *P*3 but not *P*2. Scheduling the tools in the order *abcbacb*, all the part programs can be completed, but this requires six tool switches. On the other hand, the tool schedule *abacb* allows to complete the three part programs using only four tool switches. The length of *B* is

Since the robot performs only one operation at a time, and the total duration of all operations is given, the objective only depends on the amount of time spent in setup activities (both batch and tool setups). The total batch setup time is equal to *Ts* (*b* - 1), where *b* is the number of batches. The total setup time is obtained summing the tool setup times of

robot, where any tool schedule is feasible, and provide that it is NP-hard.

Two subproblems must be simultaneously solved (Crama, 1997; Agnetis et al., 2003):

performance of FMS. One of such aspects is the presence of setups.

cannot be removed without stopping the cell operation.

time than the tool switch (Agnetis et al., 2003).

only occur at tool switches.

• Forming batches of at most *k* parts each one.

(Stecke & Kim, 1988):

in each batch.

corresponding tool schedule.

therefore five.

all batches.

environments. In semiconductor manufacturing, there are parallel machines, different types of processes like batch processes and single wafer processes, sequence-dependent setup times, prescribed customer due dates for the lots, very expensive equipment, reentrant process flows, etc. In such a changeable scenario, maintaining a competitive advantage and remaining profitable in operational terms requires minimization of cycle time, work-inprocess (WIP) inventory and the maximization of throughput.

As a part of the complex production line that exists in a semiconductor manufacturing facility, operations involved in BPM are considered to be a bottleneck. This is because the processing times of the lots on the BPM are usually very long compared to other processes, and batching decisions may affect the performance of the entire semiconductor manufacturing process. Semiconductor manufacturing involves numerous batch-processing operations like oxidation, diffusion, deposition, etching, e-beam writing and heat treatment of wafer fabrication, baking of wafer probing, and burn-in operation of device testing.

The *semiconductor burn-in scheduling problem* was first introduced by Lee et al. (2006) and then studied by Mathirajan et al. (2010). The purpose of burn-in operation is to test the integrated circuit (IC) chips. Due to various processes employed in the manufacturing process, some chips may be "fragile" and may fail only after a short period of time. It is essential that these devices are identified and scrapped as "infant mortality". The process of identifying and scrapping these "fragile" devices is known as the *burn-in operation*. It involves subjecting the chips, placed in an oven, to electrical and thermal stress to force the failure of weak or fragile devices.

IC chips arrive at the burn-in area in lots consisting of a number of IC chips of the same product type. Each lot is referred as a job. In a burn-in operation, IC chips of each job are loaded onto *boards*; each job has different lot sizes so that those job sizes (number of demanded boards) are not identical. The boards are often product-specific, and a job cannot be processed without the necessary boards. Once IC chips have been loaded onto the boards, the boards are placed into an oven. Typically, the oven capacity is larger than the job size, so the number of boards in an oven can hold defines the oven capacity, and the size of a job is defined by the number of boards it requires. Each IC chip has a pre-specified minimum burn-in time, which may depend on its type and/or the customer's requirements. Since IC chips may stay in the oven for a period longer than their minimum required burnin time, it is possible to place different products (jobs) in the oven simultaneously.

The processing time of each batch equals the longest minimum-exposure time among all the products (jobs) in the batch. Effective burn-in operation scheduling is a key issue because it causes frequently a bottleneck due to long processing times relative to other testing operations –e.g. days as opposed to hours– and because it occurs at the end of the manufacturing process and thus has a strong influence on ship dates (Azizoglu & Webster, 2000).

#### **3.6 Cell architectures**

The arisen of FMS has triggered many researches dedicated to distinct aspects of their design and functionality. New cell architectures are proposed and new types of management problems are analyzed. Most of the recourse models are dedicated to minimize production costs, that is, the productivity maximization, through optimally allocation and 74 Production Scheduling

environments. In semiconductor manufacturing, there are parallel machines, different types of processes like batch processes and single wafer processes, sequence-dependent setup times, prescribed customer due dates for the lots, very expensive equipment, reentrant process flows, etc. In such a changeable scenario, maintaining a competitive advantage and remaining profitable in operational terms requires minimization of cycle time, work-in-

As a part of the complex production line that exists in a semiconductor manufacturing facility, operations involved in BPM are considered to be a bottleneck. This is because the processing times of the lots on the BPM are usually very long compared to other processes, and batching decisions may affect the performance of the entire semiconductor manufacturing process. Semiconductor manufacturing involves numerous batch-processing operations like oxidation, diffusion, deposition, etching, e-beam writing and heat treatment of wafer fabrication, baking of wafer probing, and burn-in operation of device testing.

The *semiconductor burn-in scheduling problem* was first introduced by Lee et al. (2006) and then studied by Mathirajan et al. (2010). The purpose of burn-in operation is to test the integrated circuit (IC) chips. Due to various processes employed in the manufacturing process, some chips may be "fragile" and may fail only after a short period of time. It is essential that these devices are identified and scrapped as "infant mortality". The process of identifying and scrapping these "fragile" devices is known as the *burn-in operation*. It involves subjecting the chips, placed in an oven, to electrical and thermal stress to force the

IC chips arrive at the burn-in area in lots consisting of a number of IC chips of the same product type. Each lot is referred as a job. In a burn-in operation, IC chips of each job are loaded onto *boards*; each job has different lot sizes so that those job sizes (number of demanded boards) are not identical. The boards are often product-specific, and a job cannot be processed without the necessary boards. Once IC chips have been loaded onto the boards, the boards are placed into an oven. Typically, the oven capacity is larger than the job size, so the number of boards in an oven can hold defines the oven capacity, and the size of a job is defined by the number of boards it requires. Each IC chip has a pre-specified minimum burn-in time, which may depend on its type and/or the customer's requirements. Since IC chips may stay in the oven for a period longer than their minimum required burn-

in time, it is possible to place different products (jobs) in the oven simultaneously.

and thus has a strong influence on ship dates (Azizoglu & Webster, 2000).

The processing time of each batch equals the longest minimum-exposure time among all the products (jobs) in the batch. Effective burn-in operation scheduling is a key issue because it causes frequently a bottleneck due to long processing times relative to other testing operations –e.g. days as opposed to hours– and because it occurs at the end of the manufacturing process

The arisen of FMS has triggered many researches dedicated to distinct aspects of their design and functionality. New cell architectures are proposed and new types of management problems are analyzed. Most of the recourse models are dedicated to minimize production costs, that is, the productivity maximization, through optimally allocation and

process (WIP) inventory and the maximization of throughput.

failure of weak or fragile devices.

**3.6 Cell architectures**

synchronization machinery and parts. Some aspects of those architectures affect the performance of FMS. One of such aspects is the presence of setups.

In several flexible cell architectures each part is mounted on a fixed position in the cell and does not move until the processing machine –i.e. a robot– has completed all the required operations. A FMS recourse (machining center, robot, numerical control center, etc.) needs a certain time to switch the operating mode before the recourse can start (Co et al., 1990; Agnetis et al., 1993; Samaddar et al., 1999; Agnetis et al., 2003). There are generally two different types of setups. One setup occurs when a finished part is removed and replaced with a new part (*part replacement*). Another setup occurs when the machine switches from one operation type to another (*tool switch*). The part replacement setup usually makes more time than the tool switch (Agnetis et al., 2003).

Part replacement may be executed in two different ways named FMS *management policies* (Stecke & Kim, 1988):

Two subproblems must be simultaneously solved (Crama, 1997; Agnetis et al., 2003):

The *tool schedule* is the sequence of tools (possibly repeated) loaded by the machine when processing a given batch. The total time required to process a batch is given by the total duration of the operations, plus the *total tool switching time*, which must be minimized. The length of a tool schedule is the length of the shortest tool schedule for that batch. Hence, for each batch, the scheduling subproblem consists of finding the batch length and the corresponding tool schedule.

Agnetis et al. (2003) provide two illustrative examples of a tool schedule problem for a robot, where any tool schedule is feasible, and provide that it is NP-hard.

**Example 1.** There are three tools *a*, *b*, *c*, and a batch *B* consisting of three parts of program *P*1 = *abac*, *P*2 = *bacb*, and *P*3 = *abcb*. For instance, the tool schedule *abcabc* allows to complete *P*1 and *P*3 but not *P*2. Scheduling the tools in the order *abcbacb*, all the part programs can be completed, but this requires six tool switches. On the other hand, the tool schedule *abacb* allows to complete the three part programs using only four tool switches. The length of *B* is therefore five.

Since the robot performs only one operation at a time, and the total duration of all operations is given, the objective only depends on the amount of time spent in setup activities (both batch and tool setups). The total batch setup time is equal to *Ts* (*b* - 1), where *b* is the number of batches. The total setup time is obtained summing the tool setup times of all batches.

Lot Processing in Hybrid Flow Shop Scheduling Problem 77

As is pointed out by Potts and Van Wassenhove (1992), there are two main advantages of splitting jobs into sublots*.* Firs, splitting jobs may improve customer service; each sublot can be delivered to the customer immediately upon completion, without waiting for the remaining sublots of the same job. The other motivation for splitting jobs in multi-stage production systems is to enable various operations of the same job to be overlapped by allowing processing of downstream operations to begin immediately for any sublot which

The concept and practice of lot streaming are not new. The term of lot streaming was first introduced by Reiter (1966). Graves & Kostreva (1986) gave the notion of *overlapping operations* in material requirements planning (MRP) systems. The use of transfer batches (or

So, *lot streaming* is the process of splitting an entire production job (*process batch*) into sublots (*transfer batches*) and scheduling those sublots in an overlapping fashion, in order to accelerate the progress of an order in production. A job is defined here as a production order (*lot*) composed of many identical items (Potts & Baker, 1989), (Baker & Jia, 1993), (Çetinkaya & Duman, 2010). In many practical situations, splitting a lot is both possible and desirable. When a job is split into a number of sublots, a sublot can be processed on a machine even if the other sublots still have not been processed on the upstream machines. The *lot streaming problem* is to decide the optimal number of sublots for each job, the optimal size of each sublot and the optimal sequence for processing the sublots so that the production lead time is minimized. It combines lot sizing and scheduling decisions that were traditionally treated

Different sublots of the same job should be processed simultaneously at different stages. As a result of operation overlapping, the production is remarkably accelerated and the idle time on successive machines is reduced. In general, the makespan will be minimized if there is just one item in each sublot (Vickson & Alfredsson, 1992). Nevertheless, there may be practical considerations that make it undesirable to have a large number of unitsized sublots. It may be possible to attain the minimum makespan with fewer sublots, or there may be difficult in tracking a large number or small sublots. A lot splitting problem finds a compromise between sizes of batch process and sublots when setups are long and difficult. An example of lot streaming benefits for three-machine flow shop, a single job, with the job processing times of 6, 3 and 6 time units is shown on Fig. 1 borrowed from Pan et al. (2010). If the job is not split into sublots, the job completion time is 15 time units (Fig. 1a). When the job is split into three sublots and no-idling production interruption time is allowed between any two adjacent sublots, the job completion time is reduced to 11 time units (Fig. 1b), whereas for the idling case, the job completion time is further reduced to nine time units (Fig. 1c). Obviously, the completion time of the job under the idling case is shorter than the one under the no-idling case with the same sublot type. However, there are also many practical applications for the lot-streaming flow shop

has been processed at the current stage.

Baker and Pyke (1990) consider two cases of job splitting:

separately (Baker & Jia, 1993; Zhang et al., 2005).

scheduling under no-idling case.

• Lot streaming, where overlapping operations are permitted.

• Preemption, i.e., Interruption of the production run for a more urgent job;

sublots) is a key element of synchronous manufacturing (Umble & Srikanth, 1990).

**Example 2.** Besides batch *B* of the previous example, suppose there is also another batch *B'* formed by parts *P*4 = *bcba*, *P*5 = *caba*, and *P*6 = *bcab*. The length of *B'* is also five, obtained for the tool schedule *bcaba*. When batches *B* and *B'* are performed, the overall time spent in setup activities is given as *Ts* + 8 *ts*, where *Ts* is loading new batch setup time, and *ts* is any tool switch setup time.

In some situations, the more relevant performance criterion is the number of batches (*switching instants*). This is the case, when the setup time of operations is proportional to the number of tool interchanges, or when the tool transportation system is congested. The distinction between the number of tool switches and the number of switching instants is considered in Tang & Denardo (1988a), Tang & Denardo (1988b) and Sodhi et al. (1994). The more general formulation of the *tool switching problem* is given by Crama (1997) as follows: Determine a part input sequence and an associated sequence of tool loadings such that all the tools required by the *j-*th part are present in the *j-*th tool loading and the total number of tool switches is minimized.

Crama et al. (1994) proved that the tool switching problem is NP-hard for any fixed *C* ≥ 2, where the number *C* is the *capacity* of the tool magazine. They also observed that deciding whether there exists a job sequence requiring exactly *M* tool setups is NP-hard, where *M* is the total number of tools needed to process all the parts. This latter result conduced to the *gate matrix permutation problem* discussed in the paper of Mohring (1990). The gate matrix permutation problem is to assess the minimum value of the tool magazine capacity such that no tool needs to be set up twice. Since this problem is NP-hard, the tool switching problem is NP-hard too. When all setup times are equal –i.e. when the objective is only to minimize the total number of switches– then the integer program can be solved by a greedy algorithm which turns out to be equivalent to the so-called *keep tool needed soonest policy* (KTNS) –see Tang & Denardo (1988a)–.

#### **4. Lot streaming**

#### **4.1 Job splitting**

In most multi-stage scheduling studies associated with processing products, a *production batch* (lot) is treated as a single entity called *job* which consists of only one part. As a result, the schedule cannot be improved any more, even if there may be plenty of idle times at machines; that is, partial transfer of completed items in a job between machines is assumed to be impossible. Since the production lots are often large, items already processed on a machine need to wait a long time in the output buffer of this machine whereas the downstream machine may be idle. It can lead to large WIP inventories between the machines and make longer the makespan. When the above assumption is relaxed in the corresponding scheduling problem –i.e. when it is supposed that a job can be split– it may be possible to improve the quality of the resulting schedule. Hence, the production leading times, WIP inventory, interim storage and space requirements, and material handling system capacity requirements can be decreased (Truscott, 1986). The solutions can be implemented in a lesser time and at a lower cost than reorganization. Moreover, when the processing requirement of a job is considered as a total demand of a product in production planning, jobs can be split arbitrarily into continuous sublots and processed independently on *m* machines to finish the processing all demands as soon as possible (Xing & Zhang, 2000).

76 Production Scheduling

**Example 2.** Besides batch *B* of the previous example, suppose there is also another batch *B'* formed by parts *P*4 = *bcba*, *P*5 = *caba*, and *P*6 = *bcab*. The length of *B'* is also five, obtained for the tool schedule *bcaba*. When batches *B* and *B'* are performed, the overall time spent in setup activities is given as *Ts* + 8 *ts*, where *Ts* is loading new batch setup time, and *ts* is any

In some situations, the more relevant performance criterion is the number of batches (*switching instants*). This is the case, when the setup time of operations is proportional to the number of tool interchanges, or when the tool transportation system is congested. The distinction between the number of tool switches and the number of switching instants is considered in Tang & Denardo (1988a), Tang & Denardo (1988b) and Sodhi et al. (1994). The more general formulation of the *tool switching problem* is given by Crama (1997) as follows: Determine a part input sequence and an associated sequence of tool loadings such that all the tools required by the *j-*th part are present in the *j-*th tool loading and the total number of

Crama et al. (1994) proved that the tool switching problem is NP-hard for any fixed *C* ≥ 2, where the number *C* is the *capacity* of the tool magazine. They also observed that deciding whether there exists a job sequence requiring exactly *M* tool setups is NP-hard, where *M* is the total number of tools needed to process all the parts. This latter result conduced to the *gate matrix permutation problem* discussed in the paper of Mohring (1990). The gate matrix permutation problem is to assess the minimum value of the tool magazine capacity such that no tool needs to be set up twice. Since this problem is NP-hard, the tool switching problem is NP-hard too. When all setup times are equal –i.e. when the objective is only to minimize the total number of switches– then the integer program can be solved by a greedy algorithm which turns out to be equivalent to the so-called *keep tool needed soonest policy*

In most multi-stage scheduling studies associated with processing products, a *production batch* (lot) is treated as a single entity called *job* which consists of only one part. As a result, the schedule cannot be improved any more, even if there may be plenty of idle times at machines; that is, partial transfer of completed items in a job between machines is assumed to be impossible. Since the production lots are often large, items already processed on a machine need to wait a long time in the output buffer of this machine whereas the downstream machine may be idle. It can lead to large WIP inventories between the machines and make longer the makespan. When the above assumption is relaxed in the corresponding scheduling problem –i.e. when it is supposed that a job can be split– it may be possible to improve the quality of the resulting schedule. Hence, the production leading times, WIP inventory, interim storage and space requirements, and material handling system capacity requirements can be decreased (Truscott, 1986). The solutions can be implemented in a lesser time and at a lower cost than reorganization. Moreover, when the processing requirement of a job is considered as a total demand of a product in production planning, jobs can be split arbitrarily into continuous sublots and processed independently on *m* machines to finish the processing all demands as soon as possible (Xing & Zhang,

tool switch setup time.

tool switches is minimized.

(KTNS) –see Tang & Denardo (1988a)–.

**4. Lot streaming 4.1 Job splitting**

2000).

As is pointed out by Potts and Van Wassenhove (1992), there are two main advantages of splitting jobs into sublots*.* Firs, splitting jobs may improve customer service; each sublot can be delivered to the customer immediately upon completion, without waiting for the remaining sublots of the same job. The other motivation for splitting jobs in multi-stage production systems is to enable various operations of the same job to be overlapped by allowing processing of downstream operations to begin immediately for any sublot which has been processed at the current stage.

Baker and Pyke (1990) consider two cases of job splitting:

The concept and practice of lot streaming are not new. The term of lot streaming was first introduced by Reiter (1966). Graves & Kostreva (1986) gave the notion of *overlapping operations* in material requirements planning (MRP) systems. The use of transfer batches (or sublots) is a key element of synchronous manufacturing (Umble & Srikanth, 1990).

So, *lot streaming* is the process of splitting an entire production job (*process batch*) into sublots (*transfer batches*) and scheduling those sublots in an overlapping fashion, in order to accelerate the progress of an order in production. A job is defined here as a production order (*lot*) composed of many identical items (Potts & Baker, 1989), (Baker & Jia, 1993), (Çetinkaya & Duman, 2010). In many practical situations, splitting a lot is both possible and desirable. When a job is split into a number of sublots, a sublot can be processed on a machine even if the other sublots still have not been processed on the upstream machines. The *lot streaming problem* is to decide the optimal number of sublots for each job, the optimal size of each sublot and the optimal sequence for processing the sublots so that the production lead time is minimized. It combines lot sizing and scheduling decisions that were traditionally treated separately (Baker & Jia, 1993; Zhang et al., 2005).

Different sublots of the same job should be processed simultaneously at different stages. As a result of operation overlapping, the production is remarkably accelerated and the idle time on successive machines is reduced. In general, the makespan will be minimized if there is just one item in each sublot (Vickson & Alfredsson, 1992). Nevertheless, there may be practical considerations that make it undesirable to have a large number of unitsized sublots. It may be possible to attain the minimum makespan with fewer sublots, or there may be difficult in tracking a large number or small sublots. A lot splitting problem finds a compromise between sizes of batch process and sublots when setups are long and difficult. An example of lot streaming benefits for three-machine flow shop, a single job, with the job processing times of 6, 3 and 6 time units is shown on Fig. 1 borrowed from Pan et al. (2010). If the job is not split into sublots, the job completion time is 15 time units (Fig. 1a). When the job is split into three sublots and no-idling production interruption time is allowed between any two adjacent sublots, the job completion time is reduced to 11 time units (Fig. 1b), whereas for the idling case, the job completion time is further reduced to nine time units (Fig. 1c). Obviously, the completion time of the job under the idling case is shorter than the one under the no-idling case with the same sublot type. However, there are also many practical applications for the lot-streaming flow shop scheduling under no-idling case.

Lot Processing in Hybrid Flow Shop Scheduling Problem 79

There are *discrete* and *continuous* versions of lot splitting. In *discrete version* the sublot sizes are integers that correspond to discrete numbers of units in each sublot. Typically, these problems can be formulated as an integer linear program. Anticipating that this may be a difficult problem to solve, lot splitting becomes a *continuous version* of the problem in which the integer restrictions are relaxed. Such a routing may be acceptable if lot size is large and the number of sublots is small. The optimal makespan in the continuous version also serves as a lower bound on the optimal makespan in the discrete version, and the makespan produced by rounding the continuous solution serves as an upper bound (Trietsch &

Lot streaming is very common among modern manufacturing systems, furthermore, also introduces an additional complexity in the problems. Each sublot can be viewed as an individual job and the problem size drastically increases with the total number of sublots. If it is assumed that a job consists of a batch as in many real manufacturing environments, then we can obtain an improved schedule. However then, the size of the scheduling problem would become too large to be solved in practical time limit (Jeong et al., 1997). The review on lot streaming problems can be found in several papers –see Potts & Baker (1989),

The publications on lot streaming problems can easily be categorized into two main streams: • dealing with the determination of the optimal sublot sizes for a single job (also called

• addressing the sublot sizing and job sequencing decisions simultaneously for the

Lot streaming is very useful as many practical production systems can be considered as HFS, however has received very limited research attention. Some of them will be reviewed

Tsubone et al. (1996) studied the lot streaming problem in a two-stage HFS with one machine in the first stage and several process lines in the second stage. They examined the impact of lot size, sequencing rules and scheduling scenarios on production makespan, capacity utilization and WIP inventory, using simulation. Zhang et al. (2003) analyzed the integer version of the m-1 HFS lot streaming problem. They solved special cases of the equal-sublot version of the problem, in which one of the stages was obviously a bottleneck. The general problem is formulated as a mixed integer linear programming (MILP) model and solved using two heuristics. Both heuristics enumerated the number of sublots, and for each given number of sublots, allocated the sublots as evenly as possible to stage-1 machines. The sublot sizes were then determined by making them as equal as possible in one heuristic, and by using a smaller MILP model in the other. In this contribution, the

Potts & Wassenhove (1992), Trietsch & Baker (1993) and Chang & Chiu (2005)–.

multiple-job case, given various job and shop characteristics.

• *Consistent* - sublots sizes vary within a lot but are the same for all machines,

Sublot sizes can be (Trietsch & Baker, 1993):

Backer, 1993).

sublot sizing);

in the following.

**4.2 HFS lot streaming problem state of art**

• *Equal* - all sublots of a given lot are of equal size,

• *Variable* - sublot sizes can change from machine to machine.

Fig. 1. An example of the lot-streaming flow shop scheduling: a) schedule without sublots; b) schedule with sublots under no-idling case; c) schedule with sublots under idling case.

In the past two decades, with the increasing interest in just-in-time (JIT) and optimized production technology (OPT) philosophies in manufacturing systems, the application of lot streaming idea in scheduling problems has received considerable attention. The JIT approach views each item in the lot as a single unit or job since these results look for a minimum makespan. Through the extensive use of JIT system in manufacturing, the performance measure related to both earliness and tardiness penalties has raised significant attention in lot streaming literature (Kulonda, 1984; Glass et al., 1994; Pan et al., 2010).

One more positive aspect of lot streaming is mentioned in Jeong et al. (1997):

"By assuming that a batch can be split, we can handle the problems that occur due to dynamic nature of shop floor more elegantly. Most past solutions to scheduling problems assume that a manufacturing shop is operating steady and peacefully. But a real factory is full of unexpectedness and dynamics. The causes of such dynamism are very diverse, e.g. human errors, rush orders, requests from customers to shorten the delivery dates, and hardware related events - tool breakage, machine failure, etc. These events cannot be expected beforehand, and therefore, it is very hard to strictly observe the original schedule. As suggested earlier, we can get much better solution considering alternative schedules which allow the splitting of current batches in smaller batches."

Sublot sizes can be (Trietsch & Baker, 1993):

78 Production Scheduling

3 6 9 12 15

a)

2

111 M3 2 2

2

One more positive aspect of lot streaming is mentioned in Jeong et al. (1997):

which allow the splitting of current batches in smaller batches."

111 M3 2 2

3 6 9 12 15

b)

3 6 9 12 15

c) Fig. 1. An example of the lot-streaming flow shop scheduling: a) schedule without sublots; b) schedule with sublots under no-idling case; c) schedule with sublots under idling case.

In the past two decades, with the increasing interest in just-in-time (JIT) and optimized production technology (OPT) philosophies in manufacturing systems, the application of lot streaming idea in scheduling problems has received considerable attention. The JIT approach views each item in the lot as a single unit or job since these results look for a minimum makespan. Through the extensive use of JIT system in manufacturing, the performance measure related to both earliness and tardiness penalties has raised significant attention in lot streaming literature (Kulonda, 1984; Glass et al., 1994; Pan et al.,

"By assuming that a batch can be split, we can handle the problems that occur due to dynamic nature of shop floor more elegantly. Most past solutions to scheduling problems assume that a manufacturing shop is operating steady and peacefully. But a real factory is full of unexpectedness and dynamics. The causes of such dynamism are very diverse, e.g. human errors, rush orders, requests from customers to shorten the delivery dates, and hardware related events - tool breakage, machine failure, etc. These events cannot be expected beforehand, and therefore, it is very hard to strictly observe the original schedule. As suggested earlier, we can get much better solution considering alternative schedules

3

6

6

2

2

2 2

2 2

M3 M2 M1

M2 M1

M2 M1

2010).

There are *discrete* and *continuous* versions of lot splitting. In *discrete version* the sublot sizes are integers that correspond to discrete numbers of units in each sublot. Typically, these problems can be formulated as an integer linear program. Anticipating that this may be a difficult problem to solve, lot splitting becomes a *continuous version* of the problem in which the integer restrictions are relaxed. Such a routing may be acceptable if lot size is large and the number of sublots is small. The optimal makespan in the continuous version also serves as a lower bound on the optimal makespan in the discrete version, and the makespan produced by rounding the continuous solution serves as an upper bound (Trietsch & Backer, 1993).

Lot streaming is very common among modern manufacturing systems, furthermore, also introduces an additional complexity in the problems. Each sublot can be viewed as an individual job and the problem size drastically increases with the total number of sublots. If it is assumed that a job consists of a batch as in many real manufacturing environments, then we can obtain an improved schedule. However then, the size of the scheduling problem would become too large to be solved in practical time limit (Jeong et al., 1997). The review on lot streaming problems can be found in several papers –see Potts & Baker (1989), Potts & Wassenhove (1992), Trietsch & Baker (1993) and Chang & Chiu (2005)–.

The publications on lot streaming problems can easily be categorized into two main streams:

#### **4.2 HFS lot streaming problem state of art**

Lot streaming is very useful as many practical production systems can be considered as HFS, however has received very limited research attention. Some of them will be reviewed in the following.

Tsubone et al. (1996) studied the lot streaming problem in a two-stage HFS with one machine in the first stage and several process lines in the second stage. They examined the impact of lot size, sequencing rules and scheduling scenarios on production makespan, capacity utilization and WIP inventory, using simulation. Zhang et al. (2003) analyzed the integer version of the m-1 HFS lot streaming problem. They solved special cases of the equal-sublot version of the problem, in which one of the stages was obviously a bottleneck. The general problem is formulated as a mixed integer linear programming (MILP) model and solved using two heuristics. Both heuristics enumerated the number of sublots, and for each given number of sublots, allocated the sublots as evenly as possible to stage-1 machines. The sublot sizes were then determined by making them as equal as possible in one heuristic, and by using a smaller MILP model in the other. In this contribution, the

Lot Processing in Hybrid Flow Shop Scheduling Problem 81

used jointly with two other lower bounds obtained from the direct analysis of the problem structure. Extensive experiments showed that the aggregated machine heuristic performs

Liu (2008) studied the single-job lot streaming problem in a two-stage HFS that has *m* identical machines at the first stage and one machine at the second stage, called *m*-1 HFS, the same machine environment that in Zhang et al. (2005). The job is splitted into sublots. It is not necessary for the sizes of the sublots to be equal or to be integers, but they must not be smaller than a lower bound, x0 ≥ 0. A sublot will be treated as an independent entity during the production in the system. Each sublot requires processing on anyone of the machines at the first stage and then on the machine at the second stage. The processing times of a sublot at the two stages are proportional to its size. The unit processing times on the stage-1 and stage-2 machines are *p*(1) and *p*(2), respectively. Each machine can process at most one sublot

Before the processing of each sublot on a machine, a setup time is required for loading the sublot onto the machine. The setup times on the machines of stages 1 and 2 are *s*(1) and *s*(2), respectively, which are independent of the processing sequence and the sizes of the sublots. The problem is to determine the number and the sizes of the sublots and the schedule of processing them on the machines to minimize the makespan (the completion time of the

For the problem with a fixed number of sublots, Liu (2008) proved that it is optimal to use a rotation method for allocating and sequencing the sublots on the machines previously used by Zhang et al. (2003): First, number the sublots is 1, 2, . . ., *l*. Then, allocate and sequence these sublots on the stage-1 machines in ''rotation'', i.e. assign sublot 1 to machine 1, sublot 2 to machine 2, ..., sublot *m* to machine *m*, sublot *m* + 1 to machine 1, and so on. Finally,

Hereafter it is referred to the first sublots on the first-stage machines as the first batch of sublots, to the second sublots on these machines as the second batch, and so on. The

1. The numbers of sublots processed on the stage-1 machines are *balanced* –i.e. each stage-

2. The sublots are processed on the stage-2 machine in the order of their batch numbers; 3. For the sublots in the same batch, the processing on the stage-2 machine is in the order

When the sublots are allocated using the rotation method, the only remaining decision is to determine the sizes of the sublots. As all the discrete decisions are fixed, the problem of determining the sublot sizes can be formulated as a LP model. Then the problem with equal sublot sizes is considered and an efficient solution to determining the optimal number of sublots is developed. Finally, optimal and heuristic solution methods for the general problem are proposed and the worst-case performance of the equal-sublot solution is analyzed. Computational experiments on a wide range of problem settings, Liu (2008) and

The work of Defersha (2011) was motivated by the gap perceived in research efforts in pure flow shop lot streaming and HFS scheduling. However, the issue of lot streaming in this

at a time. Each sublot can be processed on at most one machine at any time.

sequence the sublots on the stage-2 machine in the order of their numbers.

schedule given by the rotation method is characterized by the following features:

1 machine processes at least ⎣*l*/*m*⎦ sublots and at most ⎡ *l*/*m*⎤ sublots–;

Zhang et al. (2003) showed that the heuristic solutions are very close to optimal.

of their first-stage machine numbers.

much better.

entire job).

continuous version of the problem is studied and efficient optimal solutions to both the problem with given number of sublots and all the cases of the equal-sublot problem is provided. The continuous version does not restrict the sublot sizes to be integers. This is practical in situations where the product is of continuous type –e.g. those in process industries– and where an order consists of a large quantity of small items such as DVDs.

Manufacturing systems considered in studies by Oğuzc et al. (2004), Oğuzc & Frinket (2005) and Ying & Lin (2006) are referred as flow shop with multiprocessors (FSMP). It is a special case of HFS where the parallel machines are assumed to be identical. The overlapping of operations in parallel machines is not considered across stages. Thus, such studies may not be classified as lot streaming research as the very definition of lot streaming is to allow the overlapping of operations across stages.

Zhang et al. (2005) studied the multi-job lot streaming problem in two-stage HFS with *m*  identical machines at the first stage and a single machine at the second stage and the objective is to minimize the mean completion time of the jobs. All the *n* jobs are available at time zero. The job sizes are different. A job can be split into sublots that will be treated as separate entities in production. Each sublot requires processing on any one of the machines at the first stage and then on the machine at the second stage. It is assumed that:

There is a given smallest allowable size for the sublots of each job, from which the maximum number of sublots allowed for the job that can be derived.

The problem is then to decide the number and the sizes of sublots for each job and to schedule these sublots to minimize the mean completion time of all jobs. The completion time of a job is defined as the completion time of the last sublot of the job on the secondstage machine.

To solve this NP-hard problem, two heuristics were developed, both using the strategy of first sequencing the jobs and then lot streaming each job. The two heuristics differ in the way of sequencing the jobs. The first heuristic treats each job as a whole lot. The second heuristic considers the system as a pure flow shop with the stage-1 machines aggregated. It uses a profile of each job from the single-job lot streaming result as the time requirements in the artificial pure flow shop. When solving the lot streaming problem of each job in the sequence, both heuristics assign balanced numbers of sublots to the machines at the first stage and decide the sublot sizes using a LP model. A MILP model for the problem was also formulated and used to obtain a lower bound through relaxation. The lower bound was 80 Production Scheduling

continuous version of the problem is studied and efficient optimal solutions to both the problem with given number of sublots and all the cases of the equal-sublot problem is provided. The continuous version does not restrict the sublot sizes to be integers. This is practical in situations where the product is of continuous type –e.g. those in process industries– and where an order consists of a large quantity of small items such as DVDs.

Manufacturing systems considered in studies by Oğuzc et al. (2004), Oğuzc & Frinket (2005) and Ying & Lin (2006) are referred as flow shop with multiprocessors (FSMP). It is a special case of HFS where the parallel machines are assumed to be identical. The overlapping of operations in parallel machines is not considered across stages. Thus, such studies may not be classified as lot streaming research as the very definition of lot streaming is to allow the

Zhang et al. (2005) studied the multi-job lot streaming problem in two-stage HFS with *m*  identical machines at the first stage and a single machine at the second stage and the objective is to minimize the mean completion time of the jobs. All the *n* jobs are available at time zero. The job sizes are different. A job can be split into sublots that will be treated as separate entities in production. Each sublot requires processing on any one of the machines

There is a given smallest allowable size for the sublots of each job, from which the

4. A job can be continuously divisible. As the number of units in ajob is very large, the error between the objective value of the rounded solution and that of the continuous

5. The jobs are processed one after another, i.e. the sublots of different jobs are not mixed

6. A setup is needed before the processing of each sublot of a job on a machine. The setup

The problem is then to decide the number and the sizes of sublots for each job and to schedule these sublots to minimize the mean completion time of all jobs. The completion time of a job is defined as the completion time of the last sublot of the job on the second-

To solve this NP-hard problem, two heuristics were developed, both using the strategy of first sequencing the jobs and then lot streaming each job. The two heuristics differ in the way of sequencing the jobs. The first heuristic treats each job as a whole lot. The second heuristic considers the system as a pure flow shop with the stage-1 machines aggregated. It uses a profile of each job from the single-job lot streaming result as the time requirements in the artificial pure flow shop. When solving the lot streaming problem of each job in the sequence, both heuristics assign balanced numbers of sublots to the machines at the first stage and decide the sublot sizes using a LP model. A MILP model for the problem was also formulated and used to obtain a lower bound through relaxation. The lower bound was

at the first stage and then on the machine at the second stage. It is assumed that:

maximum number of sublots allowed for the job that can be derived.

2. Each sublot can be processed on at most one machine at a time. 3. The size of each sublot is kept consistent at the two stages.

times for sublots of the same job at the same stage are equal. 7. The unit processing times and the setup times are known constants.

1. Each machine can process at most one sublot at a time.

up in the sequence of processing on any machine.

overlapping of operations across stages.

solution may be negligible.

stage machine.

used jointly with two other lower bounds obtained from the direct analysis of the problem structure. Extensive experiments showed that the aggregated machine heuristic performs much better.

Liu (2008) studied the single-job lot streaming problem in a two-stage HFS that has *m* identical machines at the first stage and one machine at the second stage, called *m*-1 HFS, the same machine environment that in Zhang et al. (2005). The job is splitted into sublots. It is not necessary for the sizes of the sublots to be equal or to be integers, but they must not be smaller than a lower bound, x0 ≥ 0. A sublot will be treated as an independent entity during the production in the system. Each sublot requires processing on anyone of the machines at the first stage and then on the machine at the second stage. The processing times of a sublot at the two stages are proportional to its size. The unit processing times on the stage-1 and stage-2 machines are *p*(1) and *p*(2), respectively. Each machine can process at most one sublot at a time. Each sublot can be processed on at most one machine at any time.

Before the processing of each sublot on a machine, a setup time is required for loading the sublot onto the machine. The setup times on the machines of stages 1 and 2 are *s*(1) and *s*(2), respectively, which are independent of the processing sequence and the sizes of the sublots. The problem is to determine the number and the sizes of the sublots and the schedule of processing them on the machines to minimize the makespan (the completion time of the entire job).

For the problem with a fixed number of sublots, Liu (2008) proved that it is optimal to use a rotation method for allocating and sequencing the sublots on the machines previously used by Zhang et al. (2003): First, number the sublots is 1, 2, . . ., *l*. Then, allocate and sequence these sublots on the stage-1 machines in ''rotation'', i.e. assign sublot 1 to machine 1, sublot 2 to machine 2, ..., sublot *m* to machine *m*, sublot *m* + 1 to machine 1, and so on. Finally, sequence the sublots on the stage-2 machine in the order of their numbers.

Hereafter it is referred to the first sublots on the first-stage machines as the first batch of sublots, to the second sublots on these machines as the second batch, and so on. The schedule given by the rotation method is characterized by the following features:

When the sublots are allocated using the rotation method, the only remaining decision is to determine the sizes of the sublots. As all the discrete decisions are fixed, the problem of determining the sublot sizes can be formulated as a LP model. Then the problem with equal sublot sizes is considered and an efficient solution to determining the optimal number of sublots is developed. Finally, optimal and heuristic solution methods for the general problem are proposed and the worst-case performance of the equal-sublot solution is analyzed. Computational experiments on a wide range of problem settings, Liu (2008) and Zhang et al. (2003) showed that the heuristic solutions are very close to optimal.

The work of Defersha (2011) was motivated by the gap perceived in research efforts in pure flow shop lot streaming and HFS scheduling. However, the issue of lot streaming in this

Lot Processing in Hybrid Flow Shop Scheduling Problem 83

classification machine measures the value of each piece and deposits it into one of 25 machine repositories according to the value range. Four tube glass types are used in the plant. One lot has a fixed amount of the pieces with the same tube glass type. When a machine starts processing, does not interrupt up to finishing lot. One lot does not divided between machines. There is a list of part numbers. A part number indicates several numbers of repositories so as the same repository can be included in different part numbers. After the classification, a lot is distributed between repositories and then the product is treated in pieces. The content of repositories is assigned on one of four blade form lines taking in account part number and the demand amounts. The rest of pieces not reclaimed for demands forms WIP inventory. The

investigated resource model is presented on Figure 2.

1

...

*m*

The information complexity causes numerous problems in the production planning and scheduling of the plant because they are realized empirically, based on previous experience,

According to the previous experience on the plant, the tube glass type has influence on the distribution of pieces between machine repositories. In (Romero & Burtseva, 2010) is shown that the distribution of pieces belonged to one lot has central tendencies specific for each glass type, and those empirical distributions trend to be near-normal (Fig. 3). A deterministic approach is used here to analyze and resolve the problem, i.e., all distributions are supposed to be known and fixed for each glass type, so as the content of a repository can

*f*

Fig. 3. The probability density functions *f*(*x*) of the distributions of the pieces between

3

*f*

*x*

Fig. 2. The *m* identical classification machines and four blade form lines.

and therefore suffer from stochastic results of the lot processing.

**5.2 Problem statement**

0.04 0.08

0

*f* (*x*)

be anticipatory assigned to a demand.

repositories for different lot glass types.

*f f*

1 2

0.12 4

type of shops has not gained as much attention as for pure flow shop scheduling. Defersha (2011) refers to the work of Zhang et al. (2005) as the only paper that addressed lot streaming in HFS. However, this work is for a very special case where there are parallel machines only in the first stage and the number of stages is limited to two. Lot streaming in a more general HFS with parallel machines on any stage and the number of stages is not limited to two has been studied implicitly and partially.

This chapter is aimed to research in bridging the gap between the efforts in pure flow shop lot streaming and HFS scheduling by presenting a comprehensive mathematical model for lot streaming addressing to the work of Ruiz et al. (2008) which considers the overlapping operations in successive stage through the concept of negative time-lag. This mathematical model incorporates several other practical issues such as unrelated parallel machines, the possibility of certain jobs to skip certain stages, sequence-dependent setup times, anticipatory or non-anticipatory nature of setups, release dates for machines, and machine eligibility. The sublots are to be processed in the order of the stages and sublots of certain products may skip some stages. At a given stage, a sublot of a job can be assigned to one of the parallel machines eligible to process that particular job. For each job there is a sequence dependent setup time on each eligible machine and this setup may be anticipatory or nonanticipatory on different stages. Each machine can process at most one sublot at a time. Sublots of different products can be interleaved. The problem is to determine the size of each sublot of each job, the assignment and processing sequence of these sublots on each machine in each stage. The objective is to minimize the completion time of the last sublot to be processed in the system. The proposed model was solved to optimality for small problem size. The numerical example shown in this referenced paper demonstrated that lot streaming can result in larger makespan reduction in HFS where there is a limited research than in pure flow shop where research is abundant.

#### **5. A problem of demand splitting in a two-stage HFS with lot processing**

In this section, an exercise of application of the concepts described trough the section is shown. It consists about the analysis of a real problem settled in electronic components manufacturing; where theoretical formulations as long as modeling results are displayed.

#### **5.1 Production model**

The production model is set in reed switch manufacturing. Reed switches are used in electric sensors and relays. The components of a reed switch are two metallic contact blades (reeds) positioned in a hermetically sealed glass tube with a gap between them. The production planning on the plant is realized per lots for a planning horizon, according to the consumer's demands. A demand includes an accepted range of switch operate value named part number, a form of blades, an amount of pieces, a delivery date and needs several lots to be completed.

The technical route of the switch manufacturing is composed of several successive operations divided on a natural manner in two parts with an external operation of one day duration. The investigation is focused on the second part where the presented problem occurs: the classification of pieces and the blade form. The classification operation is realized per lots on one of the group of parallel identical machines, so as one lot is assigned a one of machines. The 82 Production Scheduling

type of shops has not gained as much attention as for pure flow shop scheduling. Defersha (2011) refers to the work of Zhang et al. (2005) as the only paper that addressed lot streaming in HFS. However, this work is for a very special case where there are parallel machines only in the first stage and the number of stages is limited to two. Lot streaming in a more general HFS with parallel machines on any stage and the number of stages is not

This chapter is aimed to research in bridging the gap between the efforts in pure flow shop lot streaming and HFS scheduling by presenting a comprehensive mathematical model for lot streaming addressing to the work of Ruiz et al. (2008) which considers the overlapping operations in successive stage through the concept of negative time-lag. This mathematical model incorporates several other practical issues such as unrelated parallel machines, the possibility of certain jobs to skip certain stages, sequence-dependent setup times, anticipatory or non-anticipatory nature of setups, release dates for machines, and machine eligibility. The sublots are to be processed in the order of the stages and sublots of certain products may skip some stages. At a given stage, a sublot of a job can be assigned to one of the parallel machines eligible to process that particular job. For each job there is a sequence dependent setup time on each eligible machine and this setup may be anticipatory or nonanticipatory on different stages. Each machine can process at most one sublot at a time. Sublots of different products can be interleaved. The problem is to determine the size of each sublot of each job, the assignment and processing sequence of these sublots on each machine in each stage. The objective is to minimize the completion time of the last sublot to be processed in the system. The proposed model was solved to optimality for small problem size. The numerical example shown in this referenced paper demonstrated that lot streaming can result in larger makespan reduction in HFS where there is a limited research

**5. A problem of demand splitting in a two-stage HFS with lot processing**

In this section, an exercise of application of the concepts described trough the section is shown. It consists about the analysis of a real problem settled in electronic components manufacturing; where theoretical formulations as long as modeling results are displayed.

The production model is set in reed switch manufacturing. Reed switches are used in electric sensors and relays. The components of a reed switch are two metallic contact blades (reeds) positioned in a hermetically sealed glass tube with a gap between them. The production planning on the plant is realized per lots for a planning horizon, according to the consumer's demands. A demand includes an accepted range of switch operate value named part number, a form of blades, an amount of pieces, a delivery date and needs several lots to

The technical route of the switch manufacturing is composed of several successive operations divided on a natural manner in two parts with an external operation of one day duration. The investigation is focused on the second part where the presented problem occurs: the classification of pieces and the blade form. The classification operation is realized per lots on one of the group of parallel identical machines, so as one lot is assigned a one of machines. The

limited to two has been studied implicitly and partially.

than in pure flow shop where research is abundant.

**5.1 Production model**

be completed.

classification machine measures the value of each piece and deposits it into one of 25 machine repositories according to the value range. Four tube glass types are used in the plant. One lot has a fixed amount of the pieces with the same tube glass type. When a machine starts processing, does not interrupt up to finishing lot. One lot does not divided between machines. There is a list of part numbers. A part number indicates several numbers of repositories so as the same repository can be included in different part numbers. After the classification, a lot is distributed between repositories and then the product is treated in pieces. The content of repositories is assigned on one of four blade form lines taking in account part number and the demand amounts. The rest of pieces not reclaimed for demands forms WIP inventory. The investigated resource model is presented on Figure 2.

Fig. 2. The *m* identical classification machines and four blade form lines.

The information complexity causes numerous problems in the production planning and scheduling of the plant because they are realized empirically, based on previous experience, and therefore suffer from stochastic results of the lot processing.

#### **5.2 Problem statement**

According to the previous experience on the plant, the tube glass type has influence on the distribution of pieces between machine repositories. In (Romero & Burtseva, 2010) is shown that the distribution of pieces belonged to one lot has central tendencies specific for each glass type, and those empirical distributions trend to be near-normal (Fig. 3). A deterministic approach is used here to analyze and resolve the problem, i.e., all distributions are supposed to be known and fixed for each glass type, so as the content of a repository can be anticipatory assigned to a demand.

Fig. 3. The probability density functions *f*(*x*) of the distributions of the pieces between repositories for different lot glass types.

Lot Processing in Hybrid Flow Shop Scheduling Problem 85

*O* =[*ojr*] Utilization of repository *r* in the job *j*(part number, *N* chains of *R* bits), *Oj* = {*oj*1,…,

• The lots of all types are available at time zero. The size of any lot is *U* pieces and its processing time is fixed to be *p*(1). A setup time needed for lot allocating on a machine is included in the lot processing time. The lot selected to processing is identified completely by its glass type *g*. One lot does not divide between machines. When a

• The lot *l* can be assigned to any of *m*1 parallel identical machines on the first stage, and next lot is assigned to a machine immediately after finishing of the previous lot. The occupied machines start and finish together. Each machine of the first stage can process

• After first stage, the lot of type *g* is distributed between *R* machine repositories according to the row *g* of the matrix *K =* [*kgr*]; that is, one lot splits into *R* machine

• The sublots of size *dlrj*, *l* = 1, 2,…, *L*, *r =* 1,…, *R*, *j* = 1,…, *N* , are formed using repository contents. A sublot can be formed from only one repository. The content of one

• The pieces that were not assigned to any job are not used and form the WIP. The WIP

• The sublots belonged to the same job *j* are joined in batches. The sublots belonged to the different jobs are not mixed. The batches are formed from sublots whose processing is

• There is a non-anticipatory sequence independent setup time sin to form the sublots from the repository contents and the batches of sublots belonged to the same job to be

• Each machine of the second stage processes at most one batch at a time. The idle time between batches are permitted on a machine. When a dedicate machine begins

*K* = [*kgr*] Matrix of distributions of pieces for a lot of type *g* into machine repositories *r*.

**5.3 Notations**

*j* Demand index, *j =* 1,…, *N*. *J* Demand list, *J* = {*j*1, *j*2,…, *jN*}

*g* Lot type, *g* = 1,…,*G*. *l* Lot index, *l =* 1,…, *L*.

*Dj* Size of demand *j*.

*L* Quantity of lots.

*dlrj* Size of sublot *slrj*.

**5.4 Problem assumptions**

at most one lot at time.

processed on the second stage.

repositories.

*U* Lot size.

*ojR*}.

*r* Machine repository index, *r* = 1,…, *R.*

*Vj* Set of repositories associated with job *j*.

*M*1 Set of machines at the first stage, *M*1 = {1,…, *m*1} *M*2 Set of machines at the second stage, *M*2 = {1,…, *m*2}

*A* Resulted lot list, *A =* {*g*1, *g*2,…, *gl*,…, *gL*}, *gl* ∈{1,…,*G*}.

machine begins lot processing does not stop until finish.

repository can be used for one o more sublots.

processing of a batch does not stop until finish.

content is considered to be used on future demands.

assigned to the same dedicated machine of the second stage.

The follow reasons cause the problem complexity. The quantity of lots for the completion of demands depends essentially on the selection of the glass type of the pieces in the lot in consequence of differences of distributions. Moreover, as the different part numbers often include the same repositories, the allocation of demands on repositories is not evident, e.g., demands 1 and 2 need repositories 1 and 2, and demand 3 needs repositories 2 and 3 (Fig. 4). As a result, the same quantity of pieces for the required part numbers can be obtained from different quantity of lots, and consecutively, the completion time will be different.

Fig. 4. Bipartited graph of the relationship between repositories and demands (an example).

So, the considered problem is as follows. The *n* demands must be carried out in two-stage HFS with *m*1 parallel identical machines on the first stage and *m*2 dedicated machines on the second. The first stage is realized per lots of size *U*, and the second per batches of sublots. There are *G* lot types. After first stage, a lot *l* is distributed into *R* sublots of size *kgr* according to the row *g* of the matrix *K*[*g,r*], *g* = 1,…,*G*, *r* = 1,…, *R*, i.e., the lot splitting is realized on a natural manner. The demands must be allocated per parts on lot repositories employing the binary chain *j* of *R* bits, whose *r*-element is equal 1 if the repository *r* is allowed to using for fulfillment of demand *j*, and is 0 otherwise. In result of the allocation, the sublots *slrj* are formed and assigned without mixing to one of *m*2 dedicated machines of the second stage. There are sequence independent setup times before the first stage, needed for the allocation of the lot on machine, and between the first and the second stages for the sublots rebatching. The criterion is the makespan minimum.

Using the three-field notation α|β|γ, the considered problem can be denoted as:

(1) (2) (1) (1) (1) (1) (2) (2) si max 2, , |lot ,split , , job constraints ,s ,batch | *l FH PM DM p p* = *C* . (1)

Given this situation, the optimization problem addressed in (1) is summarized as follows: The shop model represents a two-stage HFS with a set of parallel identical machines on the first stage and a set of dedicated machines on the second stage. On the first stage, there are lot processing and splitting the lots in form of distribution of pieces into the machine repositories. The lot processing time is constant for any lot. The job constraints on the first stage are mentioned as the restrictions of a job allocation on certain repositories. There is batching of sublots on the second stage. The criterion is the makespan minimum, i.e., the time when the last job is finished.

#### **5.3 Notations**

84 Production Scheduling