JP5238327B2 - Multi-item multi-stage dynamic lot size scheduling method with production quota - Google Patents

Description

  The present invention is applied to a multi-item multi-stage process production system in which items corresponding to each process are processed in a plurality of processes by a plurality of machines, and at least one machine or process can be changed over with a setup. The present invention relates to a multi-item multi-stage dynamic lot size scheduling method suitable for generating a production schedule to be generated, and in particular, a production schedule for processing items belonging to the same family within a production frame (processing time zone) of the family. The present invention relates to a multi-item multi-stage process dynamic lot size scheduling method with a production frame, which is suitable for generating a product.

  In general, in a multi-item multi-stage production system in which items corresponding to each process are processed in a plurality of processes by a plurality of machines, and at least one machine or process is capable of switching items with setup. In order to generate a simple production schedule, a technique called multi-item multi-stage process dynamic lot size scheduling is adopted.

For example, Patent Document 1 is not aware of enumerating each aspect of various decisions included in the problem of scheduling of multi-item multi-stage processes, and requires artificial constraints. However, a method for generating an economical and reasonable feasible schedule by solving the various aspects from the viewpoint of overall optimization has been proposed.
JP 2002-328977 A

  However, when the number of items to be handled becomes enormous, it becomes difficult to adjust individual setups, and various problems such as time loss and increase in work in progress increase. It becomes difficult.

  In order to deal with this problem, for example, a similar group of items is considered as a family, and for a group of items belonging to the same family, the production frame (processing time zone) of the family is secured as long as the delivery date allows, and the items are grouped together It is desirable to plan to process. However, such a plan is not easy to implement.

  The present invention has been made in view of the above circumstances, and a multi-item multi-stage process operation with a production frame that can solve the existing scheduling problem by introducing a method for securing a production frame for a family of item groups. It is an object of the present invention to provide a general lot size scheduling method.

The multi-item multi-stage dynamic lot size scheduling method according to the present invention processes an item corresponding to each process in a plurality of processes by a plurality of machines, and at least one machine or process is associated with a setup. It can be switched , and it is applied to a multi-item multi-stage production system that secures a production frame that is the processing time zone of the item group defined as a family in each process and can process the item group together in the production frame. This is a multi-item multi-step dynamic lot size scheduling method in which a production schedule is generated by a computer, assuming that a virtual machine that processes a virtual item that is a material of a real item processed by a real machine is in the previous step. Process an item multistage production system as a scheduling target, at least within the virtual item and the production frame of the virtual item. In addition to setting information indicating the relationship with the actual item, 1) a machine interference prohibition restriction that prohibits the real machine or virtual machine from processing a plurality of items simultaneously, and 2) a virtual item that is the material of the actual item or Out-of-stock restrictions on in-process items that prohibit out-of-stock items, 3) Out-of-stock restriction that prohibits material items from becoming virtual materials, and 4) Pre-defined actual machine or Items that generate a schedule using a Lagrangian function having a Lagrange function having a Lagrange multiplier corresponding to each constraint, and a constraint setting step for setting a machine-specific in-process constraint that limits the in-process amount of a set of items for each virtual machine If there is another schedule generation step and the violation amount exceeds the threshold in any of the constraints, the corresponding Lagrangian function And having a Lagrange multiplier updating step of updating the Ju multiplier.

The program according to the present invention can process items corresponding to each process in a plurality of processes by a plurality of machines, and can switch items with setup in at least one machine or process. For securing multi-item multi-stage dynamic lot size scheduling in a multi-item multi-stage production system that secures a production frame that is a processing time zone of an item group defined as a family and can process the item group together in the production frame A multi-item multi-stage production system that assumes that a virtual machine that processes a virtual item that is a material of a real item processed by a real machine is in a previous stage, and that is scheduled for at least a virtual item. In addition to setting information indicating the relationship with the actual item to be processed within the production frame of the virtual item, 1) the actual machine Or a machine interference prohibition constraint that prohibits a virtual machine from processing a plurality of items at the same time, 2) a virtual item that is the material of an actual item, or an out-of-process prohibition constraint for an in-process item that prohibits an out-of-stock item, and 3 ) Material shortage prohibition restriction that prohibits the occurrence of material shortage in the actual item that is the material of the virtual item, and 4) Machine-specific processing that restricts the in-process amount of the set of items for each real machine or each virtual machine The constraint setting function that sets the constraint, the schedule generation function by item that generates a schedule using a Lagrangian function having a Lagrange multiplier corresponding to each constraint, and the amount of violation exceeds the threshold in any of the constraints A Lagrangian multiplier update function for updating a corresponding Lagrangian multiplier in the Lagrangian function when there is one; To.

The multi-item multi-stage dynamic lot size scheduling apparatus according to the present invention processes items corresponding to each process in a plurality of processes by a plurality of machines, and at least one machine or process is associated with a setup. It can be switched , and it is applied to a multi-item multi-stage production system that secures a production frame that is the processing time zone of the item group defined as a family in each process and can process the item group together in the production frame. A multi-item multi-stage dynamic lot size scheduling device that generates a production schedule by a computer, assuming that a virtual machine that processes a virtual item that is the material of a real item processed by a real machine is in the previous stage. Process an item multistage production system as a scheduling target, at least within the virtual item and the production frame of the virtual item. In addition to setting information indicating the relationship with the actual item, 1) a machine interference prohibition restriction that prohibits the real machine or virtual machine from processing a plurality of items simultaneously, and 2) a virtual item that is the material of the actual item or Out-of-stock restrictions on in-process items that prohibit out-of-stock items, 3) Out-of-stock restriction that prohibits material items from becoming virtual materials, and 4) Pre-defined actual machine or Items that generate a schedule using a Lagrange function that has a Lagrange multiplier that has a Lagrange multiplier corresponding to each constraint, and a constraint setting means that sets in-process constraints by machine that limit the in-process amount of a set of items by virtual machine If there is another schedule generation means and the violation amount exceeds a threshold value in any of the constraints, the corresponding Lagrangian multiplication in the Lagrangian function Characterized by comprising a Lagrangian multiplier update means for updating the.

  According to the present invention, it is possible to solve an existing scheduling problem by introducing a method for securing a production frame for a family of item groups.

  Embodiments of the present invention will be described below with reference to the drawings.

"Overview"
In the present embodiment, a multi-item multi-stage dynamic lot size scheduling method with a production frame is proposed. In order to solve the conventional problem, in this embodiment, similar item groups (for example, item groups using the same parts, dyes, chemicals, etc. as materials) are regarded as families, and item groups belonging to the same family are due for delivery. The goal is to secure a family production frame (processing time zone) as much as possible and plan to process them together.

  In this embodiment, in order to overcome the difficulty of the planning, in addition to the actual machine that processes the actual item, the concept of the virtual machine that processes the virtual item (family item) that is the material of the actual item is changed. Introduce (ie, expand the existing ternary relationship of “when (t), which item (i), which machine (k)”) to define relationships between processes including virtual machines and family items. ) And solve the existing multi-item multi-stage dynamic lot size scheduling problem. At that stage, we will pay particular attention to the need for a material shortage prohibition restriction that prohibits a material shortage from occurring in an actual item as a material of a family item. By solving the scheduling problem including this restriction, the necessary conditions of the original problem (although the sufficient condition is not satisfied) are satisfied.

  In addition, the solution has temporal redundancy or flexibility (it is allowed to shift the processing time period back and forth), and he uses it to heuristically respond to the production quota schedule of family items. It is proposed to synchronize the processing schedule of the actual items.

  FIG. 1 is a diagram showing an example of a main functional configuration of a multi-item multi-stage process dynamic lot size scheduling apparatus according to an embodiment of the present invention. Note that the functional configuration is not limited to the example of FIG. 1 and can be appropriately modified and implemented.

  The scheduling apparatus of FIG. 1 has the problem of scheduling (multi-item multi-stage dynamic lot size scheduling) for switching production by classifying various orders into a plurality of items in a multi-process production system, that is, high It solves the dimension time optimization problem and determines the optimal schedule.

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

The computer shown in FIG. 2 can also read into the computer information stored in advance in, for example, a magnetic disk device (hereinafter referred to as HDD) 23 as an external storage device and, for example, a CD-ROM 242 as a recording medium. And a CD-ROM device 24. In the example of FIG. 2, the CD-ROM 242 is optimal for performing multi-item multi-stage dynamic lot size scheduling in a production system that produces a plurality of items by a plurality of processes (multi-stage processes) and multiple machines (multi-equipment). A scheduling program 241 is stored in advance. This optimization scheduling program 241, the CD-ROM device 24 is loaded in a computer from the CD-ROM 242, it is assumed that that is stored in the HDD 23 (installation). When the CPU 21 reads the optimization scheduling program 241 from the HDD 23 onto the main memory 22 and executes the program 241, various functions of the scheduling apparatus of FIG. 1 are realized.

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

  The scheduling apparatus of FIG. 1 includes functions such as a setting unit 11, an item-specific schedule generation unit 12, a constraint violation monitoring unit 13, a Lagrange multiplier update unit 14, and an executable schedule generation unit 15.

  The setting unit 11 is a virtual machine (hereinafter may be referred to as “family”) that processes a virtual item (hereinafter referred to as “family item” or “F item”) that is a material of an actual item processed by the real machine. For multi-item multi-stage production systems that are assumed to be in the previous process, set various mathematical models used for scheduling and data used for them (for example, information indicating parent-child relationships between items) , Information indicating the correspondence between machines and items, information indicating the relationship between family items and actual items to be processed within the production frame of the family items, various constraint conditions, Lagrange multipliers This is a function for performing setting etc.). Regarding the constraint conditions, the setting unit 11 is 1) a machine interference prohibition constraint that prohibits the real machine or virtual machine from processing a plurality of items simultaneously, and 2) the family item or the real item that is the material of the real item is out of stock. 3) Restrictions on out-of-stock items for work-in-progress items that are prohibited, 3) Restrictions on material shortage that prohibits material shortages from occurring in the actual items that are the materials of family items, and 4) Pre-defined actual machine or virtual machine It has a function of setting a machine-specific work restriction that restricts the work amount of a set of items.

  The item-specific schedule generation unit 12 is a function that generates, for each item, a schedule using a Lagrangian function having a Lagrange multiplier corresponding to each constraint.

  The constraint violation monitoring unit 13 monitors whether there is a violation amount exceeding a threshold value in any of the constraints. If there is a violation amount exceeding the threshold value, the constraint violation monitoring unit 13 corresponds to the Lagrange function according to the violation amount. This is a function for instructing the Lagrange multiplier update unit 14 to update the Lagrange multiplier.

  The Lagrange multiplier update unit 14 is a function of updating a corresponding Lagrange multiplier in the Lagrange function when an instruction is issued from the constraint violation monitoring unit 13.

  The executable schedule generating unit 15 is a function that generates an executable schedule based on the item-specific schedule adjusted through the update of the Lagrange multiplier. The executable schedule generation unit 15 executes an executable schedule through a heuristic algorithm that sequentially resolves at least the violation of the machine interference prohibition constraint, the violation of the out of stock prohibition constraint of the work in progress, and the violation of the material shortage prohibition constraint. It has a function to generate. That is, the executable schedule generation unit 15 includes a lot start / end time acquisition unit 16, a machine interference prohibition constraint violation resolution unit 17, an in-process item out-of-stock prohibition constraint violation resolution unit 18, and a material shortage prohibition constraint violation resolution unit 19. Includes functionality.

  The lot start / end time acquisition unit 16 has a function of grasping the start time and end time of all lots for each machine item. The machine interference prohibition constraint violation resolving unit 17 is a function for resolving the violation of the machine interference prohibition constraint by moving the lot causing the machine interference for each machine item. The in-process item out-of-stock prohibition constraint violation resolving unit 18 is a function for solving violation of the out-of-process item out-of-stock prohibition constraint by changing the processing speed or order of the lot that is out of stock for each item. . The material shortage prohibition constraint violation resolving unit 19 is a function for resolving the violation of the material shortage prohibition constraint by synchronizing the processing of the virtual item and the processing of the real item.

  Here, FIG. 3 shows an example of a general configuration when the concept of the virtual machine is introduced into the multi-item multi-stage production system to be scheduled.

  In the figure, a solid circle represents an actual item, and a dotted circle represents a family item. In the example of the figure, the family items are 7 items in total of F items 1 to 7, the actual items are 14 items in total of actual items 1 to 14, and the actual items 8 to 14 are final products (items).

  In addition, a solid line square represents a real machine, and a dotted line square represents a virtual machine. In the example of the figure, the virtual machine 1 processes the F items 1 to 3, the virtual machine 2 processes the F items 4 to 7, the real machine 1 processes the real items 1 to 7, and the real machine 2 Process items 8-14.

  In addition, a solid line arrow connecting the solid line circles represents a parent-child relationship between items. In the example of the figure, the actual item 1 and the actual item 8 are in a parent-child relationship.

  A dotted arrow connecting a dotted circle and a solid circle represents a family relationship. In the example of the figure, actual items 1 to 3 belong to family item 1 and actual items 4 and 5 belong to family item 2.

  For example, regarding the relationship between such family items and actual items, it is expected to generate schedules for processing these actual items within the production quota of the family items by giving out-of-run restrictions on in-process items. Is done. However, in the example of FIG. 3, since the relationship between the family item and the actual item required by the family item is not defined, a desired schedule cannot be generated.

  Therefore, in the present embodiment, as shown in the example of FIG. 4, attention is also paid to the relationship between the family item and the actual item required by the family item, and various constraints such as a material shortage prohibition constraint are related to the relationship. give.

  In the restriction, the actual items 1, 2, and 3 cannot be processed unless they are within the production frame (processing time zone) of the family item 1. Similarly, the actual items 4 and 5 cannot be processed unless they are within the production frame (processing time zone) of the family item 2. Similarly, the real items 6 and 7 are not allowed to be processed unless they are within the production frame (processing time zone) of the family item 3.

  Further, the actual items 8 and 9 cannot be processed unless they are within the production frame (processing time zone) of the family item 4. Similarly, the actual items 10 and 11 are not allowed to be processed unless they are within the production quota (processing time zone) of the family item 5. Similarly, the actual items 12 and 13 are not allowed to be processed unless they are within the production quota (processing time zone) of the family item 6. Similarly, the actual item 14 cannot be processed unless it is in the production frame (processing time zone) of the family item 7.

  First, symbols and mathematical models handled in scheduling for the multi-item multi-stage production system 100 of FIG. 4 are shown below.

<Handling symbols>
(1) Subscript i: represents an item or process number, and its set is I = {1, 2,..., N _I−1 , n _I }. However, i = 0 represents a market (outside the system).

k: represents a machine and its set is K = {1, 2,..., n _K−1 , n _K }.

t: represents a time slot, and its set is T = {1, 2,..., n _T−1 , n _T }.

(2) Set A: Set of work-in-progress items B: Set of predetermined items (for example, by family, by machine equipment)
K (i): Set of machines that can process item i M (k): Set of items that can be processed by machine k P (i): Set of preceding directly connected items (items used for item i) of items i S (i): Set of subsequent directly connected items (items in which item i is used) of items i (including empty sets)
P _R (i): Set of preceding directly connected real item i of family item i S _R (i): Set of family item i made from real item i (3) Input data c _i ^k : Item i in machine k Setup cost per time (given)
h _i : In-process storage cost per 1 ts per unit for the value newly added by processing of item i, ie, ladder stock (in-process) storage cost (given)
p _i ^k : throughput of item i per ts in machine k (given)
r _i0t : External demand or shipment request quantity in time slot t of item i (given)
r _ijt : requirement of item i used to produce item j in time slot t r _{i · t} : requirement of item i in time slot t s _imax ^k : setup time for item i in machine k (place Given)
x _i0 : _trapezoidal inventory quantity of item i at time slot t = 0, that is, initial trapezoidal inventory quantity x _i ^u : upper limit value of ladder inventory quantity of item i (given)
y _i0 : Actual stock quantity of item i at time slot t = 0, that is, initial real stock quantity (given)
δ _i0 ^k : processing state at t = 0 of item i in machine k, that is, initial value (given)
ρ _ij : Required amount of item i per unit of item j (given)
(4) Lagrange multiplier μ _{· t} ^k : Machine interference prohibition restriction at time slot t of machine k Lagrange multiplier μ _it ^· corresponding to equation (8): Out-of-stock prohibition restriction of in-process item at time slot t of in-process item i Lagrange multiplier λ _{· t} ^k corresponding to Eq. (9): Lagrange multiplier λ _it ^· corresponding to material shortage prohibition constraint (10) Lagrange multiplier corresponding to in-process constraint (11) by machine and family (11) 5) Decision variable δ _it ^k : 0-1 decision variable that takes 1 when processing item i by machine k in time slot t and takes 0 otherwise. Where δ _it is a vector with δ _it ^k , k∈K (i) as elements,

And

(6) State variable s _it ^k : Remaining time (unit is ts) of setup of machine k in time slot t of item i, and transition in the range of 0 ≦ s _it ^k ≦ s _imax ^k . Where s _it is a vector whose elements are s _it ^l , l∈K (i),

And

x _it is the amount of ladder stock (in-process) at the end of time slot t of item i, and the definition formula is

However, when the item i is the final item (product), the ladder stock matches the actual stock.

(7) Others v: Number representing calculation iteration << Mathematical model >>
(1) Objective function The objective function is expressed as follows.

(2) Transition equation of the ladder stock quantity The transition equation of the ladder stock quantity x _it is expressed as follows.

In the above equation (3), x _it is the external demand based on the sum of the amount of inventory in the item i at the end of time slot t-1 (the first term on the right side) and the processing amount at the time slot t (the second term on the right side). It is expressed as a value obtained by subtracting the required amount r _{i · t} (third term on the right side) up to the time slot t obtained by development.

(3) Transition equation of setup time The transition equation of setup time is expressed as follows.

Represents.

The remaining setup time (remaining setup time) s _it ^k of each item i in the time slot t is s _it ^k = 0 when the machine (production line) is idle, that is, when the item is switched, that is, the processing state. Becomes s _imax ^k when δ _{i (t−1)} ^k = 0 changes to δ _it ^k = 1. Thereafter, s _it ^k decreases by 1 every time when one time slot elapses until it becomes 0, and thereafter maintains that state until switching occurs again.

The first term on the right side of the above equation (4) indicates the state transition of the remaining setup time that becomes s _imax ^k when δ _{i (t−1)} ^k = 0 is changed to δ _it ^k = 1. (S _{i (t−1)} ^k −1) in the term indicates a state where s _it ^k decreases by 1 every time one time slot elapses.

(4) the range of ladder-like stock amount ladder-like stock quantity x _it ranges may be expressed as follows.

(5) Relationship between various requirements The requirement for item j is expanded to item i as shown in the following equation.

Equation (6) is r _ijt is expressed using r _{j · t} where [rho _ij is reflected, the equation (7) is r _{j · t} is expressed using r _ijt and _r i0t.

In the above equation (7), r _{j · t} is the sum of the requirements r _ijt of the item i used to produce the item j in the time slot t for all items j included in S (i), that is, It is represented by the sum of the amount (first term on the right side) incorporated into the item j in the subsequent process (following direct connection point) and the amount (second term on the right side) drawn outside the system in the time slot t.

(6) Restriction conditions i) Machine interference prohibition restriction Machine k can process at most one item in any time slot t. During the setup and processing of one item, it is not possible to set up another item. This constraint is called a mechanical interference prohibition constraint, and the following equation must be satisfied.

ii) Restriction of out-of-stock item restriction The out-of-stock item is not allowed for any item i in any time slot t. This constraint is called the out-of-stock prohibition constraint for work-in-progress items, and the following equation must be satisfied.

iii) Material shortage prohibition restriction (restriction prohibiting the out of stock of actual items from the previous process used for production quota)
If there is no material, it cannot be processed in production. Therefore, the production quota for a family item must be planned so that at least material shortages do not occur. Furthermore, even if there is material, if it is not processed in the production frame, the actual item is not born.

  In other words, it is a condition necessary for planning the production quota of a family item, and the in-process of an actual item directly connected to the family item (in other words, an actual item directly connected to the actual item directly connected to the family item) The sum of the quantities should not cause material shortages.

  Such a constraint is called a material shortage prohibition constraint, and the following equation must be satisfied.

iv) In-process restrictions by machine and family The in-process quantity of a set of items by machine or family that has been set in advance must not exceed the upper limit. Such restrictions are called machine-specific and family-specific in-process restrictions, and the following equation must be satisfied.

(7) Lagrange function The Lagrange function shown in the following equation is derived by relaxing the above four kinds of constraints.

Where μ _{· t} ^k is a Lagrange multiplier corresponding to the mechanical interference prohibition constraint (8), μ _it ^· is a Lagrange multiplier corresponding to the out-of-stock restriction (9) of the in-process item, and λ _{· t} ^k is a Lagrange multiplier corresponding to the Zaiketsu prohibition constraints (10), λ _it ^· is a Lagrange multiplier corresponding to the machine-specific, family-specific work-in-process constraints (11).

(8) Decomposition of Lagrange function Since the above equation (12) can be added and separated,

The Lagrangian function can be decomposed as follows.

  Therefore, the Lagrangian function minimization problem can be decomposed into the following partial optimization problem.

  Again, a description will be given with reference to FIG. In FIG. 4, the above-mentioned machine interference prohibition constraint (8), in-process item out-of-stock prohibition constraint (9), material shortage prohibition constraint (10), machine-specific, family-specific in-process constraint (11 Each point related to the expression) is indicated. Hereinafter, the meaning of each constraint equation in the example of FIG. 4 will be described for each constraint equation.

-Machine interference prohibition formula (8) For example, actual items 1 to 7 are processed by the actual machine 1. Since all these items cannot be processed simultaneously, this relationship is a machine interference prohibition constraint.

-Out-of-stock restrictions on work items (9) For example, actual items 1 and 8 are in a parent-child relationship. Before making actual item 8, actual item 1 must be completed. This relationship is used as a restriction to prevent out-of-stock items.

-Material shortage prohibition formula (10) The production quota for a family item must be planned so that at least the material shortage does not occur in the material of the item. Furthermore, even if there is material, if it is not processed in the production frame, the actual item is not born. For example, the sum of inventory in a time slot of actual items 1 and 2 must always be greater than the inventory of family item 4 in that time slot. This relationship is a material shortage prohibition constraint.

-In-process restrictions by machine and family (11) If you want to keep the total in-process amount by item belonging to each machine or family below the preset upper limit, operate by machine or family. Treat as a constraint.

  Next, an example of the operation of the multi-item multi-stage process dynamic lot size scheduling apparatus according to the embodiment will be described with reference to FIGS.

  In the present embodiment, setting of various mathematical models used for scheduling and setting of data used for them (for example, information indicating a parent-child relationship between items, information indicating a correspondence relationship between machines and items, family items and After setting the information indicating the relationship with the actual item to be processed in the production quota of the family item, setting various constraint conditions, setting the Lagrange multiplier, etc. Lagrangian relaxation is performed on various interrelation constraints (the above-mentioned expressions (8) to (11)) to derive a Lagrange function (the above-mentioned expression (12)). This Lagrangian function can be decomposed (Equations (13) and (14) above), and the optimization of the problem is to solve the partial optimization problem of each item independently from the others for a given Lagrangian multiplier value. (Equation (15) described above) and updating the Lagrangian multiplier value corresponding to each constraint condition are alternately repeated. By performing such processing, an executable schedule is generated for processing an actual item group belonging to the same family item within the production frame of the family item.

  FIG. 5 is a flowchart illustrating an example of the operation of the entire scheduling apparatus.

Reading various input data into the main memory (step S1)
For example, the setting unit 11 prepares and registers the input data shown in FIGS. Here, FIG. 7 shows the required amount ρ _ij of the item i per unit of the item j, and FIG. 8 shows the production technology data (processing amount p _i ^k , setup time s _imax ^k , setup cost c _i. ^k) shows the FIG. 9, the initial actual inventory amount y _i ^0, work-in-process storage costs h _i, shows the external demand _r i0t, 10, initial悌状amount of inventory x _i0, after parts expansion Required amount r _{i · t} . In the example of FIG. 7, values are entered only for actual items, but values are also entered for family items in practice.

・ Initialization of Lagrange multiplier (step S2)
The setting unit 11 initializes each Lagrangian multiplier.

・ Set the maximum number of repetitions N (step S3)
The setting unit 11 sets the maximum number of repetitions.

-Setting threshold values for each violation amount (step S4)
The setting unit 11 sets a threshold value for each constraint violation amount.

-Variable for counting the number of repetitions N = 1 (step S5)
The setting unit 11 assigns 1 to the variable n for counting the number of repetitions before the calculation is started.

・ Create a schedule for each item (step S6)
The item-specific schedule generation unit 12 generates a schedule for each item. Specifically, the restrictions on the transition of the ladder stock quantity (previous formula (3)), the transition of the setup time (previously formula (4)) and the range of the ladder stock quantity (previously formula (5)) Originally, the partial optimization problem (formula (12)) described above is solved for a given Lagrangian multiplier value, and the solution δ _it ^k is stored (updated) in a predetermined storage area.

・ Calculation of each violation amount (step S7)
The constraint violation monitoring unit 13 calculates a violation amount for each constraint.

-Judgment of each constraint violation amount: have all been resolved? (Step S8)
If all the constraint violation amounts calculated in step S7 are all zero, an executable schedule has been generated, and the process proceeds to step S14. If any of the constraint violation amounts exceeds 0, the process proceeds to step S9 in order to determine whether it is equal to or less than the set threshold value.

・ Is each constraint violation amount less than the set threshold? (Step S9)
If all the threshold values of the constraint violation amounts set in step S4 are below, the process proceeds to step S13. If any one of the threshold values is not lower, the process proceeds to step S10.

-Determination of the number of repetitions: n> N? (Step S10)
If the number of repetitions of calculation is below the set upper limit value N, the process proceeds to step S11. If the upper limit value N is exceeded, the process proceeds to step S13.

-Update of each Lagrange multiplier (step S11)
The Lagrange multiplier update unit 14 updates the Lagrangian multiplier of each constraint according to the violation amount.

N = n + 1 (step S12)
1 is added to the variable n for counting the number of repetitions.

-Schedule generation by heuristics (step S13)
The executable schedule generator 15 generates an executable schedule by a heuristic algorithm.

-Schedule result output (step S14)
The executable schedule generation unit 15 outputs an executable schedule.

  FIG. 6 is a flowchart showing an example of the heuristic algorithm according to step S13 in FIG.

The lot start / end time acquisition unit 16 uses δit ^k to grasp the start time and end time of all lots for each machine item (step S21).

  The machine interference prohibition constraint violation resolution unit 17 resolves the machine interference prohibition constraint violation (step S22). Specifically, 1) Lots that cause machine interference by machine and item, and the interference period are specified. 2) Lots that cause machine interference are moved by the backward method, forward method, etc. according to the situation. 3) After the machine interference is eliminated, the subsequent steps are performed while basically maintaining the order of the lots.

  The out-of-stock item prohibition constraint violation resolution unit 18 resolves the in-process item out-of-stock prohibition constraint violation (step S23). Specifically, 1) Lots that are out of stock and out of stock period are specified for each item, 2) Lots of items that are in shortage are advanced or delayed, 3) or the lot and its one Change the order of the lot of the previous item, and 4) Further, take action according to the situation by delaying the lot of the directly connected item.

  The material shortage prohibition constraint violation resolution unit 19 resolves the material shortage prohibition constraint violation by matching and synchronizing the family item and the actual item (step S24). Specifically, 1) For each family, specify the phase (shift) period of processing between family items and actual items, and 2) advance or delay the lot of family items in which the phase occurs, and synchronize them. Take.

  Next, an example of an output result of the multi-item multi-stage process dynamic lot size scheduling apparatus according to the embodiment will be described with reference to FIGS. 11 and 12. Here, an output result of scheduling for the system 100 shown in FIG. 4 is shown. In the figure, “F_ITEM...” Indicates a family item, and “R_ITEM...” Indicates an actual item. “F_MACHINE1... IDLING” indicates idle of the virtual machine, and “R_MACHINE1... IDLING” indicates idle of the real machine. “INTERFERENCE” indicates whether there is a violation of the machine interference prohibition constraint.

  FIG. 11 exemplifies a non-executable schedule and restriction violation points. The upper part of the figure shows the inventory transition graph for each item (horizontal axis: time slot, vertical axis: ladder inventory) for the first iteration of the planned period, and the lower part shows the Gantt chart for each item by machine (horizontal axis: time). Slot, vertical axis: presence / absence of processing).

  Looking at the inventory transition graph on the upper side of FIG. 11, a) Violations of the material shortage prohibition constraint appear downwardly in the inventory transition of family items. In addition, b) Violations of the out-of-stock prohibition constraint for work-in-progress items appear to protrude downward in the inventory transition of actual items. On the other hand, when viewing the Gantt chart on the lower side of FIG. 11, c) violation points of the machine interference prohibition constraint appear for each machine.

  FIG. 12 shows an executable schedule result. The upper part of the figure shows the inventory transition graph by item when calculating the feasible solution (horizontal axis: time slot, vertical axis: ladder inventory), and the lower part of the figure shows the Gantt chart by item by machine (horizontal axis: time slot, The vertical axis indicates the presence or absence of processing.

  Looking at the inventory transition graph on the upper side of FIG. 12, in the inventory transition of a) family items, there are no violations of the material shortage prohibition constraint appearing convex downward. In addition, in the b) inventory transition of actual items, there are no violations of the out-of-stock prohibition constraint for work-in-progress items, which appeared convex downward. Also, looking at the Gantt chart on the lower side of FIG. 12, c) there is no violation of the machine interference prohibition constraint that appeared for each machine.

  Further, it should be noted that when viewing the Gantt chart on the lower side of FIG. 12, an actual item group belonging to the same family item is planned to be processed within the production frame of the family item.

  For example, actual items 1, 2, and 3 (R_ITEM1, R_ITEM2, and R_ITEM3) are processed only within the production frame (processing time zone) of family item 1 (F_ITEM1). Similarly, the actual items 4 and 5 (R_ITEM4, R_ITEM5) are processed only within the production frame (processing time zone) of the family item 2 (F_ITEM2). Similarly, the actual items 6 and 7 (R_ITEM6, R_ITEM6) are processed only within the production frame (processing time zone) of the family item 3 (F_ITEM3).

  It can be seen that there are 23 lots of actual items 1 to 7 (R_ITEM1 to R_ITEM7), while family items 1 to 3 (F_ITEM1 to F_ITEM3) are grouped into 20 lots.

  The actual items 8 and 9 (R_ITEM8, R_ITEM9) are processed only within the production frame (processing time zone) of the family item 4 (F_ITEM4). Similarly, the actual items 10 and 11 (R_ITEM10, R_ITEM11) are processed only within the production frame (processing time zone) of the family item 5 (F_ITEM5). Similarly, the actual items 12, 13 (R_ITEM12, R_ITEM13) are processed only within the production frame (processing time zone) of the family item 6 (F_ITEM6). Similarly, the actual item 14 (R_ITEM14) is processed only within the production frame (processing time zone) of the family item 7 (F_ITEM7).

  It can be seen that there are 28 lots of actual items 8 to 14 (R_ITEM8 to R_ITEM14), while family items 4 to 7 (F_ITEM4 to F_ITEM7) are grouped into 19 lots.

  As described above in detail, according to the present embodiment, it is possible to solve the existing scheduling problem by introducing a method for securing a production frame for a family of item groups.

  The various processing procedures according to the present invention described in the above-described embodiments are stored in a storage medium (for example, a magnetic disk, an optical disk, or a semiconductor memory) that can be read by a computer (information processing apparatus) as a computer program. If necessary, it may be read and executed by the processor. Such a computer program can also be distributed by transmitting from one computer to another computer via a communication medium.

  The present invention is not limited to the above-described embodiments as they are, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. In addition, various inventions can be formed by appropriately combining a plurality of components disclosed in the embodiment. For example, some components may be deleted from all the components shown in the embodiment. Furthermore, constituent elements over different embodiments may be appropriately combined.

The figure which shows an example of the main function structures of the multi-item multistage process dynamic lot size scheduling apparatus which concerns on one Embodiment of this invention. The figure which shows an example of a structure of the computer for implement | achieving the multi-item multistage process dynamic lot size scheduling apparatus shown by FIG. The figure which shows an example of a general structure at the time of introduce | transducing the concept of a virtual machine to the multi-item multistage process production system used as scheduling object. The figure which shows an example of a structure at the time of introduce | transducing the concept of a virtual machine to the multi-item multistage process production system used as the scheduling object in the same embodiment. The flowchart which shows an example of operation | movement of the whole scheduling apparatus. 6 is a flowchart showing an example of a heuristic algorithm according to step S13 in FIG. The figure which shows required quantity (rho) _ij of the item i per item j1 unit. The figure which shows production technical data (amount of processing p _i ^k , setup time s _imax ^k , setup cost c _i ^k ). Initial actual inventory amount y _i ^0, work-in-process storage costs h _i, shows the external demand _r i0t. Initial悌状amount of inventory x _i0, shows the required amount r _{i · t} of parts after deployment. The figure which shows a non-executable schedule and a constraint violation location. The figure which shows the schedule result which can be performed.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 11 ... Setting part, 12 ... Schedule generation part according to item, 13 ... Restriction violation monitoring part, 14 ... Lagrange multiplier update part, 15 ... Executable schedule generation part, 16 ... Lot start / end time acquisition part, 17 ... Mechanical interference prohibition Restriction violation resolving unit, 18 ... Out-of-stock prohibition restriction violation resolving unit, 19 ... Material shortage prohibition constraint violation resolving unit, 21 ... CPU, 22 ... Main memory, 23 ... HDD, 24 ... CD-ROM device, 25 ... Keyboard, 26 ... display, 27 ... system bus, 100 ... multi-item multi-stage production system, 241 ... optimization scheduling program, 242 ... CD-ROM.

Claims (9)

It is possible to process items corresponding to each process in multiple processes by multiple machines, and at least one machine or process to switch items with setup . A multi-item multi-stage dynamic lot size that secures a production frame that is a processing time zone and generates a production schedule that is applied to a multi-item multi-stage production system that can process the items together in the production frame. A scheduling method comprising:
A multi-item multi-stage production system that assumes that the virtual machine that processes the virtual item that will be the material of the real item processed by the real machine is in the previous process, and at least within the virtual item and the production frame of the virtual item. In addition to setting information indicating the relationship with the actual item to be processed in 1), 1) a machine interference prohibition restriction that prohibits the real machine or virtual machine from processing a plurality of items simultaneously, and 2) material of the actual item. Out-of-stock restrictions on work-in-progress items that prohibit virtual items or out-of-stock items, 3) Out-of-stocks restriction that prohibits a material item from becoming a material of a virtual item, and 4) Pre-defined actual A constraint setting step for setting a work-in-process constraint that limits the amount of work in progress for a set of items by machine or virtual machine;
An item-specific schedule generation step for generating, for each item, a schedule using a Lagrange function having a Lagrange multiplier corresponding to each constraint;
A multi-item multi-stage dynamic lot size scheduling method comprising: a Lagrange multiplier update step of updating a corresponding Lagrange multiplier in the Lagrangian function when there is a violation amount exceeding a threshold value in any of the constraints .   An executable schedule generation step for generating an executable schedule through a heuristic algorithm that sequentially resolves at least the violation of the machine interference prohibition constraint, the violation of the out-of-stock prohibition constraint of the work-in-progress item, and the violation of the material shortage prohibition constraint The multi-item multi-stage dynamic lot size scheduling method according to claim 1, further comprising: The executable schedule generation step includes:
Steps to grasp the start and end times of all lots for each machine item,
Resolving the violation of the machine interference prohibition constraint by moving the lot causing the machine interference for each machine by item;
Resolving the violation of the out-of-stock restriction of the in-process item by changing the processing speed or order of the lot that is out of stock for each item; and
3. The multi-item multi-step dynamic lot size according to claim 2, further comprising a step of resolving the violation of the material shortage prohibition constraint by synchronizing the processing of the virtual item and the processing of the real item. Scheduling method. Processing of items corresponding to each process in multiple processes by multiple machines, and switching of items with setup in at least one machine or process, and processing of item groups defined as families in each process A program for multi-item multi-stage process dynamic lot size scheduling in a multi-item multi-stage process production system capable of securing a production frame that is a time zone and processing the item group together in the production frame ,
On the computer,
A multi-item multi-stage production system that assumes that the virtual machine that processes the virtual item that will be the material of the real item processed by the real machine is in the previous process, and at least within the virtual item and the production frame of the virtual item. In addition to setting information indicating the relationship with the actual item to be processed in 1), 1) a machine interference prohibition restriction that prohibits the real machine or virtual machine from processing a plurality of items simultaneously, and 2) material of the actual item. Out-of-stock restrictions on work-in-progress items that prohibit virtual items or out-of-stock items, 3) Out-of-stocks restriction that prohibits a material item from becoming a material of a virtual item, and 4) Pre-defined actual A constraint setting function for setting a work-in-process constraint that limits the amount of work in progress for a set of items by machine or virtual machine;
An item-specific schedule generation function for generating a schedule using a Lagrangian function having a Lagrange multiplier corresponding to each constraint;
A program for realizing a Lagrange multiplier update function for updating a corresponding Lagrangian multiplier in the Lagrangian function when there is a violation amount exceeding a threshold value in any of the constraints. On the computer,
An executable schedule generation function that generates an executable schedule through a heuristic algorithm that sequentially resolves at least the violation of the machine interference prohibition constraint, the violation of the out-of-stock prohibition constraint of the work-in-progress item, and the violation of the material shortage prohibition constraint The program according to claim 4, further realizing the above. The executable schedule generation function is:
A function to grasp the start and end times of all lots for each machine item,
A function that eliminates violation of the machine interference prohibition constraint by moving a lot causing machine interference for each machine item,
A function for solving violation of the out-of-stock restriction of the in-process item by changing the processing speed or order of the lot that is out of stock for each item,
The program according to claim 5, further comprising: a function of resolving the violation of the material shortage prohibition constraint by synchronizing the processing of the virtual item and the processing of the real item. Processing of items corresponding to each process in multiple processes by multiple machines, and switching of items with setup in at least one machine or process, and processing of item groups defined as families in each process Multi-item multi-step dynamic lot size scheduling that generates a production schedule that is applied to a multi-item multi-step production system that secures a production frame that is a time zone and can process the items together in the production frame. A device,
A multi-item multi-stage production system that assumes that the virtual machine that processes the virtual item that will be the material of the real item processed by the real machine is in the previous process, and at least within the virtual item and the production frame of the virtual item. In addition to setting information indicating the relationship with the actual item to be processed in 1), 1) a machine interference prohibition restriction that prohibits the real machine or virtual machine from processing a plurality of items simultaneously, and 2) material of the actual item. Out-of-stock restrictions on work-in-progress items that prohibit virtual items or out-of-stock items, 3) Out-of-stocks restriction that prohibits a material item from becoming a material of a virtual item, and 4) Pre-defined actual Constraint setting means for setting an in-process constraint by machine that limits the in-process amount of a set of items by machine or virtual machine,
Item-specific schedule generation means for generating a schedule using a Lagrange function having a Lagrange multiplier corresponding to each constraint,
A multi-item multi-stage dynamic lot size scheduling comprising: a Lagrange multiplier updating means for updating a corresponding Lagrange multiplier in the Lagrangian function when there is a violation amount exceeding a threshold value in any of the constraints. apparatus.   Executable schedule generating means for generating an executable schedule through a heuristic algorithm that sequentially resolves at least the violation of the machine interference prohibition constraint, the violation of the out-of-stock prohibition constraint of the work-in-progress item, and the violation of the material shortage prohibition constraint The multi-item multi-stage dynamic lot size scheduling apparatus according to claim 7, further comprising: The executable schedule generation means includes:
A means of grasping the start and end times of all lots by machine-specific items;
Means for resolving the violation of the machine interference prohibition constraint by moving the lot causing the machine interference for each machine item;
Means for resolving the violation of the out-of-stock restriction of the in-process item by changing the processing speed or order of the lot causing out-of-stock for each item;
9. The multi-item multi-stage dynamic lot according to claim 8, further comprising means for eliminating a violation of the material shortage prohibition constraint by synchronizing virtual item processing and real item processing. Size scheduling device.

Images