JP4734604B2 - A method for dynamic lot size scheduling with setup with multiple attributes - Google Patents

Description

  The present invention can process items corresponding to each work in a plurality of operations by a single machine, and each item can be switched between items with a set-up operation according to a plurality of attributes of the items. The present invention relates to a method for dynamic lot size scheduling with setup with multiple attributes suitable for generating a production schedule applied to a production system.

  Scheduling in a production system in which a single machine processes items corresponding to each work in a plurality of work, there are two completely different aspects of determination, namely, the determination of the lot order of the items to be produced and the determination of each lot size. is there. This kind of scheduling problem is conventionally known as a scheduling problem with order-dependent setup and has been treated mathematically as a combinatorial optimization problem.

  Conventionally, the scheduling problem is often treated as an asymmetric traveling salesperson problem. However, it is only possible to determine only the order of circulation, that is, the order of production (lot order), and it is necessary to rely on another method for determining the lot size. In addition, when trying to solve a practical-scale scheduling problem using conventional techniques, a computational problem called combinatorial explosion, that is, a problem that requires a huge amount of calculation occurs. For this reason, conventionally, it is general that only a very small scale problem can be targeted.

Therefore, in recent years, a technique (hereinafter referred to as prior art) for simultaneously optimizing (determining) a plurality of different determination phases such as determination of lot size and determination of lot order from the viewpoint of overall optimization has been proposed (for example, patents). Reference 1 or 2).
JP 2002-236721 A JP 2002-328977 A

  However, the prior art described in Patent Document 1 or 2 is limited to a scheduling problem having an order-independent setup.

  Therefore, the above prior art cannot be applied to a scheduling problem involving a setup having a plurality of attributes, which is widely seen in the manufacturing industry and other industries. Even if it can be applied, it is very difficult to solve the scheduling problem.

  The present invention has been made in consideration of the above circumstances, and its purpose is to generate an extremely precise schedule without causing a combination explosion even for a problem on a practical scale having an order-dependent setup. It is an object of the present invention to provide a method for dynamic lot size scheduling with setup having a plurality of attributes.

  According to one aspect of the present invention, a single machine processes items corresponding to each operation in a plurality of operations, and each operation involves a set-up operation corresponding to a plurality of attributes of the item. A method is provided for dynamic lot size scheduling with a set-up having a plurality of attributes that is computer generated for a production schedule that is applied to a production system capable of switching items. This method assumes a virtual machine that virtually processes an attribute for each attribute of an item to be produced, and uses the one machine as an item machine to set up the work related to the attribute of the item to be produced from the item machine. For each item processed in each operation by the item machine and each attribute processed virtually in the virtual machine by machine corresponding to the machine interference prohibition restriction (first restriction) First penalty cost assigned by time slot, second penalty cost assigned by item / time slot corresponding to in-process non-negative constraint (second constraint), simultaneous setup prohibition constraint (third constraint) Product that optimizes the evaluation criteria including the corresponding third penalty cost and the fourth penalty cost corresponding to the processing consistency constraint (fourth constraint) The step of acquiring the separate attribute-specific schedule independently of other items / attributes, and whether the violations of the first, second, third, and fourth constraints are all resolved in the acquired item-specific attribute-specific schedule And determining that at least one of the violations of the first, second, third, and fourth constraints has not been resolved, and if the violation needs to be resolved, the first, second, Updating a penalty cost corresponding to a constraint in which the at least one violation is not resolved among the second, third, and fourth penalty costs so that the at least one violation is resolved; and the updating step. Each time it is executed, the step of re-executing the obtaining step is included.

  According to the present invention, not only one scheduling problem is decomposed for each item but also virtually expanded to the attribute unit of the target product (item), and the scheduling problem is decomposed for each attribute / item. By handling it, it is possible to generate a very precise schedule without causing a combination explosion even for a problem on a practical scale having an order-dependent setup.

Embodiments of the present invention will be described below with reference to the drawings.
FIG. 1 is a block diagram showing a configuration of a dynamic lot size scheduling apparatus according to an embodiment of the present invention. This dynamic lot size scheduling apparatus processes an item corresponding to each work in a plurality of work by one machine, and each work involves a setup work corresponding to a plurality of attributes of the item. A production schedule to be applied to a production system that can be switched is generated. In order to generate this production schedule, the dynamic lot size scheduling apparatus handles a dynamic lot size scheduling problem involving setup with multiple attributes.

  The dynamic lot size scheduling apparatus shown in FIG. 1 is realized using, for example, a general-purpose computer. The dynamic lot size scheduling apparatus mainly includes a keyboard 11, a display 12, a hard disk drive (HDD) 13, a CD-ROM drive 14, a main storage device 15, and a CPU 16. The keyboard 11, display 12, HDD 13, CD-ROM drive 14, main storage device 15 and CPU 16 are interconnected by a system bus 17.

  The keyboard 11 is used as an input device for inputting data, instructions, and the like by a user (operator) operation. The display 12 is used as a display device for displaying a constraint violation amount described later, a generated schedule, and the like.

  The HDD 13 is used as an auxiliary storage device. The HDD 13 stores an operating system (OS) 21, a dynamic lot size scheduling program 22, and schedule generation data 23.

  The dynamic lot size scheduling program 22 is an application program installed in the HDD 13 from the CD-ROM 20 via, for example, the CD-ROM drive 14. In the dynamic lot size scheduling program 22, machines (manufacturing apparatuses) having a plurality of different attributes that exist in reality are virtually expanded to a plurality of machines, and the relationship between attributes and items is mathematically expressed. The mathematical model is reflected. The program 22 includes a recursive equation 40, a state transition table 41, and a state transition table 42 which will be described later.

  The schedule generation data 23 includes item-attribute relation data 30, machine-item / attribute relation data 31, production requirement data 32, production / setup data 33, inventory management data 34, condition data 35 and shipping request quantity data 36. including. The schedule generation data 23 can be input from the keyboard 20 by an operator's operation. The data 23 can also be input from the CD-ROM 20 via the CD-ROM drive 14.

  The item-attribute relationship data 30 represents the correspondence between items and attributes. The machine-item / attribute relationship data 31 represents a correspondence relationship between a machine and an attribute / item. The production requirement data 32 represents the requirement of parts or semi-finished products necessary for producing one unit of an arbitrary item. The production / setup data 33 represents the number of production items, the setup time, and the setup cost for each attributed item per unit time of the machine.

  The inventory management data 34 represents an inventory storage cost rate, an initial inventory quantity, an inventory upper limit value, and an inventory lower limit value for each item by attribute. The condition data 35 represents the maximum number of loop iterations (N) and threshold values for various constraint violation amounts in a dynamic lot size scheduling process to be described later. The shipping request amount data 36 represents the shipping request amount for each item at the end of each time slot (time point) requested by the customer. In the present embodiment, 7 days, that is, 168 hours, is set as the target period of the production plan (plan target period). The time slot refers to 336 time increments obtained by dividing the planning target period at a constant time interval, for example, an interval of 30 minutes.

The main storage device 15 provides a storage area for storing the schedule generation data 23 when the dynamic lot size scheduling program 22 is executed. The main storage device 15 also provides a storage area for storing the generated schedule.

  The CPU 16 is a main controller of the dynamic lot size scheduling apparatus. The CPU 16 executes the dynamic lot size scheduling program 22 to handle the dynamic lot size scheduling problem involving setup with multiple attributes.

  Next, a concept which is a premise for processing a dynamic lot size scheduling problem involving a setup having a plurality of attributes, which is a feature of the present embodiment, will be described with reference to FIG. First, in FIG. 2 (a), a single machine (manufacturing apparatus) 200 processes each item corresponding to each operation in a plurality of operations, and each operation corresponds to a plurality of attributes of the item. An example of a production system capable of switching items with setup work will be shown. In the example of the production system in FIG. 2A, three products (items) 3, 6 and 9 are produced. The semi-finished products (items) 2, 5 and 8 are incorporated in the products (items) 3, 6 and 9, respectively, as indicated by white arrows. Parts (items) 1, 4 and 7 are incorporated in the semi-finished products (items) 2, 5 and 8, respectively, as indicated by white arrows. In FIG. 2A, the numbers given to the white arrows indicate the number of items (semi-finished products or parts) incorporated in the items (products or semi-finished products) indicated by the arrows.

  Here, it is assumed that the items 1 to 9 have two types of attributes of “color” and “form”. Also, it is assumed that there are “white, blue, black” attribute values as “color” attributes, and “◯, Δ, □” attribute values as “shape” attributes. Assume that items 1 and 7 have the attribute of “white / o”. In this case, it is not possible to enter the work until the setting of the machine 200 becomes the setting of “white” and “◯”. Changing the settings takes time, and this is called setup time. In addition to those depending on attributes, settings of the machine 200 include settings depending on items, and it takes the most time to change all the settings. When the item 7 is produced after the item 1, the production can be started only by the setting depending on the item 7 alone. This is because the item 7 has exactly the same attributes as the item 1 and does not require settings depending on the color and shape.

  On the other hand, it is assumed that the item 4 has an attribute of “black / Δ” and the production is switched from the item 1 to the item 4. In this case, since the item 4 has an attribute of “black / Δ” different from that of the item 1, all settings relating to the color “black”, the shape “Δ”, and the item 4 need to be changed. For this reason, it takes time to change from item 1 to item 4. Even when all settings are changed, the time changes depending on the type of attribute before and after switching. For example, since the “color” attribute requires a more elaborate cleaning operation when switching from a dark color to a light color than when switching from a light color to a dark color, the latter requires a longer time for setting than the former.

  In this way, the required time varies depending on which item is switched to which item. For this reason, in consideration of order-dependent setup, a precise scheduling technique for handling from the viewpoint of overall optimization is extremely important in the current manufacturing site where a short delivery time is required.

  Therefore, in this embodiment, a virtual machine (virtual machine) is assumed for each attribute of an item to be produced, and a network is configured so that each attribute is incorporated in the actual production of the item. This network is shown in FIG. 2B, in addition to the machine 200, the machine 200 shown in FIG. 2A includes a virtual machine 201 for the “shape” attribute (machine for shape attribute) and a virtual machine for the “color” attribute. The machine (color attribute machine) 202 is extended at the concept level. The shape attribute machine 201 mainly handles settings that depend on the “shape” attribute in order to make the shape attribute available to the production (processing) of items by the machine 200. That is, the shape attribute machine 201 processes the shape attribute. On the other hand, the color attribute machine 202 handles settings that depend primarily on the “color” attribute in order to make the color attribute available for production of items by the machine 200. That is, the color attribute machine 202 processes color attributes. This separates the settings dependent on the “shape” and “color” attributes from the machine 200. In this respect, unlike the machine 200 shown in FIG. 2A, the machine 200 shown in FIG. 2B can be regarded as a kind of item virtual machine (item machine). Therefore, in the following description, the actual machine may be referred to as an item machine.

  In the example of FIG. 2B, the shape attribute machine 201 handles settings depending on shape attributes having attribute values of “◯, Δ, □”. On the other hand, the color attribute machine 201 handles settings depending on color attributes having attribute values of “white, blue, and black”. On the other hand, the item machine 200 performs work for the items 1 to 9 including settings depending on the items 1 to 9. In FIG. 2 (b), from the symbols of the attribute values “○, Δ, □” of the shape attribute in the attribute machine 201 and the attribute values “white, blue, black” of the color attribute in the color attribute machine 202, A solid arrow pointing to the item symbol in the item machine 200 is drawn. This arrow indicates an item produced by the item machine 200 at its tip, and an attribute value (attribute value) of the item at its base end. Therefore, it can be seen from FIG. 2B that, for example, the item 1 has the attribute of “white / o”. Here, it can be seen that the item machine 200 can enter the work for the item 1 only after the shape attribute machine 201 and the color attribute machine 202 are set to “◯” and “white”, respectively. .

  Next, the flowchart of FIG. 3 shows the procedure of the dynamic lot size scheduling process (dynamic lot size scheduling process) involving the setup having a plurality of attributes, which is applied in the dynamic lot size scheduling apparatus of FIG. Will be described with reference to FIG.

  First, the operator uses the keyboard 11 to perform an operation for starting the dynamic lot size scheduling program 22. As a result, the CPU 16 starts executing the program 22. Then, the schedule generation data 23 stored in the HDD 13 is read into the main storage device 15 (step S1). As described above, the schedule generation data 23 includes the item-attribute relation data 30, the machine-item / attribute relation data 31, the production requirement data 32, the production / setup data 33, the inventory management data 34, the condition data 35, and the like. The shipping request amount data 36 is included.

  FIG. 4 shows an example of the item-attribute relationship data 30. According to the item-attribute relationship data 30, the correspondence between the item and the attribute is represented by 0 (no correspondence) and 1 (with correspondence). FIG. 5 shows an example of the machine-item / attribute relationship data 31. According to the machine-item / attribute relationship data 31, the correspondence between the machine and the attribute / item is represented by 0 (no correspondence) and 1 (with correspondence).

  FIG. 6 shows an example of the production requirement data 32. According to the production requirement data 32, the requirement amount of parts / semi-finished products necessary for producing one unit of an arbitrary item is represented by a From To chart. FIG. 7 shows an example of production / setup data 33. According to the production / setup data 33, the production quantity (production capacity) for each item by attribute per unit time of the machine, the setup time in terms of unit time, and the setup cost are represented.

  FIG. 8 shows an example of the inventory management data 34. According to the inventory management data 34, an inventory storage cost rate, an initial inventory amount, an inventory upper limit value, and an inventory lower limit value for each item by attribute are represented. FIG. 9 shows an example of the condition data 35. According to the condition data 35, the maximum number of loop iterations N in the dynamic lot size scheduling process and the threshold values of various constraint violation amounts are expressed. FIG. 10 shows an example of the shipping request amount data 36. According to the shipping request amount data 36, the shipping request amount for each item requested by the customer at the end of each time slot after the parts development is represented.

  When the schedule generation data 23 is read into the main storage device 15, the CPU 16 functions as an initial setting means. In this case, the CPU 16 initializes a Lagrange multiplier (to be described later) in a predetermined area of the main storage device 15, for example, based on the condition data 35 included in the schedule generation data 23 read into the main storage device 15. (Step S2). In addition, the CPU 16 sets the maximum number of repetitions N and the threshold value for each constraint violation amount in a predetermined area of the main storage device 15 (steps S3 and S4). Further, the CPU 16 initializes 1 as a variable for counting the number of repetitions (repetition count variable) n (S5).

  When the above initial setting processing is completed, the CPU 16 functions as a schedule generation unit, and generates a schedule for each time slot independently for each item attribute based on the schedule generation data 23 read into the main storage device 15. (Step S6). This schedule creation can be performed using dynamic programming as in the case of creating a schedule for each time slot independently for each conventional item.

In dynamic programming method applied in the present embodiment, a 0-1 decision variable [delta] ^k _it and stock quantity x _it is used. [delta] ^k _it is a 1 when the attribute-item i is performed in the machine k in time slot t, is World 0-1 decision variable that takes 0 when the. _xit represents the inventory quantity of the attribute / item i at the end of the time slot t. Further, in this dynamic programming, and state variables s ^k _it, the four constraints each Lagrange multiplier corresponding to the (constraint Lagrange _{^{multiplier) μ k · t, μ ·}} it, and the lambda _it and lambda _jit using It is done. s ^k _it is a state variable to distinguish machine k, attribute-item i, and the remaining time and the pending setup at the time t.

In the present embodiment, in order to apply the dynamic programming method, an optimal cost function is defined by a recursive equation 40 expressed by the following equation (1). The optimal cost function is used to optimize evaluation criteria including Lagrange multipliers μ ^k _{· t} , μ ^· _it , λ _it and λ _jit at the end of time slot t of attribute / item i.

In the recurrence equation 40 of the equation (1), the Lagrange multiplier μ ^k _{· t} is a penalty cost assigned to each machine and each time slot corresponding to machine interference between items and between attributes (machine scramble state by item and attribute). (First penalty cost). That is, the Lagrange multiplier μ ^k _{· t} represents a penalty cost corresponding to the machine interference prohibition restriction (first restriction) of the machine k and the time slot t. The Lagrange multiplier μ ^· _it is a penalty cost (second penalty cost) assigned to each item and each time slot corresponding to the fulfillment of the in-process inventory. That is, the Lagrange multiplier μ ^· _it represents the penalty cost corresponding to the in-process inventory non-negative constraint (second constraint) at the item i and the time point t. Moreover, the Lagrange multiplier lambda _it is throughout the material and attributes restriction that other items or attributes must not be in or actual processing in setup if any item i or attribute i is being setup (simultaneous setup prohibition This is a penalty cost (third penalty cost) assigned to satisfy (constraint). That Lagrange multiplier lambda _it represents a penalty cost corresponding to the attribute-item i, simultaneous setup prohibition constraint at time t (third constraints). The Lagrange multiplier λ _jit is a penalty assigned to satisfy the constraint that the accumulated actual operating time of any attribute j must be equal to the accumulated actual operating time of the item i having that attribute j (process consistency constraint) Cost (fourth penalty cost). That is, the Lagrange multiplier λ _jit represents the penalty cost corresponding to the consistency constraint (fourth constraint) of the process at the time point t of the attribute j and the item i.

In the recursive equation 40, c ^k _i is the setup cost data of the machine k and the attribute / item i shown by the production / setup data 33, and h _i is the attribute / item shown by the condition data 35. This is the inventory storage cost rate of i. In the recurrence equation 40, b _a (i) is an index function that takes 1 when i is an attribute and 0 when it is an item, and b _r (i) is opposite to b _a (i). This is an index function that takes 1 for an item and 0 for an attribute.

The recurrence equation 40 includes the sets K _a , K _r , S _a (i), S _r (i), P _r (i), and M (k). K _a and K _r are a set of virtual machines corresponding to attributes and a set of machines (item machines) corresponding to items, respectively. K = K _a ∪K _r . The sets K _a and K _r can be specified from the machine-item / attribute relationship data 31. S _a (i) is a set of items having attribute i, and P _a (i) is a set of attributes of item i. The sets S _a (i) and P _a (i) can be specified from the item-attribute relationship data 30. S _r (i) is a set of subsequent directly connected items into which the item i is incorporated, and P _r (i) is a set of preceding directly connected items to be incorporated into the item i. The sets S _r (i) and P _r (i) can be specified from the production requirement data 32. M (k) is a set of attributes / items that can be processed by the machine k. The set M (k) can be specified from the machine-item / attribute relationship data 31.

In the recurrence equation 40, I ₀ , I ₀₊ and I ₊ are index functions. The index function I ₀ is 1 when s ^kit _it = 0, and 0 otherwise. Index function I ₀₊ is, becomes 1 at the time of the s ^k _it ≧ 0, the other becomes zero at the time of the. Index function I ₊ becomes 1 at the time of the s ^k _it> 0, the other becomes zero at the time of the. n _T represents the last time slot t (t = n _T = 336) of the planning target period in scheduling.

In step S6, the optimal cost function at the end of the time slot t of the attribute / item i is calculated from time slot 0 to the last time slot n _T (t = 0 to t = n _T ) according to the recursive equation 40. Here, 0 is substituted as the value of the recursive expression in the state of the initial time point (time slot 0) shown in Expression (1), as performed by a conventionally known dynamic programming solution. Further, the maximum value (for example, ∞) that can be used for numerical calculation is substituted for a state other than the initial time point. The calculation of the recursive equation 40 up to the final time point (time slot n _T ) is performed according to the state transition tables 41 and 42. The state transition tables 41 and 42 are From To charts shown in FIG. The state transition table 41 represents an attribute transition, and the state transition table 42 represents an item transition. The state transition tables 41 and 42 in FIG. 11 are items on the upper side of the table from the state indicated by the item on the left side of the table, that is, the state that the machine k and attribute / item i can take in the time slot (time point) t−1. , That is, only the state transition in which a circle is entered is allowed to the state that can be taken by the machine k and the attribute / item i in the time slot (time point) t.

Now, according to the recurrence equation 40, it is assumed that the optimal cost function has been calculated for all states up to the final time slot n _T of the planning target period. Then CPU16 specifies the optimum value in the time slot n _T. Further, the CPU 16 _{specifies the} decision variable δ ^k _inT as the state at the optimum value, and the inventory quantities x _inT and s ^k _inT as the state variables. The CPU 16 uses the three values δ ^k _inT , x _inT and s ^k _inT and the requested shipping quantity in the time slot t (= n _T ) to calculate the inventory quantity x _it-1 at the end of the time slot t−1. wherein _{x it-1 = x it +} r it -Σ k∈K (i) p i δ k it I 0 (s k it) (2)
Calculate according to Thereby, the CPU 16 specifies δ ^k _it-1 and s ^k _it-1 in the time slot t-1. Similarly, the CPU 16 decrements t by 1 (t = t−1) and acquires x _it−1 , δ ^k _it−1 and s ^k _it−1 until t = 1. Repeat in the direction of going back in time. Thus CPU16 is from t = 0 to t = n _T, to obtain a certain single attribute, item i schedule for (i.e. set of [delta] ^k _it and x _it and s ^k _it). The CPU 16 performs this operation for all attributes / items i. In this way, the CPU 16 generates a schedule for each time slot independently for each item attribute (step S6).

  Next, the CPU 16 functions as a constraint violation amount calculating means, and calculates each constraint violation amount based on a schedule created for each time slot for each item attribute (step S7).

  Here, the constraint condition and the constraint violation amount will be described. In this embodiment, as shown in FIG. 2B, one item 1 is used for the production of the item 2, and two items 2 are used for the production of the item 3. Further, two items 4 are used for the production of the item 5, and two items 5 are used for the production of the item 6. Further, one item 7 is used for the production of the item 8, and one item 8 is used for the production of the item 9.

  Therefore, if the item 2 is not completed before the item 3 is made and the item 1 is not completed before the item 2 is made, the actually required item cannot be produced. Therefore, such a relationship is used as a constraint condition. This constraint condition is called an in-process inventory non-negative constraint (second constraint). The violating amount of the in-process inventory non-negative constraint is calculated as a value obtained by subtracting the net inventory amount from the inventory amount of the item i to be produced in the same time slot, and represents the degree of shortage of the in-process inventory. If this value exceeds 0, the in-process inventory amount is negative, so it is recognized that the in-process inventory non-negative constraint is violated. The net inventory amount is calculated as an amount obtained by subtracting the initial inventory amount from the inventory amount of the item j required for the production of the item i.

  In this embodiment, items 1-9 are produced by one machine (here, machine 200). However, a single machine cannot process all items at the same time. Therefore, this relationship is used as a constraint condition. This constraint condition is called a machine interference prohibition constraint. The violation amount of the machine interference prohibition constraint (first constraint) is calculated as a value obtained by subtracting 1 from the total number of items occupying the machine in the same time slot, and the machine interference between the items and between the attributes in the same machine. Represents the degree of

  In this embodiment, it is assumed that attribute setup cannot be processed simultaneously by one machine. This relationship is also used as a constraint condition. This constraint condition is referred to as a simultaneous setup prohibition constraint (third constraint). The amount of violation of the simultaneous setup prohibition constraint is calculated as a value obtained by subtracting 1 from the total number of attributes and items that are being set up in the same time slot. The violation amount of the simultaneous setup prohibition constraint represents the degree to which another item or attribute that is being set up or being actually processed exists while any item or attribute is being set up.

  Further, in the time slot for processing an item, the item must be processed in a state where the attribute of the item is set. Therefore, it is necessary to synchronize items and attributes. This relationship is also used as a constraint condition. This constraint condition is called a process consistency constraint (fourth constraint). The amount of violation of the process consistency constraint is calculated as follows, for example. First, in a certain time slot, a value of 1 is set when an item is being processed, and a value of 0 is set otherwise. Similarly, in a certain time slot, a value of 1 is set when an attribute is being processed, and a value of 0 is set otherwise. In this case, the violation amount of the process consistency constraint is calculated by calculating the cumulative value for each time slot and subtracting the cumulative value of the attribute from the cumulative value of the item. The amount of violation of the process integrity constraint represents the degree of deviation between the accumulated actual operation time of an arbitrary attribute and the accumulated actual operation time of an item having the attribute.

  When the CPU 16 calculates the constraint violation amounts corresponding to the four constraints in step S7, the CPU 16 functions as a constraint violation determination unit. In this case, based on the calculated constraint violation amount, the CPU 16 determines whether or not the schedule generated most recently in step S6 has solved all the violations of the above four constraints, that is, all the above four constraints. It is determined whether or not the condition is satisfied (step S8). This determination is made based on whether or not the calculated constraint violation amounts are all 0 or less.

  If all the constraint violation amounts are 0 or less, the CPU 16 determines that the generated schedule satisfies all the four constraints (that is, all the four constraint violations have been eliminated). In this case, the most recently generated schedule in step S6 indicates an executable schedule with no constraint violation points. Therefore, the CPU 16 functions as a schedule result output unit, and displays a schedule result (executable schedule) on the display 24, for example (S14).

  As described above, in this embodiment, a machine having a plurality of different attributes is virtually expanded to a plurality of machines (virtual machines), and the relationship between these virtual machines and the original machine is expressed as a mathematical model. A plurality of attributes and products (items) are disassembled completely independently, and a schedule is obtained for each item-specific attribute for each time slot at a certain time interval. In this embodiment, the four constraints corresponding to the four constraints are satisfied until all of the four constraints (mechanical interference prohibition constraint, in-process inventory non-negative constraint, simultaneous setup prohibition constraint, and process consistency constraint) are satisfied. Of the Lagrange multipliers (penalty costs), the Lagrange multipliers corresponding to constraints that do not meet the conditions are updated according to the amount of constraint violations, and all schedules are finally satisfied by repeating the schedule generation. An executable schedule can be obtained. As a result, it is possible to generate an extremely precise schedule without causing a combination explosion even for a problem on a practical scale having an order-dependent setup.

  With the remarkable development of information and communication technology, the business environment is changing drastically, companies have a mission to send a wide variety of products to the world. Here, it is required to increase the operating rate and supply products to customers in a timely manner with a small capital investment. The manufacturing industry in such a situation has a proposition of how to efficiently operate a manufacturing apparatus. For this reason, it is possible to meet the needs of today's manufacturing business world by modeling and solving the scheduling problem with order-dependent setup from a completely different perspective than the conventional way of thinking as in this embodiment. is there.

  Next, a case where at least one of the constraint violation amounts exceeds 0 will be described. In this case, the CPU 16 determines that the generated schedule does not completely satisfy the four constraints (step S8). Then, the CPU 16 functions as a constraint violation level determination unit. In this case, at least whether the amount of violation of the constraint for which the violation has not been resolved is equal to or less than a threshold specific to the constraint (see condition data 35 in FIG. 9), that is, whether the constraint violation level is equal to or lower than the reference level. Determine (step S9). Note that it may be determined whether all of the violation amounts of the four constraints are equal to or less than a threshold unique to the constraint.

  If the violation amount of the constraint whose violation has not been resolved is equal to or less than the threshold value, the CPU 16 functions as a heuristic schedule generation unit. In this case, the CPU 16 generates an executable schedule by a heuristic algorithm based on the most recently generated schedule (non-executable schedule) in step S6 (step S13). And CPU16 functions as a schedule result output means, and displays the produced | generated schedule on the display 24 (step S14).

  On the other hand, if the violation amount of the constraint whose violation has not been resolved exceeds the threshold value, the CPU 16 functions as a repeat count determination unit. In this case, the CPU 16 determines whether or not the repetition count variable (number of repetitions of calculation) n exceeds a predetermined maximum repetition number N (see the condition data 35 in FIG. 9) (step S10).

If n is N or less, the CPU 16 functions as an updating unit. In this case, the CPU 16 updates each Lagrangian multiplier according to the constraint violation amount corresponding to the Lagrange multiplier so that the constraint violation is eliminated (step S11). That is, when the violation of the machine interference prohibition constraint has not been resolved, the CPU 16 updates the Lagrange multiplier μ ^k _{· t} so that the degree of machine interference corresponding to the violation is reduced. If the violation of the in-process inventory non-negative constraint has not been resolved, the CPU 16 updates the Lagrange multiplier μ ^· _it so that the in-process inventory corresponding to the violation is satisfied. When the violation of the simultaneous setup prohibition constraint has not been resolved, the CPU 16 updates the Lagrange multiplier λ _it so that other items or attributes are not being set up or being actually processed during the setup of the item i or the attribute i. When the violation of the process consistency constraint has not been resolved, the CPU 16 updates the Lagrange multiplier λ _jit so that the accumulated actual operation time of the attribute j is equal to the accumulated actual operation time of the item i having the attribute j. To do.

  When executing step S16, the CPU 16 functions as a control unit, and after incrementing the repeat count variable n by 1 (S12), controls the repetition of the procedure starting from step S6. Eventually, when it is determined in step S10 that the iteration count variable (the number of iterations of calculation) n has exceeded the maximum iteration number N, the CPU 16 proceeds to step S13 and generates an executable schedule by a heuristic algorithm.

  Next, a procedure of processing for generating an executable schedule by a heuristic algorithm will be described with reference to the flowchart of FIG.

The CPU 16 identifies all lots for each item i based on the item-specific attribute schedule generated most recently in step S6, and generates information on the production start / end points of the lot (step S21). Here, a lot of the production start of the item i (the starting time slot) is a time when the 0-1 decision variable [delta] ^k _it transitions from 0 to 1, the production end time (end time slots) is, [delta] ^k _it Is the time at which transitions from 1 to 0.

  Next, the CPU 16 arranges the processing order of each item on the item-specific attribute schedule based on the product structure (item configuration) in order to eliminate the in-process inventory non-negative constraint violation (step S22). Next, the CPU 16 moves the lot of the item i in the direction behind or in front of the time axis in order to eliminate the machine interference prohibition constraint violation (step S23). Here, it should be noted that the relative position at the start / end time of the lot of the item i is not changed.

  Next, the CPU 16 moves the lot in order to secure the attribute setup time and eliminate the violation of the simultaneous setup prohibition constraint (step S24). In step S24, the attribute processing status is also moved.

  Next, the CPU 16 expands / contracts the processing status of the attribute j of the item i in the time axis direction to synchronize with the processing status of the item i in order to eliminate the processing consistency constraint violation. Thereby, an executable schedule is generated heuristically.

  As described above, in this embodiment, even when the violations of the four constraints are not completely eliminated, the loop starting from step S8 is repeated a certain number of times (N times) when the constraint violation amount is below a certain level. In this case, an executable schedule can be acquired by a heuristic algorithm.

  Here, FIG. 13 and FIG. 14 show an example of the executable schedule obtained as the final result of the dynamic lot size scheduling, in which the constraint violation is resolved. An example of a non-executable schedule including a constraint violation location acquired as an intermediate result of dynamic lot size scheduling is shown in FIGS. 15 and 16. In FIG. 15, a solid line frame represented by a frame 151 indicates a consistency constraint violation portion of processing that appears as inventory. In FIG. 15, a wavy line frame represented by a frame 152 indicates an in-process inventory non-negative constraint violation location that appears as a negative inventory. In FIG. 16, a solid line frame represented by a frame 161 indicates a process consistency constraint violation location, and a broken line frame represented by a frame 162 indicates an inventory non-negative constraint violation location. In FIG. 16, a dashed-dotted line frame represented by a frame 163 indicates a mechanical interference prohibition constraint violation location, and a double-dashed line frame represented by a frame 164 indicates a simultaneous setup prohibition constraint violation location.

  The present invention can be applied to a machine (manufacturing apparatus) that produces a product having a plurality of different attributes by changing or adjusting portions corresponding to those attributes. For example, in a production line that has various shapes and can be applied with various colors, it is possible to produce while changing completely different attributes such as “color of paint used for product” and “product shape”. It can be applied to a manufacturing apparatus to be used. Specifically, retort food and liquid detergent refill containers, dealuminated packaging materials, pharmaceutical packaging materials, sterilization packaging materials for medical devices, clean packaging for semiconductors and precision equipment, etc. Applicable to other production lines. In fields other than manufacturing, there is a possibility of application to work schedules such as printing. Printers for printing generally perform printing while changing various attributes such as “paper size”, “paper color”, or “ink color”. The idea of can be applied.

  Note that the present invention is not limited to the above-described embodiment as it is, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. Further, various inventions can be formed by appropriately combining a plurality of constituent elements disclosed in the embodiment. For example, some components may be deleted from all the components shown in the embodiment.

The figure which shows the whole structure of the dynamic lot size scheduling apparatus which concerns on one Embodiment of this invention. The concept of expanding a multi-process model of products, semi-finished products, parts, and raw materials produced with a machine having a plurality of different attributes targeted in the same embodiment (dynamic lot size with a setup having a plurality of attributes The figure which shows the concept used as the premise for processing a scheduling problem in contrast with the flow of the process of the product, semi-finished products, parts, and raw materials produced with the said machine. The flowchart which shows the procedure of the process for dynamic lot size scheduling with the setup which has a some attribute. The figure which shows an example of the item-attribute relationship data 30. FIG. The figure which shows an example of the machine-item and attribute relationship data 31. FIG. The figure which shows an example of the production requirement data. The figure which shows an example of the production / setup data 33. The figure which shows an example of the inventory management data. The figure which shows an example of the condition data. The figure which shows an example of the shipping request amount data. The figure which shows an example of the state transition tables 41 and 42. FIG. The flowchart which shows the procedure of the process which produces | generates an executable schedule by a heuristic algorithm. The figure which shows a part of example of the executable schedule acquired as a final result of dynamic lot size scheduling in the same embodiment. The figure which shows the remainder of an example of the said executable schedule. The figure which shows a part of example of the non-executable schedule containing the constraint violation location acquired as an intermediate result of dynamic lot size scheduling in the same embodiment. The figure which shows the remainder of an example of the said non-executable schedule.

Explanation of symbols

  16 ... CPU, 22 ... Dynamic lot size scheduling program, 23 ... Schedule generation data, 30 ... Item-attribute relation data, 31 ... Machine-item / attribute relation data, 32 ... Production requirement data, 33 ... Production / stage Take data, 34 ... Inventory management data, 35 ... Condition data, 36 ... Requested shipment amount data, 40 ... Recursive equation, 41, 42 ... State transition table.

Claims (7)

Applicable to a production system in which a single machine processes items corresponding to each of the operations in a plurality of operations, and each operation can switch items with a set-up operation according to a plurality of attributes of the items. A method for dynamic lot size scheduling with setup having a plurality of attributes generated by a computer having a storage means, a CPU, and an output means .
A virtual machine that virtually processes an item to be produced by the item machine using the one machine as an item machine, an attribute of the item, and a setup operation depending on the item machine and the item attribute The CPU stores the schedule generation data including the data relating to each machine and the condition data applied in the dynamic lot size scheduling process in the first area of the storage unit;
By item / time corresponding to the first penalty cost assigned to each machine / time slot corresponding to the first constraint on machine interference between items and between attributes in the same machine, corresponding to the second constraint on fulfillment of in-process inventory The second penalty cost assigned by slot, across the item and attribute, corresponds to the third constraint that if any item or attribute is being set up, no other item or attribute must be set up or in process And an initial value of each of the fourth penalty costs corresponding to the fourth constraint that the accumulated actual operating time of any attribute must be equal to the accumulated actual operating time of the item having the attribute. The CPU sets the second area of the storage means based on the condition data stored in the storage means And the step that,
For each attribute virtually setup operation is processed in each material and the demographic virtual machines to be processed in the respective working by the item machinery, are set respectively in the storage means, said first first penalty cost assigned by the machine-specific time slot corresponding to the constraints, the second penalty cost assigned by item by time slot corresponding to the second constraint, the third corresponding to the third constraint penalty cost, and the fourth by item demographic schedule to optimize the evaluation criteria including a penalty cost corresponding to the fourth constraint, the CPU is, the schedule generation data stored in said storage means based on the acquisition, and for each time slot in another product category attribute, independently of the product category attribute-based schedule of other items and attribute And the step that,
Violation relating to the first, second, third and fourth constraints, whether all the violations of the first, second, third and fourth constraints are resolved in the acquired item-specific attribute schedule Determining by the CPU based on the degree of
If it is determined that at least one of the violations of the first, second, third, and fourth constraints has not been resolved, and the violation needs to be resolved, the first stored in the storage means the second, third and fourth penalty cost corresponding to the at least one violation has not been solved constraints of the penalty cost, the steps of the CPU is updated to the at least one violation is resolved ,
Each time the updating step is executed, the step of causing the CPU to re-execute the acquiring step ;
When all the violations of the first, second, third, and fourth constraints have been resolved, the CPU uses the output means as the production schedule that can execute the corresponding item-specific attribute-specific schedule. method for dynamic lot size scheduling, characterized by comprising the step of outputting. Based on the obtained item-specific demographic schedule, the first, second, first representing the degree of breach of the third and fourth constraint, the second, third and fourth constraint violations amount the The CPU further includes a step of calculating,
In the determination step, it is determined based on the first, second, third, and fourth constraint violation amounts whether all violations of the first, second, third, and fourth constraints have been eliminated. The method for dynamic lot size scheduling according to claim 1. The first constraint violation amount represents the degree of machine interference in the same machine between items and attributes,
The second constraint violation amount represents a degree of in-process inventory shortage,
The third constraint violation amount represents the degree to which another item or attribute that is being set up or being actually processed exists while any item or attribute is being set up,
3. The dynamic lot size according to claim 2, wherein the fourth constraint violation amount represents a degree of deviation between an accumulated actual operation time of an arbitrary attribute and an accumulated actual operation time of an item having the attribute. A method for scheduling. In the updating step,
If the violation of the first constraint is not resolved, the first penalty cost is updated so that the degree of mechanical interference corresponding to the violation is reduced,
If the violation of the second constraint has not been resolved, the second penalty cost is updated to satisfy the in-process inventory corresponding to the violation,
If the violation of the third constraint has not been resolved, the third penalty cost is updated so that no other item or attribute is being set up or being processed during the setup of the arbitrary item or attribute,
If the violation of the fourth constraint is not resolved, the fourth penalty cost is updated so that the accumulated actual operation time of the arbitrary attribute becomes equal to the accumulated actual operation time of the item having the attribute. 4. The method for dynamic lot size scheduling according to claim 3, wherein: If it is determined that at least one of the violations of the first, second, third, and fourth constraints has not been resolved, at least the violation of the first, second, third, and fourth constraint violations The CPU determines whether the violation amount relating to the constraint that has not been resolved is less than or equal to the threshold value indicated by the condition data stored in the storage means, which is specific to the constraint for which the violation has not been resolved;
If the violation amount relating to the constraint for which the violation is not resolved even if the violation of the first, second, third, and fourth constraints is not completely resolved, the corresponding acquisition is performed. method for dynamic lot size scheduling according to claim 3, characterized by further comprising the step of said CPU executable the production schedule heuristically generating on the basis of the item-specific demographic schedule. Applicable to a production system in which a single machine processes items corresponding to each of the operations in a plurality of operations, and each operation can switch items with a set-up operation according to a plurality of attributes of the items. A program for dynamic lot size scheduling with setup having a plurality of attributes generated by a computer having a storage means, a CPU, and an output means .
In the computer,
A virtual machine that virtually processes an item to be produced by the item machine using the one machine as an item machine, an attribute of the item, and a setup operation depending on the item machine and the item attribute The CPU stores the schedule generation data including the data relating to each machine and the condition data applied in the dynamic lot size scheduling process in the first area of the storage unit;
By item / time corresponding to the first penalty cost assigned to each machine / time slot corresponding to the first constraint on machine interference between items and between attributes in the same machine, corresponding to the second constraint on fulfillment of in-process inventory The second penalty cost assigned by slot, across the item and attribute, corresponds to the third constraint that if any item or attribute is being set up, no other item or attribute must be set up or in process And an initial value of each of the fourth penalty costs corresponding to the fourth constraint that the accumulated actual operating time of any attribute must be equal to the accumulated actual operating time of the item having the attribute. The CPU sets the storage means based on the condition data stored in the storage means. ,
For each attribute virtually setup operation is processed in each material and the demographic virtual machines to be processed in the respective working by the item machinery, are set respectively in the storage means, said first first penalty cost assigned by the machine-specific time slot corresponding to the constraints, the second penalty cost assigned by item by time slot corresponding to the second constraint, the third corresponding to the third constraint penalty cost, and the fourth by item demographic schedule to optimize the evaluation criteria including a penalty cost corresponding to the fourth constraint, the CPU is, the schedule generation data stored in said storage means based on the acquisition, and for each time slot in another product category attribute, independently of the product category attribute-based schedule of other items and attribute And the step that,
Violation relating to the first, second, third and fourth constraints, whether all the violations of the first, second, third and fourth constraints are resolved in the acquired item-specific attribute schedule Determining by the CPU based on the degree of
If it is determined that at least one of the violations of the first, second, third, and fourth constraints has not been resolved, and the violation needs to be resolved, the first stored in the storage means the second, third and fourth penalty cost corresponding to the at least one violation has not been solved constraints of the penalty cost, the steps of the CPU is updated to the at least one violation is resolved ,
Each time the updating step is executed, the step of causing the CPU to re-execute the acquiring step ;
When all the violations of the first, second, third, and fourth constraints have been resolved, the CPU uses the output means as the production schedule that can execute the corresponding item-specific attribute-specific schedule. A program for executing the output step . Applicable to a production system in which a single machine processes items corresponding to each of the operations in a plurality of operations, and each operation can switch items with a set-up operation according to a plurality of attributes of the items. An apparatus for dynamic lot size scheduling with a set-up having a plurality of attributes to generate a production schedule to be performed,
The first area includes an item to be produced by the item machine using the one machine as an item machine, an attribute of the item, and the first area. Stores data for schedule generation including data on each machine of the machine for the item and virtual machine for virtually processing the setup work depending on the attribute of the item, and condition data applied in the dynamic lot size scheduling process Storage means
By item / time corresponding to the first penalty cost assigned to each machine / time slot corresponding to the first constraint on machine interference between items and between attributes in the same machine, corresponding to the second constraint on fulfillment of in-process inventory The second penalty cost assigned by slot, across the item and attribute, corresponds to the third constraint that if any item or attribute is being set up, no other item or attribute must be set up or in process And an initial value of each of the fourth penalty costs corresponding to the fourth constraint that the accumulated actual operating time of any attribute must be equal to the accumulated actual operating time of the item having the attribute. Initialization to be set in the second area of the storage means based on the condition data stored in the storage means And the stage,
For each attribute virtually setup operation is processed in each material and the demographic virtual machines to be processed in the respective working by the item machinery, are set respectively in the storage means, said first first penalty cost assigned by the machine-specific time slot corresponding to the constraints, the second penalty cost assigned by item by time slot corresponding to the second constraint, the third corresponding to the third constraint penalty cost, and the product category demographic schedule to optimize the evaluation criteria include a fourth penalty cost corresponding to the fourth constraint, on the basis of the schedule generation data stored in said storage means, for each and time slot in another product category attribute, to generate independently of the product category attribute-based schedule of other items and attribute schedule And generating means,
Violation relating to the first, second, third and fourth constraints, whether all the violations of the first, second, third and fourth constraints are resolved in the generated item-specific attribute schedule A constraint violation judging means for judging based on the degree of
If it is determined that at least one of the violations of the first, second, third, and fourth constraints has not been resolved, and the violation needs to be resolved, the first stored in the storage means Updating means for updating a penalty cost corresponding to a constraint in which the at least one violation is not resolved among the second, third and fourth penalty costs, so that the at least one violation is resolved;
Control means for controlling the schedule generation means so that the schedule by item attribute is newly generated by the schedule generation means after the update by the update means ;
Output means for outputting the corresponding item-specific attribute-specific schedule as the production schedule that can be executed when all of the violations of the first, second, third, and fourth constraints are resolved An apparatus for dynamic lot size scheduling characterized by:

Images