JP2003248508A - Method for generating production schedule of virtual fabrication - Google Patents

Abstract

(57) [Summary] In a VF, it is possible to generate an optimal production schedule in which operations between machines, processes, and companies are adjusted, and interests between companies are adjusted. A total cost including a penalty cost corresponding to inter-item mechanical interference and a penalty cost corresponding to fulfillment of a work-in-process inventory, in order to generate, by a computer, a production schedule applied to a VF multi-item multi-step production system. The one-dimensional sub-optimization problem for each item is optimized independently for all items, and for each item and machine and for each time slot, the time slot is used by the machine for production of the item. Is obtained as a solution (304-308). It is determined whether or not mechanical interference between the items with respect to the obtained solution is eliminated and whether or not the work-in-process inventory is satisfied, and the corresponding penalty cost is updated according to the determination result, and steps 304 to 3 are performed.
08 is executed again (309-311).

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a virtual fab which constitutes a multi-item multi-step production system in which a plurality of machines owned by a member process items corresponding to the respective steps in a plurality of steps. Between processes, between processes,
The present invention relates to a virtual fab production schedule generation method suitable for generating an optimal production schedule capable of coordinating operations between companies and associated interests between companies.

[0002]

2. Description of the Related Art Recently, it has been considered that members (member companies) bring a core technology and its surplus capacity to constitute a virtual fab (hereinafter, referred to as a VF) comprising an advanced production system. It is hoped that this VF will work together to promote the manufacturing industry of all members so that it can respond to orders from various customers with high quality, reasonable prices, and quick delivery. In such a VF, a multi-item, multi-process production system including a multi-process, multi-machine as shown in FIG. 8 is constructed using machines owned by the respective member companies. In a multi-item, multi-step production system, various orders are classified into a plurality of items and switched production is performed.

[0003]

However, in order to realize VF, adjustment of operation is simply performed between machines.
Since it extends not only between processes but also between companies, the scale of operation adjustment becomes enormous, and it is necessary to add a new phase of adjusting interests between companies. Therefore, in order to realize VF, a mechanism is required that enables coordination of operations between these machines, processes, and companies, and coordination of interests between companies.

[0004] If a problem relating to manufacturing is to be dealt with at the operation level, each process and the time transition of the state of the work-in-progress must be dealt with explicitly in a mathematical model, and the problem is the number of operations. Is a time optimization problem with the same dimensions as Therefore, solving the above-described problems requires a high resolution that is incomparable with the resolution of the existing model and a completely new solution principle.

However, conventionally, in the VF, each processing and the time transition of the state of the work-in-progress are handled explicitly in a mathematical model, so that the operation adjustment between machines, processes, and companies, and the accompanying company. No reasonable mechanism was known to allow coordination of interests between the two.

The present invention has been made in view of the above circumstances, and has as its object to provide an optimal production schedule for coordinating operations between machines, processes, and companies, and thereby coordinating interests between companies. It is an object of the present invention to provide a method for generating a production schedule for a virtual fab.

[0007]

According to one aspect of the present invention, a multi-item multi-process production of a virtual fab in which a plurality of processes owned by a member process items corresponding to the respective processes in a plurality of processes. A production schedule generation method for a virtual fab, wherein a production schedule applied to the system is generated by a computer is provided. This method is used for each item processed in each step.
The one-dimensional partial optimization problem for each item that optimizes the total cost including the first penalty cost corresponding to inter-item mechanical interference and the second penalty cost corresponding to the fulfillment of work-in-process inventory is different from other items. Independently solved, for each item and machine, and for each time slot whose planning period is divided at fixed time intervals, whether the time slot is used by the machine for production of the item And a machine for determining the magnitude of the degree of mechanical interference in the same machine between each item with respect to the solution for each time slot for each machine for each item obtained in this solution step. An interference determination step;
A work in process inventory sufficiency determining step of determining whether the work in process inventory is satisfied with respect to the solution for each time slot for each item and machine obtained in the solution step, and determining that the degree of mechanical interference between the items is large In this case, the first penalty cost is updated so as to reduce the degree of the mechanical interference, and if it is determined that the work-in-process inventory is not satisfied, the work-in-process inventory is satisfied. Updating the second penalty cost as described above, and re-executing the solution step each time, and determining that the degree of mechanical interference between the items is small, and that the work-in-process inventory is satisfied. Generating a production schedule based on the solution for each time slot for each item and for each machine obtained in the solution step at the time of the determination. And it features.

In the present invention, the coordination of operations between machines, processes, and companies and the coordination of interests between companies are required, and the problem of multi-item, multi-process scheduling in VF, that is, between companies, Finding the optimal solution to the problem that maximizes the profits of each company under various constraints including various constraints involves finding the optimal value of the problem that maximizes the profits of the entire VF (global optimization problem). We focus on the fact that they are equivalent. Focusing on the problem of maximizing the profit of the entire VF, that is, the problem of dimensional optimization for all items, can be replaced by a one-dimensional partial optimization problem for each item. Instead of solving the problem of maximizing the profit of each company from the grasp of each machine by each machine to the grasp of each machine, instead of solving the problem of maximizing the profit of each company, for each item processed in each process in the VF multi-item multi-process production system, The present invention solves a one-dimensional partial optimization problem for each item that optimizes total cost including a first penalty cost corresponding to mechanical interference and a second penalty cost corresponding to fulfillment of work-in-process inventory. The one-dimensional partial optimization problem includes a problem of eliminating mechanical interference between item-specific schedules (item-specific solutions) and a problem of satisfying work-in-process inventory.

Therefore, when it is determined from the operation for solving the one-dimensional partial optimization problem and the solution for each time slot for each item and each machine obtained here that the degree of mechanical interference between the items is large. The operation of updating the first penalty cost so as to reduce the degree of the mechanical interference, or the second operation so that the in-process inventory is satisfied when it is determined that the in-process inventory is not sufficient. By alternately repeating the operation of updating the penalty cost, it is possible to obtain a solution in which it is determined that the mechanical interference has been eliminated and the in-process inventory is satisfied. The solution is a decision variable that indicates, for each item and each machine, and for each time slot, whether the time slot is being used by the machine for production of the item.

Therefore, the machine interference constraint is determined from the variables determined for each item, each machine, and each time slot, which are the solutions when it is determined that the machine interference has been resolved and it is determined that the in-process inventory has been satisfied. And a production schedule that represents the lot size and the time position of each lot for each item and for each machine that satisfies all of the conditions (interrelation constraint conditions) of the in-process inventory satisfaction constraint (prohibition of out-of-stock items). It becomes possible. As can be seen, this schedule solves all of the various decision aspects involved in the multi-item, multi-step scheduling problem at the same time. In addition, focusing on the machine owned by each member (member company), when this schedule is indicated by the corresponding decision variable that the machine is used for production (operation) of the item, The member has won the operation for the item. In other words, in the generated production schedule, operations between machines, processes, and companies are coordinated. Solving the above-mentioned partial optimization problem is equivalent to solving the problem that maximizes the profit of each company.Moreover, the optimal solution of the partial optimization problem is adjusted for each machine for each item. The coordination of interests between companies will be achieved while coordinating operations between machines, processes, and companies under restrictions.

Here, as the mutual relation constraint, in addition to the above-mentioned mechanical interference constraint and the work-in-process inventory satisfaction constraint, among the items (i) processed in each step, if the processing of the item (i) is not completed. For the item (i) that cannot be processed for the subsequent item (j), a simultaneous processing prohibition constraint indicating that fact is introduced, and the one-dimensional partial optimization problem for each item is solved by the first and second items. And a partial optimization problem that optimizes the total cost including the third penalty cost corresponding to the satisfaction of the simultaneous processing prohibition constraint in addition to the above penalty cost. In this case, each time an operation for solving the partial optimization problem is performed, it is determined whether or not the simultaneous processing prohibition constraint is satisfied with respect to the obtained solution for each time slot for each machine for each item, and the simultaneous processing prohibition constraint is satisfied. If it is determined that there is no
The operation of updating the third penalty cost so as to satisfy the simultaneous processing prohibition constraint is repeated until the simultaneous processing prohibition constraint is satisfied. As a result, the production schedule that represents the lot size and the time position of each lot for each item and machine that satisfies all the conditions including not only the machine interference constraint and the work in process inventory satisfaction constraint but also the simultaneous processing prohibition constraint is set. Can be generated.

Here, the first and second penalty costs (and the third penalty cost) correspond to the first and second penalty costs.
Lagrange multiplier (and third Lagrange multiplier)
And the above-mentioned one-dimensional partial optimization problem for each item is reduced, for example, for each item processed in each step, the constraint on mechanical interference between the items is relaxed by weighting with a first Lagrangian multiplier, and If the constraint on inventory fulfillment is a one-dimensional partial optimization problem that is relaxed by weighting with the second Lagrangian multiplier (and the constraint on simultaneous processing prohibition is relaxed by weighting with the third Lagrangian multiplier), The problem of resolving the machine interference between different solutions and the problem of satisfying the work-in-process inventory (and the problem of satisfying the simultaneous processing prohibition constraint) are defined as first and second Lagrangian peculiar to the fee for use of the machine. By updating the multipliers (and further the third Lagrangian multipliers) individually, the problem can be easily solved.

[0013] Also, by dealing with the one-dimensional partial optimization problem, for each item and each machine, and for each time slot, whether or not the time slot is used by the machine for production of the item is determined. A decision variable indicating whether or not, the stock status (transition of stock), and the remaining setup time can be explicitly handled. For this reason, this one-dimensional partial optimization problem is described below in terms of an optimal cost function Vt (δ _it , x _it ,
s _it , μ), ie, any time slot t
Δ _it ^k , the first Lagrange multiplier μ _t ^k , the second Lagrange multiplier μ
_it (the third Lagrange multiplier is μ _ijt ^kl ), the vector having these Lagrange multipliers as elements is μ, and the item i at the end of the time slot t is
Using the cumulative quantity developed from the customer's shipping request quantity in each time slot up to the time slot t of the item i in the item i in the time slot t in place of the cumulative shipping quantity actually passed to the next process of the apparent calculated inventory status, and the rest of the setup time required to set up the item i, respectively the state variable x _it, as s _it, was taken at each time slot until the time slot t best It can be solved by the optimal cost function Vt (δ _it , x _it , s _it , μ) that represents the sum of the costs generated by the decision.

[0014] Here, the cost calculated in the optimal cost function includes a first penalty cost corresponding to the royalty of the machine is calculated based on the first Lagrangian multiplier mu _t ^k, the second Lagrangian multiplier a second penalty cost corresponding to the machine usage fee calculated based on μ _it and a third penalty cost corresponding to the machine usage fee calculated based on the third Lagrangian multiplier μ _ijt ^kl E), Echelon inventory storage cost per time slot hi for the value newly added by processing item _i.
And a cost determined by the state variable x _it .

The present invention according to the above-described method for generating a production schedule for virtual fabs is also realized as an invention relating to an apparatus (production schedule generating apparatus for virtual fabs).

Further, the present invention provides a computer for executing a procedure corresponding to the present invention (or for causing a computer to function as each unit corresponding to the present invention, or for realizing a function corresponding to the present invention to a computer). The present invention is also realized as an invention relating to a program (for causing the program to execute).

[0017]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 shows a functional block configuration of a production schedule generation device for a virtual fab (VF) according to an embodiment of the present invention.

The production schedule generating device shown in FIG.
A production schedule required for a VF constituting a multi-item, multi-step production system for processing items corresponding to the respective steps in a plurality of processes by a plurality of machines owned by a member company, that is, between machines, between processes, and between companies. This is to generate (determine) an optimal production schedule that allows the coordination of the operations described above and the coordination of the interests between companies.

This production schedule generating apparatus is realized by a computer such as a personal computer having a block configuration shown in FIG. The computer in FIG. 2 includes a CPU 21 that controls the entire computer, and a main memory 22 that stores various programs including an optimization scheduling program 241 executed by the CPU 21, data, and the like.

The computer shown in FIG. 2 also has, for example, a magnetic disk device (hereinafter referred to as an HDD) 2 as an external storage device.
3 and a CD-ROM device 24 capable of reading information stored in advance in a computer, for example, in a CD-ROM 242 as a recording medium. In the example of FIG. 2, the CD-ROM 242 includes a plurality of processes (multi-process),
An optimization scheduling program 241 for generating a production schedule in a multi-item, multi-step production system for producing a plurality of items with multiple machines (multiple facilities) is stored in advance. This optimization scheduling program 2
Reference numeral 41 denotes a CD-ROM 24
2 is read into the computer and stored (installed) in the HDD 23. CPU 21 is HD
By loading the optimization scheduling program 241 into the main memory 22 from D23 and executing the program 241, the functional block configuration of the production schedule generation device in FIG. 1 is realized.

The computer shown in FIG. 2 further has a keyboard 25 as an input device and a display 26 as an output device for display. CPU 21, main memory 22, H
The DD 23, the CD-ROM device 24, the keyboard 25 and the display 26 are interconnected by a system bus 27.

<< Basic Principle of Optimization Scheduling >> Next, before describing the configuration of the production schedule generating apparatus shown in FIG. 1, adjustment of operations among machines, between processes, between companies, and The basic principle of the optimization scheduling that enables the adjustment of the interests between the companies will be described.

<Introduction of Auction Principle> In the present embodiment, a rationalization is required in which real-time adjustment of operations between machines, processes, and companies and adjustment of interests between companies are performed in real time based on market principles. Apply a generic algorithm. Here, VF is applied to the order once received.
Will be responsible for processing by the deadline, and members shall maximize their interests. And
Introduce an auction mechanism based on market principles to a mechanism that adjusts conflicting interests between the entire VF and a company or a company.

However, the auction applied in the present embodiment is different from a normal auction, and an object to be bid down by a member company is an operation constituting each order. Further, it is assumed that all the auctioned operations are guaranteed to be executable by the VF. In other words, all operations must be auctioned off as if all orders had been processed by the due date. Therefore, in this auction, it is indispensable to include a mechanism for preventing a work-in-progress running out of stock generated in the course of processing and satisfying a constraint condition such as eliminating mechanical interference. For that purpose, various adjustments are required between companies or between machines and items. In order to ensure the rationality of these adjustments, perturbations or deviations from constraints will be penalized or rewarded according to their amount. In the present embodiment, this mechanism is referred to as an auction.

The auction mechanism applied in the present embodiment can be mathematically described by the Lagrange multiplier method as described later. Thus, the Lagrange multiplier method is responsible for coordinating everything regarding operations and interests.

Furthermore, it is essential to reduce the dimension of the problem for the calculation of an actual large-scale problem, and this is left to the Lagrange decomposition adjustment method.

<< Description of Problem and Description of Proposed Model >><Description of Problem> In VF, any member company can calculate all items and profits obtained by subtracting the cost of processing from the amount obtained by processing each item. I want to maximize the total amount for all machines.

At this time, there are some restrictions between machines, processes, and companies. First, one or more companies must undertake the required quantity of each item needed to fulfill the order. No company wants to do unprofitable operations, and vice versa, so we need to adjust for this. Second, for any machine, machine interference between items must be eliminated. Thirdly, there is a restriction on prohibition of stockout of the work-in-progress inventory.
Fourth, there is a simultaneous processing prohibition constraint. This is a restriction that often occurs in job shop type processing, and indicates that the next processing must be performed after the previous processing has been completed.

Under the condition that all of these must be met, the schedules for all the operations of all the machines of all the processes of all the companies are automatically set so as to maximize the above-mentioned gross profit by company. To decide. This is the problem to be solved in the present embodiment.

<Decomposition of Problems into Items> For a high-dimensional optimization problem of optimal scheduling in a multi-item multi-process production system, see the document "Kenji Muramatsu:" Simultaneous Optimal Scheduling by Extended Lagrangian Decomposition Adjustment Method ", Operations Research. vol. 45, no.6, pp.270-275. (200
As in the case of the multi-item single machine lot size scheduling problem described in “0)”, separability holds, and there are further constraint equations. Therefore, the problem is broken down by item. If this decomposition is possible, the solution of the problem will be between the solution of the sub-optimization problem for each item and the sub-problem, despite the fact that the structure of the target production system is extremely complex, especially since it has many steps. And coordination to satisfy the interrelationship constraint.

However, it is not possible to solve the partial optimization problem independently of the others as it is. It is for the following reasons. In-process items are involved in the multi-step scheduling problem. As for the actual work-in-progress, if the processing is performed in the previous process, the stock increases, and if the processing is performed in the subsequent process, the inventory decreases. Therefore, two series of processes are related to one item.
In other words, there are at least two items that increase or decrease by one series of processing before and after the processing.
Therefore, optimizing one partial problem will break optimization of the other partial problem. Thus, 1
The relation between two processing sequences per item is the biggest obstacle to decomposition and adjustment in the Lagrange decomposition adjustment method described later.

In order to clarify the location of a problem caused by the relationship between two processes in one item, the concept of "process independence" is introduced and defined as follows. When the problem is decomposed into partial optimization problems, the fact that the same process or series of processes does not appear over a plurality of partial optimization problems is referred to as "process independence".

In order to ensure the independence of this processing, it is necessary to eliminate one of the processing series from one item without changing the essence of the problem. The means for that is the concept of “apparent inventory” described below.

<Apparent inventory> In general, work in process inventory is
This is the actual inventory generated between processes, and can be defined as the sum of the initial inventory and the cumulative production amount minus the actual cumulative shipment amount or cumulative processing amount to the next process. However, in the present embodiment, instead of the cumulative shipment amount actually passed to the next process of a certain item, as shown in Expression (1) described below, each time slot (planning period) The shipment request (external demand) at the equally divided time interval) is developed for the item, and the amount corresponding to the above-described work-in-process inventory is calculated using the accumulated amount. Thus, this is not an actual work-in-progress inventory, but a fictitious inventory or an apparent inventory. Hereinafter, this is referred to as “apparent inventory”.

As described above, by introducing a new concept of apparent inventory instead of work-in-process inventory, it becomes possible to correspond one item of processing to one item. However, as a result of planning the processing based on the apparent stock, there is a risk that the actual work-in-process stock may be out of stock.
Therefore, means for avoiding this danger is required. Therefore, in the present embodiment, "processing consistency" defined below
Introduce the concept of

The actual inventory of a work-in-progress is increased or decreased by the processing of the work-in-progress and the succeeding direct connection items. "Process consistency" is established when these processes based on apparent inventory under the independence of processes are feasible in the sense that they do not cause the actual work-in-process inventory to run out of stock. Let's call it. On the contrary, as long as "processing consistency" is established, processing independence is recognized, but if "processing consistency" is not satisfied, processing independence is not recognized, This indicates that adjustment is necessary so that the actual work-in-process inventory does not run out (that is, is satisfied). Note that the item at the subsequent direct connection point is a process (subsequent direct connection point) immediately after processing (producing) an item x.
8 is an item y to be processed (produced) by incorporating the item x, and in the example of FIG.
And item i-1. On the other hand, the item x is an item processed in a process immediately before the item y, that is, an item at a preceding direct connection point.

<Achieving Process Consistency> In this embodiment, in order to achieve the process consistency defined as described above, the constraint that the actual work-in-process inventory is not out of stock (the work-in-process inventory (Sold out prohibition restriction) is applied. This constraint is represented by the following equation (7).

<Echelon Inventory Storage Cost> However, if ordinary inventory storage costs are applied to solve the partial problem by focusing on the apparent inventory instead of the actual work-in-progress inventory, the calculation will be inconsistent. Therefore, it is necessary to grasp inventory storage costs according to apparent inventory. By doing so, it is possible to calculate the inventory storage cost reflecting the actual situation. Known methods can be used for this. That is the concept of “Echelon inventory storage costs”.

Hereinafter, the Echelon inventory storage cost will be described. First, when any item is processed and added new value, inventory is stored not only for the entire value of the item created by the process but for the value of the newly added part. You can estimate the cost. Furthermore, its value can be considered to be constant when the item is incorporated into another item, as long as the item remains in the system. In that case, based on the same concept, the inventory storage cost is estimated only for the newly added value of the value of the newly produced item. The inventory storage cost defined in this way is called “Echelon inventory storage cost”.

The details of the Echelon inventory storage cost are shown in Table 3. Item 3 incorporating item 1 produced at time τ1 and item 2 produced at time τ2 is produced at time τ3, and item 3 is shipped at time τ4. An example will be described with reference to FIG. Here, the inventory management costs estimated for the values of the items 1 and 2 are h1 and h2, and the inventory management costs estimated for the value newly added by the production of the item 3 are h1 and h2.
Assume it is 3.

In this case, as shown in FIG. 7A, generally, the inventory storage cost h1 of the item 1 is generated during the period of time τ1 to τ3, and the inventory storage cost h2 of the item 2 is generated during the period of time τ2 to τ3. I do. The storage inventory cost of item 3 is the sum of the inventory storage cost h3 estimated for the value newly added by the production of the item and the sum h1 + h2 of the storage inventory costs h1 and h2 of items 1 and 2. h1 + h2 + h3, and from time τ3
It occurs during the period of τ4.

On the other hand, Echelon inventory storage cost
As shown in FIG. 7B, even after the time τ3 when the items 1 and 2 are incorporated into the item 3, the inventory storage costs h1 and h2 of the items 1 and 2 remain unchanged, and until the shipping time τ4 of the item 3. Treated as continuing. Further, the stock keeping cost of the item 3 is estimated only for the newly added value.
3, which is treated as occurring during the period from time τ3 to τ4. As a result, the inventory storage costs can be handled independently for each of the items 1, 2, 3 and the inventory storage costs can be adjusted to the apparent inventory.

<Method of Auction> (Role of Center) The VF has a center. The center performs technical analysis on customer inquiries. First, the order is broken down into operations (processes) or resulting items, and the amount of work and the price are estimated. An operation is a convenient unit of processing (or process) for distributing orders from customers based on an auction and distributing each company. What is processed is the item. For example, adding an operation to one or more items produces another item. Each item is not necessarily a finished product. Data required for the auction is given for each operation (item).

Next, the center decides whether or not to accept the order in consideration of various information such as load.

The center guarantees the contracted quality, price and delivery date to the customer.

For the accepted order, the center raises a specification necessary for processing and discloses it to the members. The specifications document, for each operation, the required production technology data in addition to the workload, price, and delivery date.

The center handles the auction.

The target of the auction is each operation, and usually a single operation is sold by a single company. However, there are cases where a plurality of companies make a successful bid for a large-scale operation, and in such a case, the members are informed in advance.

The feature of this embodiment is that the above-described auction mechanism is realized by the optimization scheduling program 2
Substitute with the computer algorithm provided by 41. More specifically, this is all about updating the Lagrange multiplier, which will be described later.

The center returns the result of the auction to the members. The center will settle the company, including penalty costs incurred for the adjustment. The penalty cost mathematically refers to the value of a Lagrange multiplier (dual cost). The penalty cost is, for each company,
It is usually an additional cost, but if the sign is reversed, it is a reward.

(Rights and Responsibilities of Members) Each member is guaranteed to give priority to their business.

Each member declares, over time, each machine's available time for VF operation by time slot.

Each member obtains public operation information and acts according to market principles. In other words, if there is an operation that you want to enter from your own profit,
Entry, otherwise no entry. But,
The entry does not necessarily mean that the operation will fit in the hand, and that it does not necessarily mean that the operation can be performed at the desired timing. These adjustments are made by the above algorithm.

<< Formulation into Problem Model >><SymbolsUsed> (1) Subscripts and Their Sets First, subscripts and their sets applied in the present embodiment are represented by t: a time slot number for engraving a planning target period, t ∈T =
(1, 2,..., N _t ) i: operation (processing) or the number of an item resulting from the operation, i∈I = (1, 2,..., N _i ) where i = 0 is a customer (outside of VF) (Since the symbol i is a suffix used to indicate movement, the same suffix is allowed to represent different types of operations or items and customers.) m: member company number, m∈F = (1, 2,..., _nm ) k: machine number, k∈K = (1, 2,..., n _k ) E (m): belongs to member company m In a set of machines, the following relationship K = Σ m _{成 り} F E (m) holds. A: a set of work-in-progress items (items having succeeding items) A 品目: a set of items having a simultaneous processing prohibition constraint with an item belonging to a subsequent direct connection point S (i): a set P of subsequent direct connection points of item i (i): set of preceding direct connection points of item i P ~ (i): intersection of P (i) and A ~, that is, P (i) ∩A ~ K (i): available for processing item i Machine set M (k): Set of items a (i) that can be processed by machine k: Index function a ~ (i) which takes 1 if item i belongs to work-in-process set A and 0 otherwise; Takes a value of 1 when belongs to the set A と き, and defines an index function that takes 0 otherwise.

(2) First Input Data (Data Provided by Member Company) Next, input data (production data) provided by the member company and set in advance, which is applied in the present embodiment, is represented by p ^k: throughput of the item i in the timeslot t in machine k, i.e. (put to zero if one is not processing) capacity b _it ^k: treatment costs in the machine k, time slot t of the material i c _it ^k: Setup cost s _imax ^k of item i in machine k and time slot t: setup time s _i0 ^{k of} machine k for item i: remaining time of setup in machine k and item i in time slot t = 0, ie, initial value x _i0 : the actual work-in-process inventory at time slot t = 0 of item i, and 0 for problems without work-in-process inventory δ _i0 ^k : time slot t = 0 of item i in machine k
, Ie, the boundary values of the decision variables.

(3) Second Input Data (Data Provided by Customer) Next, input data (shipment request amount data) provided by the customer and set in advance, which is applied in the present embodiment, is represented by r _i0t : Defined as the amount requested by the customer for item i in time slot t.

(4) Third input data (data determined by consultation between member companies or led by the center) Next, the data is determined by consultation between member companies or led by the center, which is applied in this embodiment, and The input data to be set are as follows: a _i : price per unit quantity of item i τ _ij : lead time of item i until it is incorporated into item j (time to precede processing) ρ _ij : item i to be incorporated into item j Required quantity h _i per unit of item _j : Inventory storage cost per time slot (Echelon inventory storage cost) for value newly added by processing of item i Data (Equation (1),
(Refer to (2).) R _ijt : Required amount of item i used to produce item j in time slot t r _{· t} : Defined as required amount of item i in time slot t.

(4) Decision Variable Next, the decision variable applied in the present embodiment is defined as follows.

Δ _it ^k : machine k at time slot t
The decision variable, δ _it ^k , which represents the processing of item i of item 1, is 1, when item i is processed by machine k in time slot t,
Otherwise 0 δ _it : δ _it ^k , k∈K (i) as a vector, δ _i = (δ _i1 , ..., δ _it , ... δ _int ) δ = (δ ₁ , ..., δ _{i ^{, ... δ ni) δ k:}} δ it k matrix ^{_{δ k = (δ it k)}} δ it k whose elements are the only decision variables in the model applied in this embodiment. Note that this variable deals with the processing aspect of item i, as well as the decision aspect regarding which machine, and therefore, which company has won item i.

(5) State Variables Next, the state variables applied in the present embodiment are defined as follows.

[0061] s _it ^k: here remaining time ^{_{0 ≦ s it k ≦ s imax}} k of setup of the machine k in time slot t of the item i, s _it is the s _ti ^k, k ∈ K (i) is the element Vector, s _i = (s _i1 , ..., _sit , ... s _int ) s = (s ₁ , ..., s _i , ... s _ni ) x _it : apparent work-in-process inventory at the end of time slot t of item i In terms of quantity, the defining equation is expressed as in equation (3) described below.

As described above, by paying attention to the apparent inventory instead of the actual inventory, it is possible to avoid treating the payout amount to the next process as a decision variable, and thus it is possible to solve the problem for the first time. However, inconsistencies in processing may occur, and inconveniences such as out-of-stock products may occur. However, these are handled explicitly in the constraint conditions (in-progress prohibition of out-of-stock items). Even when there are a plurality of processing machines, attention is paid to the stock of items in the system without considering the stock point, that is, the difference between machines. Details of the apparent stock will be described later.

(6) Lagrange Multiplier Next, the Lagrange multiplier applied in the present embodiment is represented by μ _{·· t} ^{k ·} : Lagrange multiplier for eliminating mechanical interference of machine k in time slot t (to the machine usage fee) ^... Μ _{i · t} ^... : Lagrange multiplier for satisfying the stock-out prohibition constraint in the time slot t of the work-in-progress item i (the processing of the item i is advanced before the time slot t, and at the same time, the items j, j∈S μ _ijt ^kl : Lagrangian multiplier for satisfying the simultaneous processing prohibition condition of item i and succeeding item j in time slot t μ: all Lagrangian multipliers as elements Define as a vector with

<Constraint Equation and Objective Function> The above problem is formulated as follows.

(Relationship between Various Required Amounts) The required amount of the item j is developed into the item with the lead time τ _ij . Here, the item i is a work in process. Therefore, r _ijt : and r _{i · t} can be expressed as in the following equations (1) and (2).

[0066]

(Equation 1)

(Definition formula of apparent work-in-progress stock) Apparent work-in-progress stock x at the end of time slot t of item i
_it is defined by the following equation (3).

[0068]

(Equation 2)

In the above equation (3), x _it is calculated from the initial stock x _i0 shown by the first term on the right side and the processing amount t ′ = 1 of the item i in the time slot t ′ shown by the second term. t '=
t, that is, item i up to the end of time slot t
Of the required amount of the item i in the time slot t ′ shown in the third term from t ′ = 1 to t ′ = t, that is, the customer (VF) Outside)
From the time t until the end of the time slot t, is defined as a value obtained by expanding the shipping request for the item i and subtracting the accumulated amount of the item i. If the item i is the last item, the apparent work-in-process inventory matches the actual inventory.

(Transition equation of apparent work-in-process inventory) The actual processing of each item i in the time slot t is δ _it ^k = 1
And s _it ^k = 0. Therefore, the transition of the apparent work-in-process inventory follows the following equation (4).

[0071]

(Equation 3)

In the above equation (4), x _it is the apparent inventory amount at the end of time slot t-1 of item i (the first term on the right side).
And the processing amount in the time slot t (the second term on the right-hand side) minus the required amount r _{i · t} (the third term on the right-hand side) up to the time slot t obtained by developing the required amount from the customer. Is represented.

(Process of transition of remaining machine setup time)
Formula) Remaining setup time of each item i in time slot t
Time (remaining setup time) s _it ^kIs the period when the machine k is idle
Between (δ_it ^k= 0) is s_it ^k= 0. This s_{i t} ^k
Is when the item is switched, that is, when the processing state of the machine k is δ
_it-1 ^k= 0 to δ_it ^kWhen = 1, s_imax ^kWhen
Become. Thereafter, each time one time slot elapses, one
To 0, and after that, item switching occurs again.
Maintain that state until Therefore, the time slot
Remaining time s of the setup time for each item i at t_it ^kIs
It is expressed by the following equation (5).

[0074]

(Equation 4)

The first term on the right side of the above equation (5) is δ_it-1 ^k=
0 to δ_it ^kS when changed to = 1 _imax ^kRemaining stage
The state transition of the sampling time is shown._it-1 ^k-1) is
Every time one time slot elapses_it ^kDecreases by 1
The state is shown.

(Machine Interference Constraint) In any time slot t, the machine k can process at most one item. That is, different items cannot be processed simultaneously in any machine k. This constraint is called a machine interference constraint, and the following equation (6)
Must be established.

[0077]

(Equation 5)

(In-progress item out-of-stock prohibition constraint) The actual inventory in the VF (multi-item, multi-process production system) at the time slot t of item i is calculated by defining the apparent in-process inventory (3) and the apparent in-process item. The following equation (7) is obtained by reformulating the equation using the inventory transition equation (4).

[0079]

(Equation 6)

(Simultaneous Processing Prohibition Constraint) The simultaneous processing prohibition constraint indicates that the processing of the item i must be completed before the subsequent processing can be started. The simultaneous processing prohibition constraint is applied when this condition is required, and is expressed by the following equation (8).

[0081]

(Equation 7)

(Objective Function) The objective function taken up in this embodiment is the profit for each company, that is, all items of profit obtained by subtracting the cost of processing from the total amount obtained by processing each item.
This is a function for calculating the total amount for all machines. This objective function is expressed by the following equation (9) for an arbitrary company m∈F.

[0083]

(Equation 8)

The first term in equation (9) is the sales obtained by processing item i with machine k in time slot t. The second to fourth terms are the costs of processing,
The term is a setup cost for processing the item i with the machine k in the time slot t. The third term is a processing cost required for processing the item i with the machine k in the time slot t.
The term is an inventory storage cost corresponding to the apparent inventory amount x _it of the item i at the end of the time slot t. The value obtained by subtracting the cost of the processing of the second to fourth items from the sales of the first item is the profit obtained by processing the item i with the machine k in the time slot t.

(Problem P0) From the above, the optimization problem to be dealt with is the problem P0 that maximizes the profit for each company represented by the equation (8) and is represented by the following objective function.

[0086]

(Equation 9)

Note that st (4), (5), (6), (7), and (8) attached to the objective function of the problem P0 are equations (4) and (5) , (6), (7), (8)
, That is, the constraint according to the transition equation of the apparent work-in-process inventory, the constraint according to the transition equation of the remaining setup time of the machine, the machine interference constraint, the constraint on the stockout of the work-in-progress item, and the constraint on the simultaneous processing. .

Here, the information on the successful bid of the item _i is carried by the decision variable vector δ _i . In the solution described later, the condition of the successful bid can be satisfied when the value of the decision variable vector is determined. Therefore, the constraint for satisfying the successful bid condition need not be added to the above set of constraint equations. The same applies to the condition for satisfying the processing amount.

<< Theory >><Introduction of the auxiliary problem P1> Although the objective function of the profit maximization problem P0 of each company is decomposed for each company, it cannot be treated independently because the constraint formula extends between companies. . In addition, the dimension of the problem is too high. Therefore, it cannot be expected to directly solve the problem P0.

In this embodiment, instead of the problem P0, V
A method is introduced in which an auxiliary problem P1 that maximizes the profit of the whole F is introduced, solved, and the solution is used as a clue. Therefore, while considering the constraint condition of the problem P0 as it is, a problem is considered in which the objective function of P0 is added to all the machines of all companies to form an objective function, and this problem is referred to as a problem P1.

(Problem P1) The problem P1, that is, the problem of maximizing the profit of the entire VF is represented by the objective function of the following equation (10).

[0092]

(Equation 10)

Here, it is noted that the objective function of the problem P1 can be added and separated for each company. That is, the decision variable δ
= (..., δ ^k , ...) is divided into one subset of decision variables δ ^k , k∈E (m) for each machine group belonging to the company m, and the objective function of P1 becomes As shown in the following equation, it can be expressed in the form of a sum of functions relating to these mutually independent decision variables.

[0094]

(Equation 11)

The above results can be summarized in the following theorem. Theorem 1 Problem P0, that is, equation (4) including constraints between companies
Finding the optimal solution to the problem that maximizes the profit of each company under (8) is a problem of maximizing the profit of the entire VF (VF
Overall optimization problem) This is equivalent to obtaining the optimal solution of P1.

Equation (4), (5), (6), (7) and (8) are related to this problem P1 as constraint conditions.
It should be noted that the method proposed here treats these constraints in two major ways. The first type is included in a subproblem and explicitly handled when solving an individual problem, and the second type is related to a plurality of subproblems as a mutual constraint. is there.

Equations (4) and (5) are transition equations,
Item specific. Therefore, they belong to the first type.

However, equation (6) relating to the mechanical interference constraint
Equation (8) relating to the simultaneous processing prohibition constraint relates to a plurality of items, and belongs to the second type of mutual relation constraint. Equation (7) relating to the prohibition of stock-out of in-process items
Also, when the item is a work-in-progress, the independence of the process is violated, so that it cannot be handled in the partial problem. Therefore, in order to guarantee the consistency of the processing, the equation (7) is treated as belonging to the second type of mutual constraint. When the item is the last item, the independence of the process is established from the beginning.

<Solution of Problem P1> Then, first, the problem P1
In relation to the objective function of Equation (6), the mechanical interference constraint of Equation (6), which is required to be treated as the interrelationship constraint, the stockout prohibition constraint of the in-process item of Equation (7), and the simultaneous processing prohibition constraint of Equation (8) are relaxed. A Lagrange function L (δ ^· , μ) shown in 11) is defined. The equation (12) is solved with the Lagrangian relaxation problem of the problem P1 as the problem P2.

[0100]

(Equation 12)

In the equation (11), μ_{・ ・ T} ^{k ・}, μ_{i ・ t} ^{・ ・}, μ
_ijt ^klAre the machine interference constraints (6) and the work in process, respectively.
Out-of-stock prohibition constraint (7), simultaneous processing prohibition constraint
Lagrange power representing penalty cost for (7)
Is a number. That is, μ_{・ ・ T} ^{k ・}, μ _{i ・ t} ^{・ ・}, μ_ijt ^klIs it
Satisfaction of machine interference constraints, inventory of work in process, simultaneous processing
Lagrange multiplier used to satisfy the prohibition constraint.

In order to solve the problem P2, it is necessary to explicitly handle the transition equation (4) of the work-in-process inventory of each item in the model. Therefore, this problem is mathematically a time optimization problem (optimal control problem), and the dimension is the number of items _ni.
Depends on Unless the dimensions of the problem are reduced, it is not expected to find a solution within reasonable time and memory requirements.

Therefore, in the present embodiment, a method of reducing the dimension of the time optimization problem to one dimension by the following decomposition is applied.

First, the Lagrangian function L of equation (11)
Note that the first term on the right side of (δ ^· , μ) becomes the following equation when the order of the sum is changed.

[0105]

(Equation 13)

Noting that the result and the function L (δ ^· , μ) can be added and separated with respect to the decision variable vector δ _i relating to processing the item i, this is decomposed for each item i. That is, formula (11) is decomposed into items and arranged.
If a term depending on δ _i is given as in equation (13) for a given μ, the function L (δ ^· , μ) is represented as in equation (14).

[0107]

[Equation 14]

This is nothing but switching the viewpoint of grasping the problem from grasping by company and by item by machine and grasping by item and machine. Lagrangian relaxation problem P2 is a time optimization problem n _i dimensional By doing further portions have been relaxed problem decomposition to issue L _i (1-dimensional partial optimization problems) it is possible to convert the P3 .

(Problem P3) The problem P3 is represented by the following equation (15).

[0110]

[Equation 15]

For a given value of the Lagrange multiplier, given by equation (15), the function maximization problem is clearly:
This is a one-dimensional time maximization problem. Therefore, the problem P3
Can be solved by the Lagrangian decomposition adjustment method.

After all, the problem P0 is the problem P1, the problem P2,
Then, the equivalent conversion is sequentially performed to the problem P3. Therefore, the following theorems 2 and 3 hold.

Theorem 2 The optimal solution of the problem P0 is obtained by finding the optimal solution of the problem P3.

Theorem 3 In the solution of the Lagrangian relaxation problem, if the value of the Lagrange function L and the value of the objective function match, it is the optimum value. Furthermore, the value of the main variable and the value of the Lagrange multiplier (dual variable) that make it possible are the optimal solution of the problem and the optimal Lagrange multiplier value, respectively. This Theorem 3 is widely known.

In the present embodiment, the subject Lagrangian relaxation problem is problem P3.

<< Solution >> <Lagrange multiplier update rule>
Lagrangian multiplier μ_{・ ・ T} ^{k ・}, μ_{i ・ t} ^{・ ・},
μ _ijt ^klEquations (16) and (1)
7) and (18).

[0117]

(Equation 16)

Α _{· t in} equations (16), (17) and (18)
^{k ·} , α _{i · t} ^·· , α _ijt ^kl are obtained by the expressions (16), (17), (1
8) Lagrange multiplier μ _{·· t} ^{k ·} , μ _{i · t} ^·· , μ _ijt
Indicates the step size used to update ^kl , all non-negative values. The step size may be determined by judging the effect of these Lagrangian multipliers from the result of the numerical solution, repeating the adjustment, and determining a value suitable for the data in question by trial and error.

<Dynamic Programming for Partial Optimization Problem> Next, a method for re-formulating the partial optimization problem P3 represented by the equation (15) into a dynamic programming method and solving the problem will be described.

(Allowable Set of Decisions) The possible value of the decision (decision variable) δ _it ^k of the machine k∈K (i) in the time slot t is stored in the inventory state x _it-1 in the preceding time slot t-1. Not only does it depend on the state (decision variable) δ _it-1 ^k in the preceding time slot t-1 and the remaining setup time s _it-1 ^k . For example, if the remaining setup time s _it-1 ^k is positive, the decision variable δ _it ^k must take the value 1, and (δ _it-1 ^k , _sit-1 ^k ) = (1,0) ) Or
Unless it is (0,0), the value 0 cannot be taken. ^{_{Therefore, (δ it-1 k,}} s i t-1 k) from ^{_{(δ it k, s it k}} ) In summary the state transition of connection to, as shown in FIG. ○ in the figure
The mark indicates that there is an allowed decision for the state of time slot t-1, and the mark indicates that it is not.

FIG. 6 shows the state transition of (δ _it ^k , s _it ^k ). For example, in FIG. 6A, the state 61 of (0,0) can be in the next time slot is either the same state 61 or the state 62 of (1, s _imax ^k ).
The state 61 indicates that the machine k is idle. Also, state 62
Indicates that the item has been switched, that is, the start of setup. This state 62, that is, the state 62 of (1, s _imax ^k )
_Can be in the next time slot is (1, s _imax ^k −
Only the state 63 of 1).

In state 63, the time has elapsed by one time slot from the start of the setup, and the remaining setup time is s _imax
^k- 1. Hereinafter, the same way, whenever the time lapse of one time ^{_{slot, (δ it k, s it}} k) at [delta] _it ^k is left 1 state of only s _it ^k is gradually decreased by 1 Eventually, the state transits to the state (1.1) 64. The state 64 indicates that the remaining setup time is 1 (for one time slot), and the state is just before the end of the setup.
The period from the state 62 to the state 64 is the period 65 during the setup. State 64, that is, the state 64 of (1,1) can be the state 66 of (1,0) only in the next time slot. State 66 indicates production. This state 6
6, that is, the state 66 of (1,0) can be in the next time slot is the same state 66 or the state 6 of (0,0).
One of 1

(Optimal cost function of partial problem and its calculation)
Next, the optimal cost function and its calculation will be described. In the present embodiment, for a given Lagrangian multiplier vector μ, the optimal cost function of the subproblem is represented by V _t (δ _it , s _it , x _it , μ), and its value is determined by the item i in the time slot t. When the decision variable vector (the state of the machine setting), the remaining setup time vector, and the inventory state (the inventory amount at the end of the time slot t) are δ _it , s _it , and x _it , respectively, It is defined as the sum of the costs incurred with the optimal decision taken in each time slot up to slot t.

What is important here is that the optimal cost function includes a vector s _it and a variable x as a vector of state variables.
_The point is that in addition to it, the decision variable vector δ _it is included. Δ _it and s _it are δ _it ^k and s _it ^k and k∈K, respectively.
Note that this is a vector with (i) as an element. Different from that of the normal optimal cost function, the decision variable [delta] _it ^k independently variable appears, due to the setup cost occurring in the time slot t is also dependent on the determination of the time slot t-1 I have. In other words, to calculate the cost incurred in time slot t,
This is because information of δ _it -1 in the time slot t-1 is required.

The optimal cost function V _t (δ _it , s _it , x _it ,
μ) is the following recursive relation (19), (2)
0).

[0126]

[Equation 17]

[0127] Here, when xit-1 is not in the allowable range, any δ _it-1 ^k, relative to ^{_{s it-1 k, V t}} (δ it, s it, x it,
μ) is always −∞. At this time, δ _it-1 ^* (δ _it , s _it ,
x _it , μ) represents the optimal decision of equation (20).

Given δ_it ^k, s_it ^k, k∈K (i) and the above equation
From (5) and (4), the selected decision δ _it-1 ^k, k∈K (i)
For s_it-1 ^k, x_it-1, The time slot t
The value of the optimal cost function at -1 is determined. Of course, Thailand
All costs incurred in the time slot t
ing. Therefore, the above equation (20) can be calculated.

(Determination of Optimal Solution in Partial Optimization Problem)
For the time slot t = 1,..., N _{t of the} item i, the optimal cost function value V _t (δ _it , s _it , x _it ,
μ) and the optimal decision δ _it-1 ^* (δ _it , s _it , x _it , μ) are all obtained and stored in the form of a table (here, cost storage area 2).
23). A procedure for determining the optimal solution of the item, that is, the schedule and the state transition at this time will be described with reference to the flowchart of FIG.

[0130] First, t = n _t all [delta] _it may take against time slots, s _it, a combination of x _{it (δ it,} s
_it , x _it ), the value of V _t (δ _it , sit, x _it , μ) is maximized, δ _it , s _it , x _it is determined, and _it is determined as an optimal solution.
These values are respectively set as δ _it ^* , s _it ^* , and x _it ^* (steps 405 and 406).

[0131] _{^{Next, δ it *, s it *}} , x it * optimal decision to _{^{δ it-1 * (δ it}} *, s it *, x it *) for specifying the (Step 4
07). These δ _it ^* , s _it ^* and x _it ^* are _calculated by the above equations (5) and (4).
To obtain s _it-1 ^* , x _it-1 ^* (step 40).
8).

Next, t is decremented by 1 (step 409). If t after this decrement does not become smaller than 1 (step 410), the processing after step 406 is performed on t after the decrement. . This is repeated until t = 1 (step 410).

As described above, the basic principle of the optimization scheduling applied in this embodiment, the problem handled by the basic principle, the formulation of the problem into a model, and the solution based on the Lagrangian decomposition adjustment method (particularly, the partial optimization Problem dynamic programming)
Was explained.

<< Example of Implementation of Optimization Scheduling >> Next, an example of implementation of the above-described optimization scheduling will be described. The production schedule generating apparatus shown in FIG. 1 performs the optimization scheduling by applying the above-described basic principle of the optimization scheduling.
, A stock amount extraction unit 11, a remaining setup time extraction unit 12,
Inter-item mechanical interference determination unit 13 and inter-item mechanical interference control unit 1
4, an in-process inventory fulfillment determination unit 15, an in-process inventory control unit 16, a simultaneous processing inhibition constraint satisfaction determination unit 17, a concurrent processing inhibition constraint control unit 18, and an optimal production schedule generation unit 1.
9 and a main control unit 20. Each of these parts 10
Reference numeral 20 denotes a functional element realized by the CPU 21 in the computer shown in FIG. 2 executing the optimization scheduling program 241.

The item-specific optimizing unit 10 calculates the partial optimization problem of the equation (15) for each item i under the constraint of the transition of inventory and the transition of the remaining setup time by the optimal cost function of the equation (20). Is used to solve independently of other items, and perform an operation to find the solution. The stock amount extraction unit 11 extracts a stock amount necessary for the operation of the item-specific optimization unit 10. The remaining setup time extracting unit 12 extracts a remaining setup time required for the operation of the item-specific optimization unit 10.

The inter-item mechanical interference determining unit 13 determines whether or not the mechanical interference can be regarded as being eliminated from the solution for each item i obtained by the item-specific optimizing unit 10. The inter-item mechanical interference control unit 14 controls the item-specific optimization unit 10 so that the mechanical interference is reduced when the mechanical interference is not eliminated. Specifically, the Lagrange multiplier (μ _{·· t} ^{k ·} ) used to satisfy the machine interference constraint in the optimal cost function used by the item-specific optimization unit 10 is updated.

The work-in-progress inventory sufficiency determination section 15 determines whether or not the work-in-progress inventory is satisfied from the solution for each item i obtained by the item-specific optimization section 10. The work-in-process inventory control unit 16 controls the item-specific optimization unit 10 so that the work-in-process inventory is satisfied when the work-in-process inventory is not sufficient, that is, when the work-in-process inventory is out of stock. Specifically, the Lagrange multiplier (μi _{· t} ^·· ) used to satisfy the work-in-progress in the optimal cost function used by the item-specific optimization unit 10 is updated.

The simultaneous processing prohibition constraint satisfaction determination section 17 determines whether or not the simultaneous processing prohibition constraint (simultaneous processing prohibition condition) is satisfied from the solution for each item i obtained by the item-specific optimization section 10. . Simultaneous processing prohibition constraint satisfaction determination unit 17
Controls the item-specific optimization unit 10 so that the simultaneous processing prohibition constraint is satisfied when the simultaneous processing prohibition constraint is not satisfied. Specifically, the Lagrange multiplier (μ _ijt ^kl ) used to satisfy the simultaneous processing prohibition constraint in the optimal cost function used by the item-specific optimization unit 10 is updated.

If it is determined that all the constraints (conditions) of mechanical interference, prohibition of stockout of work-in-process inventory, and prohibition of simultaneous processing are all satisfied, the optimum production schedule generation unit 19 uses the solution obtained at that time. To generate a production schedule. The main control unit 20 controls the entire production schedule generation device.

The main memory 22 stores the item i and the machine
p at each time slot t for k_it ^k, b_it ^k, c_it ^k
S for each item i and machine k_imax ^k, s_i0 ^k, δ
_i0 ^kData and x for each item i_i0, a_i, τ_ij, ρ_ij, h_i
For storing production data consisting of
Data storage area 221 and each time slot for each item i
R at tot_i0tStorage of shipment request data consisting of
Request storage area 222 for storage and item-specific optimization
Sum of costs up to time slot t calculated by unit 10
V_t(δ_it, s_it, x_it, μ) and the sum V_t(δ_it, s_it,
x_it, μ) _it ^*, s_it ^*, x_it ^*To store
And a cost storage area 223 are secured. here
And δ_it ^*, s_it ^*, x_it ^*Separate area for storing
It is also possible. In the production data storage area 221
Is a product calculated in advance according to the above equations (1) and (2).
R in each time slot t for each eye i_ijt, r_{i ・ t}Each of
Data is also stored.

The main memory 22 further includes an item-specific optimization unit 1
An intermediate result storage area 224 for storing an intermediate result of the solution obtained by solving the optimal partial problem with 0, and a final result storage area 22 for storing the final result as well.
5 and a production schedule storage area 226 for storing the production schedule generated by the optimal production schedule generation unit 19.

Next, the operation of the configuration of FIG. 1 will be described with reference to the flowchart of FIG.
This will be described with reference to a chart. First, the production schedule shown in Fig. 1
The optimal production schedule using the rule generator
In each time slot t for item i and machine k,
P_it ^k, b_it ^k, c_it ^kData and item i and machine k
Another s_imax ^k, s_i0 ^k, δ_i0 ^kData and x for each item i
_i0, a_i, τ_ij, ρ_ij, h_iProduction data consisting of
Must be input in advance. Here, this production data
Data in a table format using the keyboard 25, for example.
Shall be.

The input production data is stored in the production data storage area 22 in the main memory 22 under the control of the main control unit 20.
1 is stored. The production data storage area 22
If the production data stored in the storage device 1 is stored in the HDD 23, the production data can be reused when the production data does not need to be changed.

Each time a production schedule needs to be generated, r in the designated time slot t for each item i
_The requested shipment amount data consisting of _i0t is input and stored in the requested shipment amount storage area 222 in the main memory 22. Further, by using this _r i0t, r _ijt at each time slot t for each item i, the respective data of r _{i · t,} wherein the formula (1),
The process of calculating according to (2) is performed by the main control unit 20. Each data of r _ijt and r _{i · t} is stored in the production data storage area 221.

In this state, when a scheduling start instruction is input from the keyboard 25, the main control unit 20 performs an initialization process, and the number of repetitions (repetition number) ν
Is initialized to 0 (step 301). Further, the decision variables δ _it ^kν , s _it ^kν (ie, the boundary value δ _i0 ) at time slot t = 0 for each item i (i （I) and machine k (k 上 の K) in the intermediate result storage area 224. ^kν , s _i0 ^kν )
Is set to an initial value (step 302). Further, a Lagrangian multiplier μ _{·· t} ^{k · ν} in each time slot t (t 別 T) for each machine k (k∈K) and a work item i (i∈
A) Another Lagrange multiplier μ _{i · t} ^{·· ν at} each time slot t (t∈T) and an item j belonging to a subsequent direct connection point
Item i (i∈A ~) that has a simultaneous processing prohibition constraint between
Another machine k (k 機械 K (i)) that can be used to process item i
Another machine l (l @ K
(j)) of another, and the Lagrange multiplier ^μ _ijt klν at each time slot t (T∈T) are both is initialized to 0 (step 303).

Then, the main control unit 20 controls the item-specific optimization unit 10.
Start The item-specific optimization unit 10 first initializes the item i to 1 (step 304). Next, the item-by-item optimization unit 10 solves the partial optimization problem shown in Expression (15) for the item i under the constraints of the work-in-process inventory transition equation (4) and the remaining setup time transition equation (5). The solution is solved using the optimal cost function of equation (20), and the solution δ _it ^kν is obtained (step 305). Here, for the item i, a solution δ _it ^kν (∈t∈T, k∈K (i)) for each time slot t is obtained for each machine k available for processing the item i.

A detailed procedure of step 305 is shown in a flowchart of FIG. Here, the item-specific optimization unit 10
In order to solve the partial optimization problem of the item i, the optimal cost function value V _t (δ _it , s _it , x _it , μ) described below and the optimal decision δ
_It-1 ^* (δ _it , s _it , x _it ).

Therefore, the item-specific optimizing unit 10 first sets the time slot t to 1 (step 401). Then, the item-specific optimizing unit 10 calculates (δ _it , sit,
to x _it), the item i of processing (range of machine k available for production) (k ∈ K (i)) with using the optimal cost function in the equation (20) the optimal cost function value V _t ( δ _it , s _it ,
x _it , μ) and the optimal decision at that time δ _{it -1} ^* (δ _it , s
along with _it , x _it ) are stored in the cost storage area 223 (step 402).

Next, the item-specific optimizing unit 10 increments t by 1 (step 403), and if the incremented t is not larger than n _t (step 40).
4) The processing after step 402 is performed on t after the increment. This is repeated until t = n _t (step 404).

In this state, the item-specific optimizing unit 10
Optimal cost V on storage area 223 _t(δ_it, x_it, s_it)
To t = n_tFollow in reverse. That is, the optimization unit 10 for each item
As described above, first, t = n_tTime slot
All possible δ for_it, s_it, x_itCombination of
(δ_it, s_it, x_itV)_t(δ_it, s_it, x_it, μ)
Looking for a large value (optimum cost), then δ_it, s_it, x_it
Is the optimal solution δ_it ^*, s_it ^*, x _it ^*(Step 405,
406).

Next, the item-specific optimizing unit 10 calculates δ _it ^* , s _it ^* ,
x _it ^* relative to optimal decision ^{_{δ it-1 * (δ i}} t *, s it *, x it *) identifies (step 407), the δ _it ^*, s _it ^*, the equation x _it ^* (5), (4) to be substituted, the optimal cost Vt to reach the immediately preceding time slot s in ^{_{t-1 it-1 *,}} x it-1 * the determined (step 408). This is repeated until t = 1 (step 410) while decrementing t by 1 (step 409).

As described above, the item-specific optimizing unit 10 ^obtains δ _it ^kν (t = 1,..., N _t , k∈K (i)) that gives the optimum cost for the item i (step 30).
5). Then, the item-specific optimization unit 10 ^updates δ _it ^kν in the intermediate result storage area 224 to the latest δit ^kν obtained (step 306).

Next, the item-specific optimization unit 10 enters i by one.
Increment (step 307) and increment it
After i is n_iIs not exceeded (step 30
8), it is determined that there is an unprocessed item,
For item i shown by i after increment,
The processing after step 305 is executed. And i = 1, ...,
n _iSolution δ for all items of_it ^kν({I {I, t}
T, k∈K (i)), the inter-item mechanical interference determination unit 1
3. Work-in-process inventory satisfaction determination unit 15 and simultaneous processing prohibition constraint satisfaction
The foot determination unit 17 is activated.

The inter-item machine interference determination unit 13 determines, for each machine k, all the items i processed (produced) by the machine k.
From the solution δ _it ^kν of ( ^i∈M (k)), δ _it ^k =
The number of mechanical interferences representing the number of timeslots of one time slot is calculated, and it is determined from the number whether or not the mechanical interference can be regarded as being eliminated (step 309). In particular,
The sum of the number of machine interferences over all items and all periods (all planned periods) in the repetition number ν for all machines is n _t × n _k
Calculate the average number of mechanical interference obtained by dividing by (the total number of timeslots x the total number of machines), and determine whether or not the mechanical interference can be regarded as having been eliminated based on whether or not the value is below a threshold value. I do.

Next, in step 309, the work-in-process inventory satisfaction determination unit 15 determines that the work-in-process inventory amount becomes negative for all the work-in-process items i (i （A) (that is, the work-in-stock inventory satisfaction condition is not satisfied). The total number of time slots is obtained, and it is determined from the number whether or not the work-in-process inventory is satisfied. Specifically, for all WIP items, the total number of time slots in which the WIP inventory amount is negative is calculated, and the average WIP inventory shortage ratio obtained by dividing it by the total number of WIP items x the total number of time slots is calculated. Then, it is determined whether or not the work-in-process inventory is satisfied based on whether or not the value is equal to or less than the threshold value. Here, each in-process in-stock amount is calculated in step 30.
It is calculated according to the equation (7) using x _it paired with the corresponding solution δ _it ^kν obtained in step 5.

Next, the simultaneous processing prohibition constraint satisfaction determination section 17
In step 309, all items i (i
∈A ~), from the solution (decision variable) δ _it ^kν , δ _it ^lν for the item i, j in the machine k.l that produces the item i, j in each time slot t, The total number of time slots that did not satisfy the simultaneous processing prohibition constraint in ()) is determined, and whether or not the simultaneous processing prohibition constraint is satisfied is determined from the number. Specifically, all items i (i
∈A ~), the total number of time slots that do not satisfy the simultaneous processing prohibition constraint is calculated, and is calculated for all items i (i∈A
Calculates the average concurrent processing prohibition constraint violation rate obtained by dividing by ~) x the total number of time slots, and determines whether the simultaneous processing prohibition constraint is satisfied based on whether the value is equal to or less than a threshold. .

If at least one of the condition that the machine interference is eliminated, the condition that the in-process inventory is satisfied, and the condition that the simultaneous processing prohibition constraint is satisfied is not satisfied, the process is repeated. Number (number of iterations) ν
Is incremented by 1 (step 310), and the corresponding control unit among the inter-item mechanical interference control unit 14, the work-in-process inventory control unit 16, and the simultaneous processing prohibition restriction control unit 18 is activated. Here, the inter-item mechanical interference control unit 14 does not satisfy the inter-item mechanical interference control unit 14 when the mechanical interference has not been eliminated, the in-process inventory control unit 16 does not satisfy the in-process inventory amount when the in-process inventory amount is not satisfied, and does not satisfy the simultaneous processing prohibition constraint. At this time, the simultaneous processing prohibition constraint control unit 18 is activated. When none of the above three conditions are satisfied, the inter-item mechanical interference control unit 14
WIP inventory control unit 16 and simultaneous processing prohibition constraint control unit 18
Is all started.

When the inter-item mechanical interference control unit 14 itself is activated, the Lagrange multiplier μ _{· t} used for mechanical interference is activated.
^{k · ν} is updated (adjusted) according to the above equation (15), and is notified to the item-specific optimization unit 10 (step 311).

On the other hand, when the work-in-progress inventory control section 16 itself is started, in step 311, the Lagrangian multiplier μ _{i · t} ^{·· ν} used to satisfy the work-in-progress inventory is updated in accordance with the above equation (16). Adjustment), and then optimize by item 1
Notify 0.

When the simultaneous processing prohibition constraint control unit 18 is activated, in step 311 the Lagrange multiplier μ _ijt used for satisfying the simultaneous processing prohibition constraint is set.
^klν is updated (adjusted) according to the above equation (18), and is notified to the item-specific optimization unit 10.

As a result, the updated Lagrange multipliers, ie, the Lagrange multipliers μ _{·· t} ^{k · ν} and / or μ _{i · t}
^{· · [Nu} and or ^μ _ijt klν with step 305 is executed the number of repeats material, product category, machine-specific solutions ^δ _it kν
Is calculated for each time slot.

Eventually, the inter-item mechanical interference judging section 13 judges that the mechanical interference can be regarded as being eliminated, and the in-process inventory stock determining section 15 judges that the in-process inventory amount has been satisfied. When the prohibition constraint satisfaction determination unit 17 determines that the simultaneous processing prohibition constraint is satisfied,
The solution δ _it ^kν for each item and each machine at that time is stored in the final result storage area 225, and the optimum production schedule generation unit 19 is started.

The optimum production schedule generation unit 19 generates a production schedule based on the solution δ _it ^kν for each item and each machine stored in the final result storage area 225,
It is stored in the production schedule storage area 226. As described above, the solution δ _it ^kν for each item and each machine is represented by the 0-1 variable. Then, in the time slot t engraved on the time axis, if the item i is processed (set up or produced) by the machine k in the slot, it is 1;
(See FIG. 6B). Therefore, the solution δ _it
^The lot size and the time position of each lot can be generated for each item and machine by the arrangement of ^1s in ^kν and their time position. In addition, all machines are divided into a set of machines for each VF member company. As is apparent, the solution δ _it of the item i of the machine k owned by the member company m
^If there is a time slot in which ^kν is 1, the company m has won the operation on the item i on the machine k (at the price a _i per unit quantity). That is, in the present embodiment, the auction based on the market principle is automatically performed according to the optimization algorithm.

The temporal position of a lot gives information for determining the order of the lot in an executable schedule. That is, in the present embodiment, it can be considered that the mechanical interference of the solution (schedule) between the items has been resolved, the in-process inventory is determined to be sufficient, and the simultaneous processing prohibition constraint is satisfied. When the solution δ _it ^kν is determined, the lot size and the lot order can be generated at the same time.

The production schedule stored in the production schedule storage area 226 is displayed on the display 26 in FIG.
Are printed out from a printer (not shown) in response to a print instruction input from the keyboard 25 or automatically. Further, this production schedule can be used as it is or as control information in a production line by predetermined data conversion. In this production schedule, for example, machine k Separately, solution [delta] _it ^k of each item i using (more corresponding s _it ^k), operation of the machine k for each time slot t (production or setup) /
Non-operation (idle), work-in-process inventory, and the like can be represented.
Also, by using δ _it ^k , each (own machine k)
It is also possible to calculate the item i (operation) of the company, the profit for each machine k, the total amount of profits for all items (operations) of each company (owning the machine k) and all machines.

In the above-described embodiment, the simultaneous processing prohibition restriction is considered as one of the mutual relation restrictions. However, depending on the product to be handled, the simultaneous processing prohibition restriction does not exist between any items. It is possible. In this case, A ~ may be an empty set, but depending on the VF, the simultaneous processing prohibition constraint itself may be excluded from consideration.

The present invention is not limited to the above-described embodiment, and can be variously modified in an implementation stage without departing from the gist of the invention. Further, the embodiments include inventions at various stages, and various inventions can be extracted by appropriately combining a plurality of disclosed constituent elements. For example, even if some components are deleted from all the components shown in the embodiment, the problem described in the column of the problem to be solved by the invention can be solved, and the effects described in the column of the effect of the invention can be solved. If you get
A configuration from which this configuration requirement is deleted can be extracted as an invention.

[0168]

As described above in detail, according to the present invention, it is required to coordinate operations between machines, processes, and companies, and to coordinate interests between companies with the adjustment of the operations. In order to find the optimal solution to the problem of scheduling, that is, the problem of maximizing the profit of each company under various constraints including inter-company constraints, the problem of maximizing the profit of the entire VF (global optimization) Focusing on the fact that it is the same as finding the optimal value of (Problem) and maximizing the profit of the entire VF, that is, the dimensional optimization problem for the number of items is a one-dimensional partial optimization problem for each item. Instead of solving the problem that maximizes the profit of each company, instead of changing the viewpoint of grasping the problem from grasping each company's machine and item by machine to grasping each machine's profit, In production systems One-dimensional item-by-item optimization of total cost including, for each item processed in each step, a first penalty cost corresponding to inter-item mechanical interference and a second penalty cost corresponding to fulfillment of WIP inventory Since the partial optimization problem has been solved, the virtual fab is able to coordinate the operations between machines, processes, and companies, and the related interests between companies. Production schedule can be generated.

[Brief description of the drawings]

FIG. 1 is a diagram showing a functional block configuration of a virtual fab production schedule generation device according to an embodiment of the present invention.

FIG. 2 is a block diagram of a computer for realizing the production schedule generating device of FIG. 1;

FIG. 3 is a flowchart for explaining the operation of the configuration of FIG. 1;

FIG. 4 is a flowchart for explaining a detailed procedure of step 305 in FIG. 3;

FIG. 5 is a diagram for explaining a relation of a state transition from (δ _it-1 ^k , s _it-1 ^k ) to (δ _it ^k , s _it ^k ).

FIG. 6 is a state transition diagram of (δ _it ^k , s _it ^k ).

FIG. 7 is a diagram for explaining echelon inventory storage costs.

FIG. 8 is a diagram for explaining a multi-item, multi-step production system.

[Explanation of symbols]

10: Product-specific optimization department 11: Inventory amount extraction unit 12: remaining setup time extraction unit 13: Inter-item mechanical interference determination unit 14. Inter-item mechanical interference control unit 15: Work-in-process inventory satisfaction judgment section 16: WIP inventory control unit 17: Simultaneous processing prohibition constraint satisfaction determination unit 18: Simultaneous processing prohibition constraint control unit 19: Optimal production schedule generation unit 20: Main control unit 21 ... CPU 22: Main memory 221: Production data storage area 222: Shipment request amount storage area 223: Cost storage area 224: Intermediate result storage area 225: Final result storage area 226: Production schedule storage area 241: Optimized scheduling program 242 ... CD-ROM

Claims (11)

[Claims] 1. A virtual fab for generating, by a computer, a production schedule applied to a virtual fab multi-item multi-step production system in which a plurality of processes owned by members are processed in a plurality of processes by a plurality of machines. Total cost including a first penalty cost corresponding to the inter-item mechanical interference and a second penalty cost corresponding to the fulfillment of the work-in-process inventory for each item processed in each of the processes. Solving the one-dimensional sub-optimization problem for each item independently of other items independently of each other, for each item and each machine, and for each time slot in which the planning period is divided at a fixed time interval, The solution is a decision variable that indicates whether the timeslot is being used by the machine to produce the item. A solution interference step; a machine interference determination step of determining the magnitude of the degree of mechanical interference in the same machine between the respective items with respect to the solution for each time slot for each machine for each item obtained in the solution step; A work in process inventory sufficiency determining step of determining whether or not the work in process inventory is satisfied for the solution for each time slot for each item by machine determined by the item, and a degree of mechanical interference between the respective items by the mechanical interference determining step. If it is determined to be large, the first penalty cost is updated so as to reduce the degree of the mechanical interference, and it is determined that the in-process inventory is not satisfied by the in-process inventory satisfaction determination step. In this case, the second penalty cost is updated so as to satisfy the work-in-process inventory, and the solution step is re-executed each time. An update step, when the degree of mechanical interference between the respective items is determined to be small by the mechanical interference determination step, and when it is determined that the in-process inventory is satisfied by the in-process inventory determination step, Generating a production schedule based on the solution for each time slot for each item and machine obtained in the solution step. 2. In the solving step, in addition to the first and second penalty costs, among the items processed in each of the steps, subsequent processing is not started unless the processing of the item is completed. For one item that does not exist, solve the one-dimensional partial optimization problem for each item that optimizes the total cost including the third penalty cost corresponding to satisfying the simultaneous processing prohibition constraint, independently of the other items, The simultaneous processing prohibition constraint satisfaction determining step of determining whether or not the simultaneous processing prohibition constraint is satisfied for the solution for each time slot for each item and for each machine obtained in the solution step, and in the updating step, If it is determined in the prohibition constraint satisfaction determination step that the simultaneous processing prohibition constraint is not satisfied, the third page is set to satisfy the simultaneous processing prohibition constraint. Update the Luthi cost, virtual fab for production schedule creation method according to claim 1, wherein the to rerun every time the solution step. 3. A virtual fab for generating, by a computer, a production schedule applied to a virtual fab multi-item, multi-step production system in which a plurality of machines owned by a member process items corresponding to the respective steps in a plurality of steps. A production schedule generation method, wherein for each item processed in each of the processes, the constraint on the mechanical interference between the items is relaxed by weighting with the first Lagrangian multiplier, and the constraint on the satisfaction of the work-in-process inventory is the second. Solving the one-dimensional partial optimization problem alleviated by weighting with the Lagrangian multiplier independently of other items, for each item and each machine, and for each time slot in which the planning period is divided at fixed time intervals The time slot is used by the machine for the production of the item. A solution step of obtaining a decision variable indicating whether or not there is a solution, and determining the magnitude of the degree of mechanical interference in the same machine between the items with respect to the solution for each time slot for each machine for each item obtained in the solution step. A machine interference determination step of determining; a work in process inventory satisfaction determination step of determining whether or not a work in process inventory is satisfied for a solution for each time slot for each item of machine determined in the solution step; and the machine interference determination step When it is determined that the degree of mechanical interference between the respective items is large, the first Lagrangian multiplier is updated so as to reduce the degree of mechanical interference, and the work-in-progress inventory sufficiency determining step determines the work-in-process inventory sufficiency. If it is determined that the product inventory is not satisfied, the second Lagrangian multiplier is updated so as to satisfy the work-in-process inventory, An update step of re-executing the solution step each time, and the degree of mechanical interference between the respective items is determined to be small by the mechanical interference determination step, and the in-process inventory is determined by the in-process inventory determination step. Generating a production schedule based on the solution for each time slot for each item and machine obtained in the solution step at the time of the solution step. Production schedule generation method. 4. A constraint on mechanical interference between the items,
Among the decision variables for each item and machine in an arbitrary time slot, the correlation constraint is that it is possible to indicate that at most one decision variable for the same machine is used for production. Claim 3
The production schedule generation method for the virtual fab described. 5. The method according to claim 1, wherein the solving step includes: converting the one-dimensional partial optimization problem to an item i in an arbitrary time slot t.
And the decision variable of the machine k is δ _it ^k , the first Lagrangian multiplier is μ _t ^k , the second Lagrangian multiplier is μ _it , and a vector having a Lagrangian multiplier including both the Lagrangian multipliers is μ. At the same time, at the end of the time slot t, instead of the cumulative shipment amount actually passed to the next process of the item i, the shipment request amount from the customer in each time slot up to the time slot t of the item i is calculated. The apparent inventory status calculated using the accumulated amount developed for the item i in the time slot t, and the remaining setup time required for setting up the item i,
Each state variable x _it, as s _it, the optimal cost function Vt representing the sum of the costs incurred with the taken optimum determined at each time slot until the time slot t
5. The production schedule generation method for a virtual fab according to claim 4, wherein the method is solved by (δ _it , x _it , s _it , μ). 6. A cost is calculated by the optimal cost function, first and penalty cost corresponding to the royalty of the machine which is calculated on the basis of the first Lagrange multiplier mu _t ^k, the second Lagrangian A second penalty cost corresponding to the machine usage fee calculated based on the multiplier μ _it and an echelon inventory storage cost per time slot h for a value newly added by processing the item i.
6. The virtual fab production schedule generating method according to claim 5, further comprising a cost determined by _i and the state variable x _it . 7. In the solving step, in addition to mitigation by weighting using the first and second Lagrangian multipliers, among the items processed in each of the steps, if the processing of the item is not completed, the subsequent processing is performed. For an item that does not start, a one-dimensional partial optimization problem in which the constraint on simultaneous processing prohibition, which expresses this, has been relaxed by weighting with a third Lagrange multiplier is solved independently of other items. The method further comprises a simultaneous processing prohibition constraint satisfaction determination step of determining whether or not the simultaneous processing prohibition constraint is satisfied for the solution for each time slot obtained for each item-by-item and machine-specific solution. In the updating step, the simultaneous processing prohibition constraint satisfaction determination is performed. If it is determined in the step that the simultaneous processing prohibition constraint is not satisfied, the simultaneous processing prohibition constraint is satisfied. The third update the Lagrange multiplier, virtual fab for production schedule creation method according to claim 3, wherein the to rerun every time the solution step. 8. A computer for generating a production schedule applied to a virtual fab multi-item multi-step production system in which an item corresponding to each step is processed in a plurality of steps by a plurality of machines owned by a member. A program comprising: a total cost including a first penalty cost corresponding to inter-item mechanical interference and a second penalty cost corresponding to fulfillment of work-in-process inventory for each item processed in each of the processes. Solving the one-dimensional sub-optimization problem for each item independently of other items independently of each other, for each item and each machine, and for each time slot in which the planning period is divided at a fixed time interval, A solution that takes as a solution a decision variable that indicates whether the timeslot is being used by the machine to produce the item Step, a machine interference determination step of determining the magnitude of the degree of mechanical interference in the same machine between the respective items with respect to the solution for each time slot for each machine for each item obtained in the solution step, A work-in-progress inventory sufficiency determining step of determining whether or not the work-in-process inventory is satisfied for the solution for each time slot for each item-specific machine, and when the degree of mechanical interference between the respective items is large by the mechanical interference determining step. If it is determined, the first penalty cost is updated so as to reduce the degree of the mechanical interference, and if it is determined that the in-process inventory is not satisfied by the in-process inventory determination step, Updating the second penalty cost so as to satisfy the work-in-process inventory, and re-executing the solution step each time. If the degree of mechanical interference between the respective items is determined to be small by the mechanical interference determination step, and if the in-process inventory is determined to be satisfied by the in-process inventory determination step, Generating a production schedule based on the solution for each time slot for each item and machine obtained in the solution step. 9. A computer for generating a production schedule applied to a virtual fab multi-item multi-step production system in which a plurality of processes owned by a member process items corresponding to the respective steps in a plurality of processes. A program, wherein: for each item processed in each of the steps, a constraint on mechanical interference between items is relaxed by weighting with a first Lagrangian multiplier, and a constraint on satisfaction of work-in-process inventory is second. Solving the one-dimensional partial optimization problem alleviated by weighting with the Lagrangian multiplier independently of other items, for each item and each machine, and for each time slot in which the planning period is divided at fixed time intervals Whether the time slot has been used by the machine for the production of the item. And a machine for determining the magnitude of the degree of mechanical interference in the same machine between the items with respect to the solution for each time slot for each machine for each item obtained in the solution step. An interference determination step, a work in progress inventory determination step of determining whether or not the work in process inventory is satisfied for the solution for each time slot for each item of machine determined in the solution step, and When it is determined that the degree of the mechanical interference between the items is large, the first Lagrangian multiplier is updated so as to reduce the degree of the mechanical interference, and the in-process inventory is determined by the in-process inventory satisfaction determination step. If it is determined that the in-process inventory is not satisfied, the second Lagrangian multiplier is updated so as to satisfy the work-in-process inventory, and each time, An update step of re-executing the notation step; and the mechanical interference determining step determines that the degree of mechanical interference between the respective items is small, and the work-in-process inventory fulfillment determining step satisfies the work-in-process inventory. And generating a production schedule based on the solution for each time slot for each item and for each machine determined in the solution step at that time. 10. A production for a virtual fab which generates a production schedule applied to a virtual fab multi-item multi-step production system in which a plurality of machines owned by a member process a plurality of processes corresponding to the respective processes in a plurality of processes. A schedule generating apparatus, which optimizes a total cost including a first penalty cost corresponding to inter-item mechanical interference and a second penalty cost corresponding to fulfillment of a work-in-process inventory for each item processed in each of the processes. The one-dimensional partial optimization problem for each item to be converted is solved independently of the other items, and the time is calculated for each item and each machine, and for each time slot in which the planning period is divided at fixed time intervals. Item-specific optimization that takes as solution a decision variable that indicates whether the slot is being used by the machine to produce the item Means, and machine interference determining means for determining the magnitude of the degree of mechanical interference in the same machine between the respective items with respect to the solution for each time slot for each item machine obtained by the item-specific optimizing means; WIP inventory sufficiency determining means for determining whether or not the WIP inventory is satisfied for the solution for each time slot for each machine obtained for each item obtained by the different optimizing means, and a machine between the respective items by the machine interference determining means. When it is determined that the degree of interference is large, the first penalty cost is updated so as to reduce the degree of the mechanical interference and the mechanical interference control means for controlling the item-specific optimizing means; If it is determined that the in-process inventory is not satisfied by the in-stock inventory determination unit, the second penalty cost is updated so as to satisfy the in-process inventory. A work-in-progress inventory control means for controlling the item-by-item optimization means, and a degree of mechanical interference between the respective items is determined to be small by the mechanical interference determination means, and the work-in-progress inventory is determined by the work-in-process inventory satisfaction determination means. When it is determined that the stock is sufficient, at that time, an optimal production schedule generation for generating an optimal production schedule based on the solution for each time slot for each machine for each item obtained by the optimization means for each item. Means for generating a production schedule for virtual fabs. 11. Production for a virtual fab which generates a production schedule applied to a virtual fab multi-item multi-step production system in which a plurality of machines owned by a member process items corresponding to the respective steps in a plurality of steps. A schedule generation device, wherein, for each item processed in each of the processes, a constraint on mechanical interference between items is reduced by weighting with a first Lagrangian multiplier, and a constraint on satisfaction of work-in-process inventory is reduced by a second Lagrangian. Solving the one-dimensional partial optimization problem, which has been alleviated by the weighting by the multiplier, independently of other items, for each item and each machine, and for each time slot in which the planning period is divided at fixed time intervals, Indicates whether the timeslot is being used by the machine to produce the item Item-specific optimizing means for acquiring the decision variable as a solution; and magnitude of the degree of mechanical interference in the same machine between the respective items with respect to the solution for each time slot for each item-specific machine obtained by the item-specific optimizing means. Interference determination means for determining, and work-in-stock inventory satisfaction determination means for determining whether or not the work-in-process inventory is satisfied for the solution for each time slot for each machine for each item obtained by the optimization means for each item, When the degree of mechanical interference between the respective items is determined to be large by the mechanical interference determining means, the first Lagrangian multiplier is updated so as to reduce the degree of mechanical interference, and the item-specific optimizing means is updated. When the in-process inventory is determined to be unsatisfied by the in-process inventory sufficiency determining means, the in-process inventory is satisfied. A work-in-progress inventory control means for updating the second Lagrangian multiplier to control the item-specific optimizing means, and the mechanical interference determining means determines that the degree of mechanical interference between the items is small, and When it is determined that the WIP inventory is satisfied by the WIP inventory sufficiency determination means, at that time, based on the solution for each time slot for each machine for each item obtained by the optimization means for each item. A production schedule generating apparatus for a virtual fab, comprising: