96cec284-93b2-4c01-a9a4-b4e254431647.jpg width=142.5 height=32.1099992752075 /> (25)

(26)

Here, (12) shows the objective function: the expectation of the sum total of the preparation costs and inventory storage costs; (13) updates the changes in inventory; (14)is the constraint on the time that a machine can be used; (15) reflects that, at each time, a machine is only capable of producing one type of item; (16) is a constraint on preparation being carried out; (17) and (18) are the initial conditions for production and inventory; (19), (20), (21), and (22) are the nonanticipativity conditions; and (23), (24), (25), and (26) are additional conditions on the individual variables.

4. Applying the Scenario Aggregation Method

4.1. Equivalent Deterministic Programming Problems

The formulation of problems (not only the lot-scheduling problem on parallel machines) via a stochastic programming model such as this poses a large-scale mathematical programming challenge, due to the variables that must be defined and the constraint conditions that must be listed for all of the scenarios. The lot-scheduling problem, which is modeled by the stochastic programming model considered in the present study, in particular, involves very substantial difficulties, if it is to be solved in its original format, as a mixed-integer programming problem. Therefore, in the present study, we took the problem structure arising from the modeling and formulation into account, and opted to pursue an approximate solution by using a framework known as the scenario aggregation method, which was proposed by Rockafellar and Wets [4].

4.2. Overview of the Scenario Aggregation Method

The scenario aggregation method is a solution method wherein a scenario sub-problem is defined for each route on the scenario tree leading from the root to a leaf, and the solutions obtained by solving the scenario sub-problems are aggregated. An overview of this solution method follows.

First, solutions are computed by solving the scenario sub-problems (we call these the admissible solutions). Next, the allowable solutions are aggregated, in order to compute a solution that satisfies the nonanticipativity condition (we call this the implementable solution).

The admissible solutions are guaranteed to be practicable for each scenario, but do not necessarily satisfy the nonanticipativity condition. In contrast, the implementable solution is guaranteed to satisfy the nonanticipativity condition, but is not guaranteed to be feasible for each scenario. Therefore, in the scenario aggregation method, the difference between these two types of solution is added to the scenario sub-problem in the form of a quadratic penalty term, and these differences are gradually allowed to converge until finally a solution to the problem to be solved can be computed.

The following section describes this process in detail.

4.3. Solution Algorithm

Below is described the specific procedure. In order to reduce the computation time required to reach the end condition in the scenario aggregation method, following the research of Løkketangen and Woodruff [5], we took into consideration only the convergence of integer variables, not the convergence of continuous variables.

Step 1

The following initial scenario sub-problem, corresponding to a scenario s, is solved and the admissible solutions are computed.

Step 2

The following aggregation is applied to the admissible solutions, and the implementable solutions are computed. The values of the Lagrange multipliers are set to 0 and we go to Step 3.

Step 3

A scenario sub-problem that has the following 0-1 constraints, corresponding with each scenario s, is solved and the admissible solutions, , , are computed. The objective function terms starting from the third term are penalty terms for the admissible and implementable solutions; ρ is a parameter in the scenario aggregation method.

Step 4

Aggregation is applied to the admissible solutions, and the implementable solutions, , , are computed. If the admissible solution and the implementable solution become equal, we go to Step 5. Otherwise, the values of the Lagrange multipliers, , , are altered using the equations below and we go to Step 3.

Step 5

The value of the converged integer variable is substituted into the original problem formulation and the following linear programming problem is solved. The values of the continuous variables, , are computed to complete the procedure.

5. Numerical Experiments

5.1. Objective and Method of Numerical Experiments

Numerical experiments were performed based on the following perspectives.

1) The benefits of the stochastic programming model are assessed by comparison with the deterministic programming model (see Section 5.2).

2) Next, the behavior of the solution method using parameter ρ, as mentioned in Section 4.3, is analyzed. After that, the performance of the proposed solution method is assessed by comparing it with a case in which a direct branch-and-bound method-based solution method is used for the formulation of the stochastic programming model (a mixed-integer programming problem) (see Section 5.3).

The method of simulation was as follows. The numbers of item types N, machines M, and times T were set as (N, M, T) = (3, 2, 10), (3, 2, 15), (4, 2, 10), (4, 2, 15), (4, 3, 10), (4, 3, 15), (5, 3, 10), (5, 3, 15).

(These problems were then numbered from 1 to 8 so that problems could later be reference by number). Instances were then generated for each of these by random number. However, the changing demand scenarios were applied according to Table 1. In the table, up to eight of the T number of times have been divided into four equal sets, which are named P1, P2, P3, and P4 (for example, with T = 10, P1 represents t = 1, 2). The values in the table indicate the ratios of how the demand changes in

Table 1. Demand patern in each secenario.

each scenario, compared with the base amount of demand (the case where s = 1) when the changing demand scenarios were generated.

We consider cases with two, four, and eight scenarios. When S = 2, scenarios 1 and 2 each arise with a probability of; when S = 4, scenarios 1, 2, 3 and 4 each arise with a probability of. The case when S = 8 is treated similarly.

The package used to apply the scenario aggregation method was OPL Studio 5.2. For optimization of the scenario sub-problem in Step 3, which is a quadratic programming problem having a 0 - 1 condition, and the mixed-integer programming problem used for comparison, the mixed integer optimizer in CPLEX (branchand-bound method-based solution) was used. The computer used for experiments was a DELL Precision 490 (Xeon 5060 3.20 GHz, memory 2 GB).

5.2. Value of Stochastic Solution

As a criterion of assessment, we used the value of stochastic solution (VSS) represented by the equation below. If we take the optimal objective function value of the stochastic programming model to be zp and the optimal objective function value of the deterministic programming model to be zd, then VSS is defined as follows.

The demand at each time in the deterministic programming model was given by the mean of the demand across all scenarios in the stochastic programming model, and we assume that this demand will arise with probability 1 under that scenario only. Specifically, this was solved as one instance of the deterministic programming model, and the values of the decision variables were decided.

Next, we looked at the situation depicted in the formulation below that considers the penalty of running out of inventory, and computed the costs in each scenario when the values of the (only set of) decision variables xnmt, ynmt, znmt which could solve the current deterministic programming model were used (the number of results obtained corresponds with the number of scenarios). We then computed the mean of these results based on the probabilities of the scenarios arising and used this as the objective function of the deterministic programming model. is the amount of demand which could not be satisfied by each scenario, and Hn is the penalty per unit of demand not satisfied (which corresponds to twice the inventory storage cost hn).

(27)

(28)

(29)

(30)

(31)

Factors which do not appear in the original problem are considered here because, in contrast to conventional deterministic and stochastic programming models that do not allow for inventory to run out, when the values of variables are decided in a deterministic programming model that incorporates stochastic variation in the demand, it is possible for inventory to run out. As stated above, the penalty that arises when inventory runs out in such cases is assumed, in this numerical example, to be twice the inventory storage cost.

Table 2 lists the value of solutions from the stochastic programming model. Since it is necessary, in this case, to accurately assess the model, the formulation by the stochastic programming model (a mixed-integer program) was solved in its original format by the mixed integer optimizer in CPLEX, and only the data from which an optimal solution (within 3600 seconds) was obtained was considered. That is to say, the solution found at this time was not from the aforementioned scenario aggregation method. Table 2 shows the results for Problem 1 and Problem 5, for which optimal solutions could be obtained for all scenarios (as shown in the table).

From Table 2, it is apparent that when the number of scenarios increases, the VSS value increases accordingly. This is thought to be due to the fact that when the number of scenarios increases and the element of uncertainty

Table 2. Value of solutions from the stochastic model.

grows, the benefit of the stochastic programming model also increases.

In this section, we have shown only the case solvable as an integer programming problem that is equivalent to the stochastic programming model. However, in general, the scale of the problem grows as the number of scenarios is increased, making it more difficult to obtain a good solution (the optimal solution or one close to the optimal solution). As such, the importance of a procedure for finding the solution for a stochastic programming model directly and in a short period of time is heightened.

5.3. Assessment of Performance of the Proposed Solution Method

The optimal objective function values and computation times for the solution method proposed in the present study and the method of using the mixed integer optimizer in CPLEX directly to determine the formulation of the stochastic programming model (this will be referred to below simply as mixed-integer programming) were compared for the problem groups described in Section 5.1 for two, four, and eight scenarios.

The computation time for the solution method of the present study and mixed-integer programming were both limited to less than 3600 seconds; if the optimal value was not obtained by mixed-integer programming, a tentative objective function value was computed when the computation time reached the limit. The results are shown in Tables 3-5.

With proposed solution method, it was necessary to set the value of the parameter ρ that appears in Step 3 of Section 4.3. It was predicted that the behavior of the optimization would depend on this parameter value. Therefore, all of the results are shown for the values ρ = 0.2, 0.4, 0.6, 0.8, and 1.0. The optimization problems that appear in each step of the proposed solution method, as described in Section 4.3, were solved by using CPLEX as stated above.

Two points are of interest here:

• The relationship between the parameter set and the behavior of the solution method

• The performance of the proposed solution method in contrast to the case where the mixed-integer programming problem was solved directly using the branch-and-bound method-based solution

Table 3. Results from the stochastic model (# of scenario = 2).

Table 4. Results from the stochastic model (# of scenario = 4).

Table 5. Results from the stochastic model (# of scenario = 8).

The changes in behavior that result from changing the parameter ρ can be observed by comparing within a given row of a particular table. However, no specific pattern of behavior can necessarily be observed in the computation times and the optimal objective function values, and even when the parameter is changed in addressing the same problem, one cannot say that the effect is large enough to bring about any significant differences.

Comparing the solution method proposed in the present study and mixed-integer programming using Tables 3-5 reveals that although the proposed solution method does not always compute the same result as mixed-integer programming, in many cases either the same or an extremely close value is obtained.

There is a striking increase in the computation time of mixed-integer programming as the number of scenarios increases. In contrast, the computation time of the solution method we propose is relatively short, and although it falls a little behind the results of the latter in terms of how good the solution is, in cases where there are many scenarios, it is overwhelmingly superior in computation time. In particular, when the number of scenarios is high (S = 8), the proposed solution method obtains the feasible solution in a short period of time, in contrast to the mixed-integer programming computation, which frequently reaches the upper limit of time and has to stop.

This difference in computation time trends is thought to be due to the fact that, with the solution method we propose, although the computation time grows as the number of scenarios increases, the fact that the problem is broken down into sub-problems for each scenario which are then solved means that the effects of increasing the number of scenarios can be limited, compared to mixed-integer programming.

6. Conclusion and Future Challenges

In the present study, we considered the formulation of the lot-scheduling problem on parallel machines using a stochastic programming model and demonstrated the benefit of such a model over a deterministic programming model.

We developed an approximate solution method which applied the scenario aggregation method and demonstrated that even when the number of scenarios increases, thus making the problem large in scale, it is possible to compute an accurate solution that is of practical application in a short period of time.

REFERENCES

  1. J. R. Birge, “Stochastic Programming Computation and Applications,” INFORMS Journal on Computing, Vol. 9, No. 2, 1997, pp. 111-133. doi:10.1287/ijoc.9.2.111
  2. J. R. Birge and F. Louveaux, “Introduction to Stochastic Programming,” Springer-Verlag, Berlin, 1997.
  3. T. Shiina, “Stochastic Programming (in Japanese),” In: M. Kubo, A. Tamura and T. Matsui, Eds., Ôyô Sûri-Keikaku Handbook, Asakura Syoten, Tokyo, 2002, pp. 710-769.
  4. R. T. Rockafellar and R. J.-B. Wets, “Scenarios and Policy Aggregation in Optimization under Uncertainty,” Mathematics of Operations Research, Vol. 16, No. 1, 1991, pp. 119-147. doi:10.1287/moor.16.1.119
  5. A. Løkketangen and D. L. Woodruff, “Progressive Hedging and Tabu Search Applied to Mixed Integer (0,1) Multistage Stochastic Programming,” Journal of Heuristics, Vol. 2, 1996, pp. 111-128.
  6. H. Meyr, “Simultaneous Lotsizing and Scheduling on Parallel Machines,” European Journal of Operational Research, Vol. 139, No. 2, 2002, pp. 277-292. doi:10.1016/S0377-2217(01)00373-3
  7. H. Arai, S. Morito and J. Imaizumi, “A Column Generation Approachfor Discrete Lotsizing and Scheduling Problem on Identical Parallel Machines,” Journal of Japan Industrial Management Association, Vol. 55, 2004, pp. 69-76.

Journal Menu >>