# Integrated Model for Capacity Planning for Manufacturing

## Transcript Of Integrated Model for Capacity Planning for Manufacturing

Integrated Model for Capacity Planning for Manufacturing Systems

Andr´es Ramos

September 1992

1 Introduction

1.1 Problem framework

In general, manufacturing production lines can be classiﬁed as:

• job shops These lines are characterized by production of complex elements requiring numerous operations to be performed. Elements are made in very small series and manufacturing time can be around a month. For example, a high voltage transformer or a thermal generator. The emphasis of these lines is on coordination and scheduling of the diﬀerent operations.

• continuous production lines These lines are characterized by production of simple elements requiring few operations. The elements are made in big amounts and manufacturing time can be around one minute. As an example, we can think of bolts. The emphasis of these lines is on throughput and in-process inventory.

• ﬂexible manufacturing systems (FMS) These lines lie in between the other two. They produce a variety of elements but in small quantities. These are intermittent production systems with the following characteristics: batch production, many products which share the workstations, products relative short-lived and uncertain demand. As an example, the High Mix Low Volume Production Line at the Hewlett-Packard facility in Puerto Rico [27] produces around 30 diﬀerent board types at a rate of 250 boards per day. The production mix ranges from 1 to 1500 board per month depending on the type. The typical time in system is 2 hours. In these lines the emphasis is on minimizing the makespan (i.e., the time to achieve the prescribed orders) and other desirable attributes are minimize the diﬀerence with respect to due delivery dates, in-process inventory, machine and personnel utilization. Also it is a ﬂow shop type because products are moving in a uniform direction. Each operation is done just by one machine/operator (there are few exceptions). There is no machines in parallel although there are shortcuts in the line because certain operations are not needed for any type of product.

1

1 INTRODUCTION

2

The present model is aimed at solving the capacity planning of ﬂexible manufacturing systems.

An integrated capacity planning model has to implement the diﬀerent type of decisions addressed in manufacturing systems, borrowed from [15]:

• strategic planning Process of deciding the resources used to attain the objectives of a manufacturing facility, policies governing the acquisition, use and disposition of these resources.

• tactical planning Eﬃcient allocation of the available resources (e.g., machines, work force).

• operations control Process of assuring that the speciﬁc tasks are carried out eﬀectively and eﬃciently.

Moreover, this classiﬁcation tries to match functions and people responsible for taking these decisions.

One has to include the complex interactions among decision levels while keeping a balance and coordination in modeling aspects in order to achieve minimum costs. Thus, an integrated approach is needed if one wants to avoid the problems of suboptimization. This approach suggests a hierarchical model linking all the decision levels in an eﬀective manner. Decisions made at higher levels provide constraints for lower ones. While, detailed results provide the necessary feedback to evaluate upper level decisions. Because a capacity planning model is concentrated in solving the upper level decisions it will be necessary to simplify the lower levels while keeping their main implications.

The application of the previous three levels to decisions taken inside a manufacturing facility, where the examples shown below have been taken from an electronic memory board production line described in [27], will result in:

• capacity planning (facility design) decisions. Type of decisions addressed:

– updating or replacement of existing equipment (stencil printer, infrared soldering) during or after its useful life

– acquisition of new equipment – location and size (discrete by nature) of inventory buﬀers – replacement of support equipment (AGV, conveyors) – acquisition of new support equipment – equipment speciﬁcation – reinforcement of the human activity (inspection personnel) – new conﬁguration or layout of equipment

1 INTRODUCTION

3

These decisions allow the ﬁrm to maintain their competitive capabilities. The driving forces for these decisions can be: increment in demand causing investments in new faster and more reliable machines, new type of products requiring new production technologies.

A capacity planning proposal will be a combination of the above decisions and can be modeled as substitution of old activities by new ones. Decisions are discrete (number of machines to instal) or continuous (processing speed) involving diﬀerent equipment speciﬁcations for a production line.

Consequences: negotiating purchasing agreements with equipment manufacturers, new capital requirements (land, building, labor, machines).

• production scheduling decisions.

The importance of the production scheduling function is related to the type of line and parts produced. This function can be less relevant if products are similar and a great amount of them are produced in one time period or can be important when existing interdependence among products (like in the case of sequence-dependent setup times).

Besides, this decision level is specially required when appearing highly uncertain future demand where previous scheduling patterns are ever repeated.

A master production scheduling plan controls and organizes the line operations after evaluating and deciding diﬀerent policies (decisions) for dispatching orders to the shop ﬂoor: choosing batch sizes, designing rules for moving parts, sequencing of parts through the system. A schedule or plan is an ordering of the products and operations onto machines subject to priorities and routing relationships.

Commonly used criteria for production scheduling decisions are: minimize workin-process inventory or related costs, maximize completion of the products on time or minimize penalty costs, maximize utilization of the available capacity, minimize makespan or time to complete all the prescribed products.

Consequences: delivery schedules, setup time reductions.

Uniform scheduling is common practice in just-in-time environments. It is a planning method for resource allocation based on smooth, homogenized production ﬂow, see [31]. This strategy is trying to decrease the time needed in setup changes and to maintain a constant rate in production delivery.

• operational (intermediate range planning) decisions.

Operating decisions are: priority rules changes when certain events occur at the shop ﬂoor.

An operations model reproduces the production line rules and performance giving attributes (or performance measures) such as:

– utilization of personnel and equipment

1 INTRODUCTION

4

– productivity or throughput – time in system for parts – makespan (total time needed to produce certain number of parts) – inventory in system (is proportional to the time in system for parts) – timeliness of deliveries (proportion of late orders) – times that parts spend in queues, transport, waiting for transport – product reliability and quality

Some of them can be diﬃcult to measure or quantify. Furthermore, robustness of each attribute (dependence or variance with respect to stochastic factors) for any of the capacity planning proposals should be considered.

Usually, the most important attributes are converted into costs according to some factors (e.g., penalty for deviation from a due time).

Consequences: changes in equipment design and operation, identiﬁcation of bottlenecks, product speciﬁcations.

The application of a model to a certain type of manufacturing lines conditions its design. The manufacturing lines addressed by this model are FMS.

1.2 Time frames

The useful life of the machines is up to 5-7 years, then the time frame of the investment decisions will be 1-3 years. Intrinsically, these decisions are time dependent (dynamic). One has to decide when to invest.

It is supposed that production is a continuous task that does not depend on the time (month, day) during the year. Therefore, any representative time unit (e.g., week or month) is convenient. It seems that a month is a natural time interval.

Then, the total annual demand estimate is split into monthly objectives being the production demand for each month. Monthly demand is scheduled along the month to balance production for each day and type of product. The orders are dispatched to the shop ﬂoor once a month and production begins as soon as an order arrives.

1.3 Uncertainty

One has to take decisions on new investments, replacements, process improvements that take into account and hedge against all the problem uncertainties.

On one hand, there is uncertainty in volume and mix (number) of each diﬀerent type of product (memory boards, CPUs) to be demanded during the investment time frame. Besides, there is uncertainty in the production line itself because of the many stochastic factors involved in (equipment failure, human behavior). These uncertainties are considered within the model. In other planning environments (e.g., electric power systems planning) the optimization process can take into account both stochasticities. However,

2 FORMULATION

5

in the present model the last factors are considered into the operations model, while demand uncertainty is considered in an upper level. Synthetic demand series could be used to include the variation of the demand along the time horizon, obtained from previous demand patterns or from predictions about future evolution.

On the other hand, uncertainties associated with cost, reliability or delivery time of new equipment are also considered in the upper level.

2 Formulation

1. Investment decision variables (machine of certain type, certain inspection position, new layout). Using the simulation terminology they would be number of servers (machines, people) in each workstation (machine type, human activity). X are by nature integer, convertible to 0/1 variables.

X = {xit}

(1)

i index of the investment variables. i = 1, . . . , I t index of the time periods. t = 1, . . . , T

2. Attributes of each investment decision (equipment costs, labor costs, building or land costs).

C = {ci}

(2)

3. Attributes of the investment plan.

F = {fk}

(3)

k index of the investment plan attributes. k = 1, . . . , K

4. Speciﬁcations for the production line derived from investment decisions (characteristics of the new machine in speed, throughput, availability, percentage of error). They are a linear function of X.

E = {em}

(4)

m index of the speciﬁcations. m = 1, . . . , M

5. Future demands of each type of product over the planning horizon in each time period. They are stochastic.

Dω = {dωt }, ω ∈ Ω

(5)

2 FORMULATION

6

6. Random factors aﬀecting production line operations (equipment failure, human behavior).

Rω = {rω}, ω ∈ Ω

(6)

7. Production line decision variables.

Y = {yjt}

(7)

j index of the production line decision variables. j = 1, . . . , J

8. Attributes of the production line operation (utilization of equipment and personnel, time in system, time to achieve the orders).

V = {vlt}

(8)

l index of the production line attributes. l = 1, . . . , L

The global objective function is:

min g(F, V )

(9)

and it can be: monoattribute, multiattribute weighted to form a single attribute, multiattribute not weighted treated akin to goal programming. See in [6, 10] diﬀerent techniques used for multicriteria optimization.

Usually, the global objective function will be total cost (investment plus operating costs). If only investment cost were considered, then K = 1, and if they were linear with respect to the investment variables

TI

F=

cixit

t=1 i=1

(10)

Operating costs ought to be obtained from production line attributes. The computation of the production line attributes V from their inputs E, D, and R (some of them are stochastic) and from their decision variables Y is done by simulation, necessary when no other analytical or optimization techniques can be applied to represent the complexity involved in the production line. The randomness included in R (for each scenario of demand D) is considered by repeating the simulation until a conﬁdence interval small enough is reached. The minimum value of the attributes V are obtained by a simulation optimization process (see section 5).

We are interested in mean values of the attributes over the diﬀerent stochastic factors aﬀecting the manufacturing process.

V ω ω = f (E, Dω , Rω, Y )

(11)

3 INVESTMENT OPTIMIZATION

7

V¯ ω = EωV ω ω

(12)

Vˆ = Eω V ω

(13)

Eω expected value in the Ω probability space. Eω expected value in the Ω probability space.

Restrictions can aﬀect investment variables (e.g., maximum investment, labor constraints) and will be deterministic. Also, there can be constraints associated with production line operations. Firstly, those aﬀecting operating decisions will be deterministic and explicit (they can be considered prior the simulation and deﬁne a feasible experimental region). And secondly, those aﬀecting operational attributes (e.g., maximum percentage of late orders, unacceptance of certain throughput of the production line, certain standard variation in an attribute) will be probabilistic and implicit (they require the simulation to be done).

From other point of view, the constraints can be monoperiod or multiperiod, according to the number of periods aﬀected. Naturally, the later are much more involving because they make interdependent all the periods and have to be included at the capacity planning level.

3 Investment Optimization

The solution method has to deal with the relation between investment and operational decisions and involves stochastic optimization. How can we ‘organize’ the global attributes computation to achieve the optimal investment plan?

Few references have been found on this topic. Possible methods are:

1. Nested decomposition

The diﬃculty of this method is the computation of the dual variables of the operation subproblem with respect to the investment decisions. See an application of Benders decomposition in [9].

The only way to obtain derivatives for the production line we are dealing with is by inﬁnitesimal ﬁnite diﬀerences. They are meaningful in the case of buﬀer capacities (if the buﬀer capacities are big enough to be thought as continuous) but meaningless in the case of machines and operators.

Besides, one has to demonstrate or assume the convexity of the production problem.

2. Combinatorial-enumeration

The number of possible solutions and their combinations have to be small enough to be calculated, see [14] as an example. Small examples allow this type of solution.

4 PRODUCTION SCHEDULING OPTIMIZATION

8

3. Guided heuristic search Which are the criteria that could be used to guide the search of solutions?

A totally diﬀerent approach to the investment optimization process known as ﬁnancial simulation has been found in [23].

4 Production Scheduling Optimization

A basic algorithm is needed to obtain a master production scheduling plan. This algorithm should capture the eﬀects in the line derived from the investment decisions.

The combinatorial nature of the problem directs the eﬀort to ﬁnd good feasible schedules, rather than ﬁnd optimality. Heuristics approaches are the most promising, see for example [2].

Recent surveys on production scheduling and lot-sizing are found in [26, 4].

5 Operations Optimization

How can we get an optimal production plan with a simulation model? We have a combinatorial, discrete, multivariate stochastic optimization called simulation optimization. Running the simulation model we can obtain conclusions about:

• what parameters are most sensitive, where and how do they aﬀect the performance of the line?

• what are the changes in the line performance measures with respect to the parameters?

• which are the possible actions to improve the performance?

From a knowledge of the line (by the local expertise) and using of a simulation model the parameters that are decision variables in the production line optimization process are identiﬁed.

The simulation model requires an optimization process for the current activities of the plant. A change produced in an activity of the production line (replacement of a machine, introduction of another person in certain inspection position) will require the adjustment in the operations decisions that otherwise would mask the eﬀects of the changes proposed.

Two main diﬃculties arise associated with simulation optimization. Firstly, the objective function is not analytical, then classical nonlinear programming techniques are not applicable in strictu sensu. And secondly, the objective function (attributes) is stochastic and the criteria used to improve the solution have to be aware of that, specially those regarding the evaluation and convergence properties of the algorithms.

5 OPERATIONS OPTIMIZATION

9

5.1 Statistical comparison of attributes and constraints

Attributes are uncertain due to stochastic factors aﬀecting production line performance and constraints can also be stochastic. The simulation is replicated until the conﬁdence intervals for the attributes of interest are small enough (see [18, 24]). Mean and variance of the attributes are used to draw inferences about the performance of a system operation compared to another. Statistical procedures or decision criteria are applied to ensure improvement of a solution with respect to another or to test the violation of the constraints in the optimization process, see references [3, 18, 22].

In [18] a modiﬁed two-sample-t conﬁdence interval is shown for comparing two independent operation points with unequal and unknown variances. After obtaining mean and variance for each one the estimated degrees of freedom fˆ are computed

fˆ =

SA2 (nA)/nA + SB2 (nB)/nB 2

(14)

SA2 (nA)/nA 2 /(nA − 1) + SB2 (nB)/nB 2 /(nB − 1)

X¯A(nA) sample mean at point A with nA observations. SA2 (nA) sample variance at point A with nA observations.

and the equation

X¯A(nA) − X¯B(nB) ± tfˆ,1−α/2

SA2 (nA) + SB2 (nB)

nA

nB

(15)

is used as the 100(1 − α)% conﬁdence interval of the diﬀerence. If the interval does not include the 0, we can say that A diﬀers from B with a 100(1 − α)% conﬁdence level and that one is superior to the other depending of the interval position. A similar approach is found in [22].

In [3] an heuristic technique is found. When the upper limit of a conﬁdence interval of an attribute is less than the lower limit of another, then a conclusive decision is taken: the ﬁrst solution is better than the second if we are minimizing. If this conclusion can not be reached the simulation replication is extended to decrease the conﬁdence interval width for the second solution until a maximum number of replications.

Analogously, the constraints should be satisﬁed with a certain conﬁdence level. That means that the upper (lower) limit of the conﬁdence interval of the left hand side should be less or equal (greater or equal) than the right hand side in less or equal (greater or equal) constraints.

5.2 Simulation optimization techniques

Mathematically the simulation optimization problem can be expressed as:

min V¯ ω

(16)

subject to: gp(Y ) = G, p = 1, . . . , P

5 OPERATIONS OPTIMIZATION

10

References [12, 17] present surveys of the methods used in simulation optimization. Particular applications to manufacturing systems are presented in references [3, 6, 8, 20, 22, 30] although with simple examples. Moreover, some include capacity planning decisions in the simulation optimization process.

Techniques used to ﬁnd local or global optima for discrete-event simulations, according to reference [17], can be classiﬁed in:

1. pattern search methods

These methods work with nonconvex, nonconcave objective functions, do not need continuity in decision variables and attributes and only use speciﬁc function values, no derivatives. They can be applied to constrained as well as unconstrained problems.

In general, these methods make rapid early progress toward the optimum but iterate close to the ﬁnal solution. The search procedures are very simple and could be easily implemented in a parallel computer.

• modiﬁed Hooke-Jeeves (see [22]) The method performs two types of search routines cyclically: an exploratory search and a pattern search. The exploratory search is conducted along the individual coordinate directions in the neighborhood of a reference point to ﬁnd the search path. The pattern search proceeds along the direction deﬁned by the starting and ending points of the exploratory search.

• simplex procedure, Nelder-Mead simplex, constrained simplex (complex) (see [3, 5, 6]) Randomly or uniformly spread generate a set of points forming a simplex satisfying the explicit constraints. Perform a simulation for each point and evaluate the attributes. Eliminate the points violating the implicit constraints. Evaluate the objective function. Find the worst point. Obtain the centroid of the remaining. Determine a new point image of the worst with respect to the centroid. Perform the simulation at this new point and iterates until no further improvement is achieved. Through this process, the simplex moves around in the feasible region while vertices get closer to each other until they collapse in the optimum. In the complex search special eﬀort is made to prevent the simplex from leaving the feasible region.

2. path search methods

They involve estimating a direction to move from a current variable set to an improved point in the feasible variable set. Only local information is used. Once a direction is found, a distance to move in that direction is determined.

Typically, these methods assume that decision variables and attributes are continuous. Assumption not necessary in pattern search methods.

Andr´es Ramos

September 1992

1 Introduction

1.1 Problem framework

In general, manufacturing production lines can be classiﬁed as:

• job shops These lines are characterized by production of complex elements requiring numerous operations to be performed. Elements are made in very small series and manufacturing time can be around a month. For example, a high voltage transformer or a thermal generator. The emphasis of these lines is on coordination and scheduling of the diﬀerent operations.

• continuous production lines These lines are characterized by production of simple elements requiring few operations. The elements are made in big amounts and manufacturing time can be around one minute. As an example, we can think of bolts. The emphasis of these lines is on throughput and in-process inventory.

• ﬂexible manufacturing systems (FMS) These lines lie in between the other two. They produce a variety of elements but in small quantities. These are intermittent production systems with the following characteristics: batch production, many products which share the workstations, products relative short-lived and uncertain demand. As an example, the High Mix Low Volume Production Line at the Hewlett-Packard facility in Puerto Rico [27] produces around 30 diﬀerent board types at a rate of 250 boards per day. The production mix ranges from 1 to 1500 board per month depending on the type. The typical time in system is 2 hours. In these lines the emphasis is on minimizing the makespan (i.e., the time to achieve the prescribed orders) and other desirable attributes are minimize the diﬀerence with respect to due delivery dates, in-process inventory, machine and personnel utilization. Also it is a ﬂow shop type because products are moving in a uniform direction. Each operation is done just by one machine/operator (there are few exceptions). There is no machines in parallel although there are shortcuts in the line because certain operations are not needed for any type of product.

1

1 INTRODUCTION

2

The present model is aimed at solving the capacity planning of ﬂexible manufacturing systems.

An integrated capacity planning model has to implement the diﬀerent type of decisions addressed in manufacturing systems, borrowed from [15]:

• strategic planning Process of deciding the resources used to attain the objectives of a manufacturing facility, policies governing the acquisition, use and disposition of these resources.

• tactical planning Eﬃcient allocation of the available resources (e.g., machines, work force).

• operations control Process of assuring that the speciﬁc tasks are carried out eﬀectively and eﬃciently.

Moreover, this classiﬁcation tries to match functions and people responsible for taking these decisions.

One has to include the complex interactions among decision levels while keeping a balance and coordination in modeling aspects in order to achieve minimum costs. Thus, an integrated approach is needed if one wants to avoid the problems of suboptimization. This approach suggests a hierarchical model linking all the decision levels in an eﬀective manner. Decisions made at higher levels provide constraints for lower ones. While, detailed results provide the necessary feedback to evaluate upper level decisions. Because a capacity planning model is concentrated in solving the upper level decisions it will be necessary to simplify the lower levels while keeping their main implications.

The application of the previous three levels to decisions taken inside a manufacturing facility, where the examples shown below have been taken from an electronic memory board production line described in [27], will result in:

• capacity planning (facility design) decisions. Type of decisions addressed:

– updating or replacement of existing equipment (stencil printer, infrared soldering) during or after its useful life

– acquisition of new equipment – location and size (discrete by nature) of inventory buﬀers – replacement of support equipment (AGV, conveyors) – acquisition of new support equipment – equipment speciﬁcation – reinforcement of the human activity (inspection personnel) – new conﬁguration or layout of equipment

1 INTRODUCTION

3

These decisions allow the ﬁrm to maintain their competitive capabilities. The driving forces for these decisions can be: increment in demand causing investments in new faster and more reliable machines, new type of products requiring new production technologies.

A capacity planning proposal will be a combination of the above decisions and can be modeled as substitution of old activities by new ones. Decisions are discrete (number of machines to instal) or continuous (processing speed) involving diﬀerent equipment speciﬁcations for a production line.

Consequences: negotiating purchasing agreements with equipment manufacturers, new capital requirements (land, building, labor, machines).

• production scheduling decisions.

The importance of the production scheduling function is related to the type of line and parts produced. This function can be less relevant if products are similar and a great amount of them are produced in one time period or can be important when existing interdependence among products (like in the case of sequence-dependent setup times).

Besides, this decision level is specially required when appearing highly uncertain future demand where previous scheduling patterns are ever repeated.

A master production scheduling plan controls and organizes the line operations after evaluating and deciding diﬀerent policies (decisions) for dispatching orders to the shop ﬂoor: choosing batch sizes, designing rules for moving parts, sequencing of parts through the system. A schedule or plan is an ordering of the products and operations onto machines subject to priorities and routing relationships.

Commonly used criteria for production scheduling decisions are: minimize workin-process inventory or related costs, maximize completion of the products on time or minimize penalty costs, maximize utilization of the available capacity, minimize makespan or time to complete all the prescribed products.

Consequences: delivery schedules, setup time reductions.

Uniform scheduling is common practice in just-in-time environments. It is a planning method for resource allocation based on smooth, homogenized production ﬂow, see [31]. This strategy is trying to decrease the time needed in setup changes and to maintain a constant rate in production delivery.

• operational (intermediate range planning) decisions.

Operating decisions are: priority rules changes when certain events occur at the shop ﬂoor.

An operations model reproduces the production line rules and performance giving attributes (or performance measures) such as:

– utilization of personnel and equipment

1 INTRODUCTION

4

– productivity or throughput – time in system for parts – makespan (total time needed to produce certain number of parts) – inventory in system (is proportional to the time in system for parts) – timeliness of deliveries (proportion of late orders) – times that parts spend in queues, transport, waiting for transport – product reliability and quality

Some of them can be diﬃcult to measure or quantify. Furthermore, robustness of each attribute (dependence or variance with respect to stochastic factors) for any of the capacity planning proposals should be considered.

Usually, the most important attributes are converted into costs according to some factors (e.g., penalty for deviation from a due time).

Consequences: changes in equipment design and operation, identiﬁcation of bottlenecks, product speciﬁcations.

The application of a model to a certain type of manufacturing lines conditions its design. The manufacturing lines addressed by this model are FMS.

1.2 Time frames

The useful life of the machines is up to 5-7 years, then the time frame of the investment decisions will be 1-3 years. Intrinsically, these decisions are time dependent (dynamic). One has to decide when to invest.

It is supposed that production is a continuous task that does not depend on the time (month, day) during the year. Therefore, any representative time unit (e.g., week or month) is convenient. It seems that a month is a natural time interval.

Then, the total annual demand estimate is split into monthly objectives being the production demand for each month. Monthly demand is scheduled along the month to balance production for each day and type of product. The orders are dispatched to the shop ﬂoor once a month and production begins as soon as an order arrives.

1.3 Uncertainty

One has to take decisions on new investments, replacements, process improvements that take into account and hedge against all the problem uncertainties.

On one hand, there is uncertainty in volume and mix (number) of each diﬀerent type of product (memory boards, CPUs) to be demanded during the investment time frame. Besides, there is uncertainty in the production line itself because of the many stochastic factors involved in (equipment failure, human behavior). These uncertainties are considered within the model. In other planning environments (e.g., electric power systems planning) the optimization process can take into account both stochasticities. However,

2 FORMULATION

5

in the present model the last factors are considered into the operations model, while demand uncertainty is considered in an upper level. Synthetic demand series could be used to include the variation of the demand along the time horizon, obtained from previous demand patterns or from predictions about future evolution.

On the other hand, uncertainties associated with cost, reliability or delivery time of new equipment are also considered in the upper level.

2 Formulation

1. Investment decision variables (machine of certain type, certain inspection position, new layout). Using the simulation terminology they would be number of servers (machines, people) in each workstation (machine type, human activity). X are by nature integer, convertible to 0/1 variables.

X = {xit}

(1)

i index of the investment variables. i = 1, . . . , I t index of the time periods. t = 1, . . . , T

2. Attributes of each investment decision (equipment costs, labor costs, building or land costs).

C = {ci}

(2)

3. Attributes of the investment plan.

F = {fk}

(3)

k index of the investment plan attributes. k = 1, . . . , K

4. Speciﬁcations for the production line derived from investment decisions (characteristics of the new machine in speed, throughput, availability, percentage of error). They are a linear function of X.

E = {em}

(4)

m index of the speciﬁcations. m = 1, . . . , M

5. Future demands of each type of product over the planning horizon in each time period. They are stochastic.

Dω = {dωt }, ω ∈ Ω

(5)

2 FORMULATION

6

6. Random factors aﬀecting production line operations (equipment failure, human behavior).

Rω = {rω}, ω ∈ Ω

(6)

7. Production line decision variables.

Y = {yjt}

(7)

j index of the production line decision variables. j = 1, . . . , J

8. Attributes of the production line operation (utilization of equipment and personnel, time in system, time to achieve the orders).

V = {vlt}

(8)

l index of the production line attributes. l = 1, . . . , L

The global objective function is:

min g(F, V )

(9)

and it can be: monoattribute, multiattribute weighted to form a single attribute, multiattribute not weighted treated akin to goal programming. See in [6, 10] diﬀerent techniques used for multicriteria optimization.

Usually, the global objective function will be total cost (investment plus operating costs). If only investment cost were considered, then K = 1, and if they were linear with respect to the investment variables

TI

F=

cixit

t=1 i=1

(10)

Operating costs ought to be obtained from production line attributes. The computation of the production line attributes V from their inputs E, D, and R (some of them are stochastic) and from their decision variables Y is done by simulation, necessary when no other analytical or optimization techniques can be applied to represent the complexity involved in the production line. The randomness included in R (for each scenario of demand D) is considered by repeating the simulation until a conﬁdence interval small enough is reached. The minimum value of the attributes V are obtained by a simulation optimization process (see section 5).

We are interested in mean values of the attributes over the diﬀerent stochastic factors aﬀecting the manufacturing process.

V ω ω = f (E, Dω , Rω, Y )

(11)

3 INVESTMENT OPTIMIZATION

7

V¯ ω = EωV ω ω

(12)

Vˆ = Eω V ω

(13)

Eω expected value in the Ω probability space. Eω expected value in the Ω probability space.

Restrictions can aﬀect investment variables (e.g., maximum investment, labor constraints) and will be deterministic. Also, there can be constraints associated with production line operations. Firstly, those aﬀecting operating decisions will be deterministic and explicit (they can be considered prior the simulation and deﬁne a feasible experimental region). And secondly, those aﬀecting operational attributes (e.g., maximum percentage of late orders, unacceptance of certain throughput of the production line, certain standard variation in an attribute) will be probabilistic and implicit (they require the simulation to be done).

From other point of view, the constraints can be monoperiod or multiperiod, according to the number of periods aﬀected. Naturally, the later are much more involving because they make interdependent all the periods and have to be included at the capacity planning level.

3 Investment Optimization

The solution method has to deal with the relation between investment and operational decisions and involves stochastic optimization. How can we ‘organize’ the global attributes computation to achieve the optimal investment plan?

Few references have been found on this topic. Possible methods are:

1. Nested decomposition

The diﬃculty of this method is the computation of the dual variables of the operation subproblem with respect to the investment decisions. See an application of Benders decomposition in [9].

The only way to obtain derivatives for the production line we are dealing with is by inﬁnitesimal ﬁnite diﬀerences. They are meaningful in the case of buﬀer capacities (if the buﬀer capacities are big enough to be thought as continuous) but meaningless in the case of machines and operators.

Besides, one has to demonstrate or assume the convexity of the production problem.

2. Combinatorial-enumeration

The number of possible solutions and their combinations have to be small enough to be calculated, see [14] as an example. Small examples allow this type of solution.

4 PRODUCTION SCHEDULING OPTIMIZATION

8

3. Guided heuristic search Which are the criteria that could be used to guide the search of solutions?

A totally diﬀerent approach to the investment optimization process known as ﬁnancial simulation has been found in [23].

4 Production Scheduling Optimization

A basic algorithm is needed to obtain a master production scheduling plan. This algorithm should capture the eﬀects in the line derived from the investment decisions.

The combinatorial nature of the problem directs the eﬀort to ﬁnd good feasible schedules, rather than ﬁnd optimality. Heuristics approaches are the most promising, see for example [2].

Recent surveys on production scheduling and lot-sizing are found in [26, 4].

5 Operations Optimization

How can we get an optimal production plan with a simulation model? We have a combinatorial, discrete, multivariate stochastic optimization called simulation optimization. Running the simulation model we can obtain conclusions about:

• what parameters are most sensitive, where and how do they aﬀect the performance of the line?

• what are the changes in the line performance measures with respect to the parameters?

• which are the possible actions to improve the performance?

From a knowledge of the line (by the local expertise) and using of a simulation model the parameters that are decision variables in the production line optimization process are identiﬁed.

The simulation model requires an optimization process for the current activities of the plant. A change produced in an activity of the production line (replacement of a machine, introduction of another person in certain inspection position) will require the adjustment in the operations decisions that otherwise would mask the eﬀects of the changes proposed.

Two main diﬃculties arise associated with simulation optimization. Firstly, the objective function is not analytical, then classical nonlinear programming techniques are not applicable in strictu sensu. And secondly, the objective function (attributes) is stochastic and the criteria used to improve the solution have to be aware of that, specially those regarding the evaluation and convergence properties of the algorithms.

5 OPERATIONS OPTIMIZATION

9

5.1 Statistical comparison of attributes and constraints

Attributes are uncertain due to stochastic factors aﬀecting production line performance and constraints can also be stochastic. The simulation is replicated until the conﬁdence intervals for the attributes of interest are small enough (see [18, 24]). Mean and variance of the attributes are used to draw inferences about the performance of a system operation compared to another. Statistical procedures or decision criteria are applied to ensure improvement of a solution with respect to another or to test the violation of the constraints in the optimization process, see references [3, 18, 22].

In [18] a modiﬁed two-sample-t conﬁdence interval is shown for comparing two independent operation points with unequal and unknown variances. After obtaining mean and variance for each one the estimated degrees of freedom fˆ are computed

fˆ =

SA2 (nA)/nA + SB2 (nB)/nB 2

(14)

SA2 (nA)/nA 2 /(nA − 1) + SB2 (nB)/nB 2 /(nB − 1)

X¯A(nA) sample mean at point A with nA observations. SA2 (nA) sample variance at point A with nA observations.

and the equation

X¯A(nA) − X¯B(nB) ± tfˆ,1−α/2

SA2 (nA) + SB2 (nB)

nA

nB

(15)

is used as the 100(1 − α)% conﬁdence interval of the diﬀerence. If the interval does not include the 0, we can say that A diﬀers from B with a 100(1 − α)% conﬁdence level and that one is superior to the other depending of the interval position. A similar approach is found in [22].

In [3] an heuristic technique is found. When the upper limit of a conﬁdence interval of an attribute is less than the lower limit of another, then a conclusive decision is taken: the ﬁrst solution is better than the second if we are minimizing. If this conclusion can not be reached the simulation replication is extended to decrease the conﬁdence interval width for the second solution until a maximum number of replications.

Analogously, the constraints should be satisﬁed with a certain conﬁdence level. That means that the upper (lower) limit of the conﬁdence interval of the left hand side should be less or equal (greater or equal) than the right hand side in less or equal (greater or equal) constraints.

5.2 Simulation optimization techniques

Mathematically the simulation optimization problem can be expressed as:

min V¯ ω

(16)

subject to: gp(Y ) = G, p = 1, . . . , P

5 OPERATIONS OPTIMIZATION

10

References [12, 17] present surveys of the methods used in simulation optimization. Particular applications to manufacturing systems are presented in references [3, 6, 8, 20, 22, 30] although with simple examples. Moreover, some include capacity planning decisions in the simulation optimization process.

Techniques used to ﬁnd local or global optima for discrete-event simulations, according to reference [17], can be classiﬁed in:

1. pattern search methods

These methods work with nonconvex, nonconcave objective functions, do not need continuity in decision variables and attributes and only use speciﬁc function values, no derivatives. They can be applied to constrained as well as unconstrained problems.

In general, these methods make rapid early progress toward the optimum but iterate close to the ﬁnal solution. The search procedures are very simple and could be easily implemented in a parallel computer.

• modiﬁed Hooke-Jeeves (see [22]) The method performs two types of search routines cyclically: an exploratory search and a pattern search. The exploratory search is conducted along the individual coordinate directions in the neighborhood of a reference point to ﬁnd the search path. The pattern search proceeds along the direction deﬁned by the starting and ending points of the exploratory search.

• simplex procedure, Nelder-Mead simplex, constrained simplex (complex) (see [3, 5, 6]) Randomly or uniformly spread generate a set of points forming a simplex satisfying the explicit constraints. Perform a simulation for each point and evaluate the attributes. Eliminate the points violating the implicit constraints. Evaluate the objective function. Find the worst point. Obtain the centroid of the remaining. Determine a new point image of the worst with respect to the centroid. Perform the simulation at this new point and iterates until no further improvement is achieved. Through this process, the simplex moves around in the feasible region while vertices get closer to each other until they collapse in the optimum. In the complex search special eﬀort is made to prevent the simplex from leaving the feasible region.

2. path search methods

They involve estimating a direction to move from a current variable set to an improved point in the feasible variable set. Only local information is used. Once a direction is found, a distance to move in that direction is determined.

Typically, these methods assume that decision variables and attributes are continuous. Assumption not necessary in pattern search methods.