JP7147243B2 - Scheduling device, method and program - Google Patents

Description

The present invention relates to a scheduling device, method, and program for creating a schedule for production or physical distribution.

2. Description of the Related Art Scheduling tasks such as determining work for production and its time and products to be transported and their time are indispensable for smooth progress of business in the manufacturing and distribution industries. Scheduling work is constantly exposed to fluctuations such as new orders, production volume changes, and delivery time delays, so the work load is high, such as creating and correcting schedules each time. In addition, once a schedule has been created, it is necessary for people to review it many times, change the preconditions, and fix some parts. is the limit, scheduling needs to be done quickly. Therefore, scheduling support technology is essential.

As techniques for realizing this, mathematical programming methods that consider schedule creation as an optimization problem and seek the optimal solution, heuristic methods that seek quasi-optimal solutions, and the like have been proposed. The problems to be dealt with in the industrial world are the items that must be considered, the processes to be processed, the number of objects to be processed, and the time and date required for each process while coordinating the work that is processed over multiple processes. Complex constraints are set, such as the realization of set delivery dates and equipment (machinery) usage leveling, the need to avoid stockouts in each storage and the need to comply with storage capacity upper limits, so the scale is There was a problem that the number of calculations became enormous and the calculation time was long. Also, when creating a schedule, there are frequent changes in operations due to economic conditions and economic fluctuations, changes in constraints, changes in the priority of meeting the delivery date and leveling the use of equipment, or other purposes. The need for maintenance, such as additions, is pressing, and this load reduction has been desired.

JP-A-2002-328977 JP 2010-285053 A

Patent Literature 1 discloses a multi-item, multi-process lot size scheduling method using the Lagrangian decomposition adjustment method. In Patent Document 1, it is determined whether or not the machine interference is resolved and whether or not the work-in-progress inventory is sufficient. is updated. However, there is no guarantee that the update of the Lagrangian multiplier will eliminate machine interference or suffice inventory, and there is no guarantee that a workable schedule that satisfies all constraints will be obtained.

Patent Literature 2 discloses a technique related to recreating an operation plan for recreating an operation plan for railway vehicles or crews when a train operation schedule is changed. In Patent Document 2,
Using the Lagrangian relaxation method, the lower bound of the optimal solution is found and compared with the feasible solution of the primal problem to perform iterative processing. However, the calculation when using the Lagrangian relaxation method and the calculation when obtaining a feasible solution are significantly different, and the mechanism is complicated.

The present invention has been made in view of the above points, and is capable of finding a feasible solution that satisfies all constraints at a higher speed than before, even for a scheduling problem with large-scale and complicated constraints. To provide a schedule creating device or the like capable of creating a schedule related to production or physical distribution with a mechanism that can be maintained more easily than before.

The gist of the present invention for solving the above problems is as follows.
[1] A schedule creation device that creates a schedule for production or distribution based on a primal problem that is a mathematical programming problem formulated with constraints and objective functions,
a relaxation problem constructing means for constructing a relaxation problem in which part of the constraints are removed from the main problem and the objective function is modified;
a mitigation problem solving means for solving the mitigation problem constructed by the mitigation problem construction means;
fixation means for adding, to the main problem, a constraint expression for fixing conditions included in the main problem based on the result of solving the relaxed problem by the relaxed problem solving means;
and a solution finding means for solving the main problem in which the conditions are fixed by the fixing means.
[2] The relaxation problem constructing means constructs the Lagrangian relaxation problem in which the objective function is modified using Lagrangian multipliers so that the amount of violation of the removed constraint is penalized. The scheduling device according to [1].
[3] comprising updating means for updating the Lagrangian multiplier;
The schedule creation device according to [2], wherein the relaxation problem solving means solves the Lagrangian relaxation problem reflecting the Lagrangian multipliers updated by the updating means.
[4] The schedule creation device according to [2] or [3], wherein the relaxation problem construction means decomposes the Lagrangian relaxation problem by a Lagrangian decomposition adjustment method.
[5] The relaxation problem solving means obtains an optimal solution or a quasi-optimal solution by optimizing or quasi-optimizing in order to solve the relaxation problem constructed by the relaxation problem structuring means [ 1] to [4].
[6] The schedule according to any one of [1] to [5], which includes at least one step including a plurality of selectable machines and creates a schedule in a process of processing an object. creation device.
[7] The main problem is the upper limit of the number of objects that can be processed by the same machine at the same timing, the time required for processing each object, each process, and each machine, and the possible processing start time for each product and each process. The schedule creation device according to [6], wherein the purpose is to improve a predetermined operation index based on.
[8] The objective of the main problem is to minimize late-delivery costs based on the delivery time for each object and each process and the unit cost for late delivery for each object and each process. The schedule creation device according to [7], characterized by:
[9] According to any one of [6] to [8], the fixation means fixes the machine to be used for each object based on the result of solving by the relaxation problem-solving means. Scheduling device as described.
[10] The schedule creation according to any one of [6] to [9], wherein the fixing means fixes the processing order based on the result of solving by the relaxation problem solving means. Device.
[11] A schedule creation method for creating a schedule for production or distribution based on a primal problem that is a mathematical programming problem formulated with constraints and objective functions,
constructing a relaxed problem that removes some of the constraints from the primal problem and modifies the objective function;
solving the relaxation problem;
adding a constraint equation to the main problem for fixing conditions included in the main problem based on the result of solving the relaxed problem;
and a step of solving the main problem in which the conditions are fixed.
[12] A program for creating a production or distribution schedule based on a primal problem that is a mathematical programming problem formulated with constraints and objective functions,
a relaxation problem constructing means for constructing a relaxation problem in which part of the constraints are removed from the main problem and the objective function is modified;
a mitigation problem solving means for solving the mitigation problem constructed by the mitigation problem construction means;
fixation means for adding, to the main problem, a constraint expression for fixing conditions included in the main problem based on the result of solving the relaxed problem by the relaxed problem solving means;
A program for causing a computer to function as solving means for solving the main problem with the conditions fixed by the fixing means.

According to the present invention, even for a scheduling problem with large-scale and complicated constraints, a feasible solution that satisfies all constraints can be found faster than before, and maintenance is easier than before. can create a schedule for production or distribution.

It is a figure showing functional composition of a schedule creation device concerning an embodiment. It is a flowchart which shows the procedure of the schedule creation method by the schedule creation apparatus which concerns on embodiment. 1 is a diagram for explaining an outline of a multi-step parallel machine flow shop problem; FIG. 10 is a Gantt chart showing the results of solving the Lagrangian relaxation problem; FIG. 12 is a diagram showing transition of a Gantt chart showing the result of solving the Lagrangian relaxation problem by updating the Lagrangian multiplier; 4 is a Gantt chart showing the result of solving the main problem; FIG. 9 is a characteristic diagram showing changes in calculation time when the number of products to be handled increases.

Preferred embodiments of the present invention will now be described with reference to the accompanying drawings.
FIG. 1 shows the functional configuration of a schedule creation device 100 according to the embodiment. The schedule creation device 100 creates a schedule for production or physical distribution based on a mathematical programming problem formulated with constraints and objective functions. The schedule creation device 100 includes an input unit 101, a primal problem construction unit 102, a relaxation problem construction unit 103, a relaxation problem solving unit 104, a Lagrangian multiplier updating unit 105, a fixation unit 106, and a primal problem solving unit 107. and an output unit 108 .

The input unit 101 inputs information necessary for creating a schedule.
The main problem constructing unit 102 constructs a mathematical programming problem formulated with constraints and objective functions for creating a schedule as a main problem.

The relaxed problem constructing unit 103 removes some of the constraints from the mathematical programming problem constructed by the primal problem constructing unit 102, and constructs a relaxed problem in which the objective function is modified. As a relaxation problem, we construct a Lagrangian relaxation problem in which the objective function is modified with Lagrangian multipliers such that the amount of violation of the removed constraint is penalized. In this embodiment, the mitigation problem construction unit 103 functions as the mitigation problem construction means of the present invention.

The relaxation problem solving unit 104 solves the Lagrangian relaxation problem constructed by the relaxation problem construction unit 103 . Also, the Lagrangian multiplier update unit 105 updates the Lagrangian multiplier. The relaxation problem solving unit 104 and the Lagrangian multiplier updating unit 105 repeat updating the Lagrangian multiplier and solving the Lagrangian relaxation problem reflecting the Lagrangian multiplier until a predetermined condition is satisfied. In this embodiment, the relaxed problem solving unit 104 functions as the relaxed problem solving means of the present invention, and the Lagrangian multiplier updating unit 105 functions as the updating means of the present invention.

The fixing unit 106 fixes the conditions included in the mathematical programming problem constructed by the primal problem construction unit 102 based on the result obtained by the relaxed problem solving unit 104 . In this embodiment, the immobilizing section 106 functions as the immobilizing means of the present invention.
The main problem solving unit 107 solves the mathematical programming problem whose conditions are fixed by the fixing unit 106 . In this embodiment, the main problem solving section 107 functions as the solution finding means of the present invention.
The output unit 108 outputs a schedule that is the result of solving by the main problem solving unit 107 . The output here means, for example, displaying on a display (not shown) or transmitting to an external device of the apparatus 100 .

A specific example of the schedule creation method by the schedule creation device 100 will be described below. FIG. 2 is a flow chart showing the procedure of the schedule creation method by the schedule creation device 100. As shown in FIG.
In this embodiment, a schedule is created for the production process. The production process dealt with in this embodiment has a plurality of steps including at least one step including a plurality of selectable machines, and each step processes a product, which is an object. For simplicity of explanation, a multi-step parallel machine flow-shop problem, in which constraint expressions are limited to simple ones, is taken as an example. The flow shop problem refers to a problem in which the order of the production processes of products is the same. In this embodiment, the multi-step parallel machine flow-shop problem is taken as an example, but the problem may be a schedule problem of one process including a plurality of selectable machines or a job-shop problem, and the constraint equation may be Generality is not lost even if the problem becomes complicated and the scale of the problem increases. The job shop problem means that the production process differs for each product.

With reference to FIG. 3, an overview of the multi-step parallel machine flow shop problem handled in this embodiment will be described. Shown in FIG. 3 is a two-process, two-machine flow shop problem, where there are two processes, process P1 and process P2, where each process P1 and P2 has two machines J1 and J2 that can be selected. The direction from left to right in the figure represents time. A process 301 represents a predetermined process to be performed on a product, the length of which represents the implementation period, and the line connecting the processes 301 represents the transition of the product. It should be noted that although the names of the machines existing in process P1 and process P2 are the same, they are different machines.

A product i passes through all of the processes (p ∈ {1,2}) in sequence and is processed by any one of the machines (j ∈ {1,2}) as it passes through the processes. The same machine can only process up to N products at the same timing (at the same time). In this embodiment, N=1. The time required for processing each product, each process, and each machine is given in advance, and when processing is completed in a certain process, it is possible to move to the next process. In addition, the time at which processing can be started for each product and each process and the delivery time for each product and each process are given in advance. The main problem dealt with in this embodiment is to determine the machine to be used and the processing start time for each product, with the aim of minimizing the late delivery cost as an operational index that is desired to be improved while observing these constraints. In the example described below, let i={1, 2, . . . , 8}.

In step S1, the input unit 101 inputs information necessary for creating a schedule. These pieces of information may be input, for example, from a host computer (not shown) on the network, or may be directly input by the user.
Specifically, the user inputs the schedule creation period, which is the period for which the schedule is to be created, and the upper limit N of the number of products that can be processed by the same machine at the same time (N=1 in this embodiment).

Also, as shown in Table 1, the processing time for each product, each process, and each machine is entered.

In addition, as shown in Table 2, the processing start time is input for each product and each process. Here, the time at which processing can be started is given with 0 as the first time of the schedule creation period.

Also, as shown in Table 3, the delivery time for each product and each process is entered. Here, the delivery time is given with 0 as the first time of the schedule creation period.

Also, as shown in Table 4, the unit price (expense per day) for delay in delivery is entered for each product and each process.

In step S2, the primal problem constructing unit 102 constructs a mathematical programming problem formulated with constraints and objective functions as a primal problem. As described above, the main problem to be addressed in this embodiment is to determine the machine to be used and the processing start time for each product with the aim of minimizing the delivery delay cost. The constraints of the primal problem and the objective function are formulated using mathematical expressions. It should be noted that the construction of the main problem, the formulation of the constraint and the objective function referred to here mean that the information input by the input unit 101 is reflected in the framework of the mathematical formula given in advance by the user to obtain the constraint formula and the objective function. It means to make it a function. In the present embodiment, mixed integer linear programming is used as a technique for obtaining exact solutions, and constraints and objective functions are formulated according to this form.

In formulating, constants and variables to be determined (decision variables) are defined as follows, and values are set based on the information input in step S1.
[constant]
N: Upper limit of the number of products that can be processed by the same machine at the same time D _ipj : Processing time for process p of product i, machine j A _ip : Processing start time for process p of product i L _ip : Process p of product i delivery time c _ip : Unit cost for late delivery of process p of product i

In the present embodiment, time slots obtained by equally dividing one day (number of divisions M) are considered, and formulation is performed using time slots that are discrete times. For example, if M=4, the unit of the time slot is 6 hours, and the formulation is based on the image of discrete times in units of 6 hours. In this embodiment, M=10.

[decision variable/independent]
δ _itmpj : Variable set to 1 if product i starts processing in process p, machine j, t days, time slot m, otherwise 0 δT _itmpj : Product i, process p, machine j, t days, time A variable that is 1 if processing is in progress in slot m and 0 otherwise

[decision variable/dependent]
b _ip : Processing start time of process p of product i (day)
_{δJ ipj} : Variable set to 1 when product i is processed by process p and machine j;

Using the above-described constants and decision variables, the objective function is formulated as shown in Equation (1) to minimize late delivery costs.

Also, the constraint equations are formulated as, for example, equations (2) to (9). Equation (2) expresses that each product must be processed exactly once in each step. Equation (3) expresses that each product can use the same machine only once. Equation (4) represents a relational expression indicating which time slot the processing start time b _ip in each process of each product corresponds to. Equation (5) expresses that when a machine with a certain process for a product is used, the process is in progress for the processing time from the processing start time. Equation (6) expresses that the upper limit of the number of products that can be processed by the same machine at one time is N. Equation (7) expresses that if δ _itmpj is 1, then δJ _ipj is also 1. Equation (8) indicates that when a product is processed, the processing of the next process is started after the processing of the previous process is completed. Expression (9) is an expression that defines the amount of time by which the end of processing is delayed with respect to the delivery time _Lip of the product as delivery delay.

In step S3, the relaxation problem constructing unit 103 constructs a Lagrangian relaxation problem in which a part of the constraint equation is removed from the mathematical programming problem constructed in step S2 and the objective function is modified. In the Lagrangian relaxation problem, the quantity that violates the constraint is defined as a new formula as a violation quantity for the removed constraint equation, and the violation quantity is minimized by incorporating that formula (for example, a linear expression) into the objective function. be formulated as
For formulation, the following w _tmpj (constants) are provided.
w _tmpj : Penalty unit price per time slot for occupation of machine j in process p by product i Initial value of penalty unit price w _tmpj , given as a given condition as shown in Table 5, the value is set based on this information be done. This w _tmpj is called the Lagrangian multiplier.

In this embodiment, the expression (6) is _relaxed , that is, removed from the _constraint , and the expression Modify the objective function using the Lagrange multiplier w _tmpj as in (1-2). The larger the Lagrangian multiplier w _tmpj , the less the amount of violations the optimization or semi-optimization will be performed.

Here, the Lagrangian relaxation problem may be decomposed by the Lagrangian decomposition adjustment method. Focusing on i, the objective function of formula (1-2) can be transformed into formula (1-3). In equation (1-3), since the last term is a constant, it can be omitted and can be transformed into equation (1-4). Thus, the constraint equations (equations (2) to (5), equations (7) to (9)) and the objective function (equation (1-4)) of the Lagrangian relaxation problem are respectively Since the problem can be solved separately, you can solve the problem separately.

It should be noted that the user predefines which constraint equations are to be removed and how the amount of violation is incorporated into the objective function, and the relaxation problem construction unit 103 constructs the Lagrangian relaxation problem accordingly. Alternatively, the mitigation problem construction unit 103 receives an instruction from the user, for example, via an interactive user interface, and according to the instruction, decides each time which constraint equation to remove and how to incorporate the amount of violation into the objective function. may

In step S4, the relaxation problem-solving unit 104 performs optimization or semi-optimization to solve the Lagrangian relaxation problem constructed in step S3, thereby obtaining an optimal solution or a sub-optimal solution close to the optimal solution. For example, the branch-and-bound method is used as an optimization technique to obtain an exact solution of the Lagrangian relaxation problem. Note that the branch-and-bound method is a generally known method, and its description is omitted here. Also, a commercially available solver implemented with an optimization or semi-optimization technique may be used to solve the Lagrangian relaxation problem.
By this solution, the constraint formulas (formulas (2) to (5), formulas (7) to (9)) are satisfied, and any of the objective functions (formulas (1-2) to (1-4) ) is computed. That is, the machine to be used and the processing start time for each product are determined by relaxing the upper limit on the number of products that can be processed by the same machine at the same time, which is expressed by the equation (6).

Table 6 and FIG. 4 show the results of solving the Lagrangian relaxation problem. In the Gantt chart of FIG. 4, the horizontal axis represents time. Also, the rectangles represent the execution period of each process, and the number shown in each rectangle represents the product number. When the Gantt chart is displayed on the screen as shown in FIG. 4, each rectangle is colored (represented by dots in FIGS. 4, 5, and 6). Since the upper limit on the number of products that can be processed by the same machine at the same time has been relaxed, there are cases where the same machine is used at the same time. 4, the density of dots is increased in FIG. 5). A dashed line is drawn for each product from the processing start time to the processing start time. A solid line represents the time from the end of processing to the delivery date, and is drawn for each product.

In step S5, the Lagrangian multiplier update unit 105 determines whether or not to update the Lagrangian multiplier _{w_tmpj} . In this embodiment, the update of the Lagrangian multiplier is terminated at the loop count of 21 as described below. If the Lagrangian multiplier w _tmpj needs to be updated (step S5; Yes), the process proceeds to step S6; otherwise (step S5; No), the process proceeds to step S7.

In step S6, the Lagrangian multiplier update unit 105 updates the Lagrangian multiplier, and then returns to step S4.
In this embodiment, the Lagrangian multiplier is updated according to equation (10). l indicates the number of loops, and (l) on the right side of the constant and decision variable indicates the value taken by the constant and decision variable in each loop. Also, w indicates a coefficient for updating the Lagrangian multiplier, and in this embodiment, w=0.5. In equation (10), the larger the violation amount (Σ _i ^(l) δT _itmpj −N) at the loop count l, the larger the Lagrangian multiplier w _tmpj ^(l+1) in the next loop. . Also, as the number of loops increases, the amount of change in the Lagrangian multiplier w _tmpj ^(l+1) in the next loop is suppressed.

A condition for ending the update of the Lagrangian multiplier is set in advance. For example, a threshold for the amount of change in the Lagrangian multiplier from the previous loop and a threshold for the number of loops are set in advance, and whether or not to update the Lagrangian multiplier is determined based on comparison with these thresholds. In this embodiment, the update of the Lagrangian multiplier is terminated at the loop count of 21 .

FIG. 5 shows the transition of a Gantt chart showing the result of solving the Lagrangian relaxation problem by updating the Lagrangian multipliers. As the number of loops increases, the number of dark-colored rectangles (overlapping rectangles) decreases, indicating that the upper limit on the number of products that can be processed by the same machine at the same time is gradually being complied with.

In step S7, the fixing unit 106 fixes the conditions included in the mathematical programming problem based on the result obtained in step S4.
For example, the fixation unit 106 selectively fixes a machine that is a feasible solution to be used among the use machines for each product obtained by solving the Lagrangian relaxation problem in step S4. If the result of solving the Lagrangian relaxation problem in the 21st loop is, for example, that machine 2 is used in process 1 of product 1, add a fixed constraint equation such as equation (11) to the main problem. .

Further, the fixation unit 106 selectively fixes the processing start times obtained by solving the Lagrangian relaxation problem in step S4 as those to be processed in the order of feasible solutions. As a result of solving the Lagrangian relaxation problem in the 21st loop, for example, when machine 1 in process 1 processes product 1 and then product 2 in that order, a fixed constraint equation such as equation (12) is added to the main problem. do.
b ₁ , ₁ ≤ b ₂ , ₁ (12)

It should be noted that which condition included in the mathematical programming problem is to be fixed is defined in advance by the user, and the fixing unit 106 fixes accordingly. Alternatively, the fixation unit 106 may receive an instruction from the user via, for example, an interactive user interface, and may determine each time which condition included in the mathematical programming problem is to be fixed according to the instruction. .

In step S8, the main problem solving unit 107 solves the mathematical programming problem whose conditions are fixed in step S7. The main problem solving unit 107 solves the main problem in a state in which the machine used for each product and the order of processing are fixed, so that the main problem can be solved in a short calculation time. Moreover, in the solution of the Lagrangian relaxation problem, the upper limit of the number of products that can be processed by the same machine at the same time was relaxed, but here we can obtain a feasible schedule that satisfies all the required constraints. .

Table 7 and FIG. 6 show the results of solving the main problem. FIG. 6 represents a Gantt chart like FIG. It shows that there are no dark colored rectangles (overlapping rectangles) and that the upper limit of the number of products that can be processed by the same machine at the same time is obeyed. Also, the delivery delay cost in this example is a sufficiently small value of 0.31.

At step S9, the output unit 108 outputs the schedule resulting from the solution obtained at step S8. For example, as shown in FIG. 6, a Gantt chart showing the machines to be used and the processing start times for each product, determined for the purpose of keeping the constraints and minimizing the delivery delay costs, is displayed on the screen.

FIG. 7 shows changes in calculation time when the number of products handled increases. A comparison was made between the case where the main problem was solved with 25 loops and 50 loops by applying the above embodiment and the case where the main problem was solved all at once using the branch and bound method.
When the branch-and-bound method was used to solve the main problem all at once, as indicated by the solid line, when the number of products exceeded 100, the calculation time abruptly increased, and a solution could not even be obtained. Here, the calculation was terminated at 600 seconds.
On the other hand, when the main problem is solved by applying the above embodiment, as indicated by the dashed line and the dashed line, the calculation time does not increase significantly even when the number of products increases, and the calculation time is stable and fast. It is possible to obtain a solution.

As described above, when creating a schedule related to production or distribution based on a mathematical programming problem formulated with constraints and objective functions, a relaxation problem that relaxes the mathematical programming problem is constructed, solved, and By fixing the conditions contained in the mathematical programming problem based on the results, even for large-scale scheduling problems with complex constraints, a feasible solution that satisfies all constraints can be generated faster than before. can be asked for. Also, when creating a single schedule, it is easier to modify when deleting constraints or adding new constraints, compared to creating a schedule with multiple, wildly different scheduling calculations. It is possible to create a schedule with a mechanism that requires less and can be easily maintained.

Note that the schedule creation device 100 of the above embodiment is implemented by a computer device including, for example, a CPU, a ROM, a RAM, and the like. Although the schedule creation device 100 is illustrated as one device in FIG. 1, it may be configured by, for example, a plurality of devices.
Further, the various functions of the schedule creation device 100 of the above embodiment are to supply software (programs) to a system or device via a network or various storage media, and the computer of the system or device to read and execute the programs. It can also be realized by
The above-described embodiments are merely specific examples for carrying out the present invention, and the technical scope of the present invention should not be construed to be limited by these. That is, the present invention can be embodied in various forms without departing from its technical concept or main features.

100: Schedule Creation Device 101: Input Unit 102: Main Problem Construction Unit 103: Relaxation Problem Construction Unit 104: Relaxation Problem Solving Unit 105: Lagrange Multiplier Update Unit 106: Fixation Unit 107: Main Problem Solving Unit 108: Output Unit

Claims (12)

A scheduling device for creating a schedule for production or distribution based on a primal problem, which is a mathematical programming problem formulated with constraints and objective functions,
a relaxation problem constructing means for constructing a relaxation problem in which part of the constraints are removed from the main problem and the objective function is modified;
a mitigation problem solving means for solving the mitigation problem constructed by the mitigation problem construction means;
fixation means for adding, to the main problem, a constraint expression for fixing conditions included in the main problem based on the result of solving the relaxed problem by the relaxed problem solving means;
and a solution finding means for solving the main problem in which the conditions are fixed by the fixing means. 2. The relaxation problem constructing means constructs the Lagrangian relaxation problem in which the objective function is modified using Lagrangian multipliers so that the amount of violation of the removed constraint is penalized. The scheduling device according to . comprising updating means for updating the Lagrangian multiplier;
3. The schedule generating apparatus according to claim 2, wherein said relaxation problem solving means solves the Lagrangian relaxation problem reflecting the Lagrangian multipliers updated by said updating means. 4. The schedule creation device according to claim 2, wherein said relaxation problem construction means decomposes the Lagrangian relaxation problem by a Lagrangian decomposition adjustment method. 3. The relaxation problem solving means obtains an optimal solution or a semi-optimal solution by optimizing or semi-optimizing in order to solve the relaxation problem constructed by the relaxation problem constructing means. 5. The schedule creation device according to any one of 4. 6. A scheduling device according to any one of claims 1 to 5, characterized in that it comprises at least one step involving a plurality of selectable machines and creates a schedule for a process of processing an object. The main problem is based on the upper limit of the number of objects that can be processed by the same machine at the same timing, the time required for processing each object, each process, and each machine, and the processing start time for each product and each process. 7. The schedule creation device according to claim 6, wherein the purpose is to improve a predetermined operational index. The main problem is characterized in that it aims at minimizing the late delivery cost based on the delivery time for each object and each process and the unit price for delay in delivery for each object and each process. The schedule creation device according to claim 7. 9. The schedule creation device according to claim 6, wherein said fixation means fixes a machine to be used for each object based on the result of solving by said relaxation problem-solving means. . 10. The schedule generating apparatus according to claim 6, wherein said fixing means fixes the processing order based on the result obtained by said relaxation problem solving means. A schedule creation method for creating a schedule for production or distribution based on a primal problem that is a mathematical programming problem formulated with constraints and objective functions,
constructing a relaxed problem that removes some of the constraints from the primal problem and modifies the objective function;
solving the relaxation problem;
adding a constraint equation to the main problem for fixing conditions included in the main problem based on the result of solving the relaxed problem;
and a step of solving the main problem in which the conditions are fixed. A program for creating a schedule related to production or distribution based on a primal problem that is a mathematical programming problem formulated with constraints and objective functions,
a relaxation problem constructing means for constructing a relaxation problem in which part of the constraints are removed from the main problem and the objective function is modified;
a mitigation problem solving means for solving the mitigation problem constructed by the mitigation problem construction means;
fixation means for adding, to the main problem, a constraint expression for fixing conditions included in the main problem based on the result of solving the relaxed problem by the relaxed problem solving means;
A program for causing a computer to function as solving means for solving the main problem with the conditions fixed by the fixing means.

Images