SCHEDULING METHOD AND INFORMATION PROCESSING APPARATUS

An information processing apparatus obtains system data representing a system including first objects that each undergo a state change in response to an operation and second objects that each undergo a state change in response to the state change of one or more first objects related thereto and assigning each second object a cost that changes in response to the state change. The information processing apparatus determines, for each second object, the number of unchanged first objects among the related first objects, a change in total cost caused by operating the unchanged first objects, and an index value that increases as the number of unchanged first objects decreases and increases as the change increases. The information processing apparatus generates schedule data representing an operation sequence for the first objects such that the second objects undergo the state change preferentially in descending order of index values.

CROSS-REFERENCE TO RELATED APPLICATION

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2023-147488, filed on Sep. 12, 2023, the entire contents of which are incorporated herein by reference.

FIELD

The embodiments discussed herein relate to a scheduling method and an information processing apparatus.

BACKGROUND

There are cases in which a computer solves an optimization problem to determine a sequence of operations for a plurality of objects included in a system, taking into account the cost of the entire system. The system, which is an optimization target, may include two types of objects: group A and group B. Each object in the group A undergoes a state change in response to an operation. Each object in the group B undergoes a state change in response to the state changes of its one or more related objects among the objects of the group A. Each of some or all of the objects is assigned a cost that changes in response to a state change.

A change in the sequence of operations for the objects in the group A consequently changes the timing when each object in the group B undergoes the state change. Therefore, if the sequence of operations is changed, a curve representing the temporal change in the unit time cost of the entire system is changed accordingly. For example, the computer searches for a sequence of operations that minimizes the system cost obtained by integrating the unit time cost.

For example, there is proposed a circuit migration sequence generation method for determining a circuit migration sequence in which a plurality of circuits in a circuit-switched network are to be migrated. Each circuit passes through at least one of a plurality of circuit switching devices included in the circuit-switched network. This proposed method calculates, for each circuit, a score representing the number of circuit switching devices that is no longer needed after the migration of the circuit. The proposed method repeats a process of removing the circuit with the highest score and recalculating the score for each remaining circuit until no more circuits exist.

Here, for a just-in-time (JIT) manufacturing system, there is proposed a modeling method of modeling a process chain such that a state change in a replenishment process of one component causes a state change in a replenishment process of another component. Further, there is proposed a change management system in which an operation plan for changing the states of a plurality of components is created on the basis of the dependence relationships between the plurality of components, the current state of each component, and a desired state of each component after the change. Still further, there is proposed a resource allocation apparatus that manages resources to be allocated to network nodes through which a plurality of communication flows pass on the basis of the network nodes and their data traffic amounts.

SUMMARY

According to one aspect, there is provided a non-transitory computer-readable storage medium storing a computer program that causes a computer to perform a process including: obtaining system data representing a system including a plurality of first objects that each undergo a first state change in response to an operation and a plurality of second objects that are each related to one or more first objects among the plurality of first objects and that each undergo a second state change in response to the first state change of the one or more first objects related thereto, the system data assigning each of the plurality of second objects a cost that changes in response to the second state change; determining, for each of the plurality of second objects, based on the system data, a number of unchanged first objects that are yet to undergo the first state change among the one or more first objects related thereto, and a change in total cost defined for the system using costs of the plurality of second objects, the change in the total cost being caused by performing the operation on the unchanged first objects, and determining, for each of the plurality of second objects, an index value that increases as the number of unchanged first objects decreases and increases as the change in the total cost increases; and generating schedule data representing a sequence in which the operation is to be performed on the plurality of first objects such that the plurality of second objects undergo the second state change preferentially in descending order of the index value.

DESCRIPTION OF EMBODIMENTS

As described above, there are cases in which a computer searches for a schedule indicating a sequence of operations for one type of objects among two types of objects included in a system. However, the heuristics provided by the circuit migration sequence generation method taught in U.S. Patent Application Publication No. 2022/0094571 may sometimes fail to create a highly efficient schedule, and therefore there is room for improvement.

For example, in the circuit migration sequence generation method taught in U.S. Patent Application Publication No. 2022/0094571, it may happen that no circuit switching devices get into an unused state regardless of which circuit is removed in an early stage of the search. This method therefore may sometimes fail to optimize the sequence of operations in the early stage, even with the use of the above-described scores.

First Embodiment

A first embodiment will now be described.

FIG.1is a view for describing an information processing apparatus according to the first embodiment.

The information processing apparatus10is designed to search for an appropriate operation sequence of operations for a plurality of objects included in a system in terms of the cost of the entire system and generate schedule data representing the operation sequence. The information processing apparatus10may be a client device or a server device. The information processing apparatus10may be called a computer, a scheduling apparatus, or an optimization apparatus.

The information processing apparatus10includes a storage unit11and a processing unit12. The storage unit11may be a volatile semiconductor memory, such as a random access memory (RAM). Alternatively, the storage unit11may be a non-volatile storage device, such as a hard disk drive (HDD) or a flash memory.

For example, the processing unit12is a processor such as a central processing unit (CPU), a graphics processing unit (GPU), or a digital signal processor (DSP). Note that the processing unit12may include an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), or another electronic circuit. For example, the processor runs programs stored in a memory such as a RAM (which may be the storage unit11). The information processing apparatus10may include a plurality of processors. A set of the processors may be called a multiprocessor or simply a “processor.” A processor may be called “processor circuitry”. Among a plurality of processing steps to be executed by the information processing apparatus10, one processor may execute a processing step while another processor may execute another processing step.

The storage unit11stores system data13. The system data13may be generated by a user. The information processing apparatus10may accept the system data13input by the user, or may receive the system data13from another information processing apparatus. The system data13represents a system including a plurality of objects. The plurality of objects include a plurality of first objects including objects14-1to14-4and a plurality of second objects including objects15-1to15-3.

For example, the plurality of first objects are of the same type and make up a first group. The plurality of second objects are of the same type and make up a second group. Note that the first objects and the second objects may be of different types. Examples of the object types include device, product, user, organization, and others. As an example, the first objects are circuits, and the second objects are circuit switching devices that are used by the circuits. As another example, the first objects are manufacturing devices, and the second objects are products that are manufactured by the manufacturing devices.

Each second object is related to one or more first objects. For example, this relation may be a relationship in which one or more circuits share a certain circuit switching device or a relationship in which one or more manufacturing devices are used to produce a certain product. A certain first object may be related to two or more second objects. For example, the object15-1is related to the objects14-1to14-3. The objects15-2is related to the objects14-2and14-4. The object15-3is related to the object14-4.

Each first object undergoes a first state change in response to an operation. Each second object undergoes a second state change in response to the first state changes of its one or more related first objects. A state change may be called a state transition, and changing a state may be called triggering or firing. For example, a state change indicates a shutdown from ON to OFF or a startup from OFF to ON. For example, the operation indicates an ON-OFF switching operation for the first objects. As an example, the first state change is the shutdown of a circuit, and the second state change is the shutdown of a circuit switching device. As another example, the first state change is the startup of a manufacturing device, and the second state change is the startup of production of a product.

In the case where a certain second object is related to two or more first objects, a condition to cause the second state change may be an AND condition. Under this condition, the second state change occurs when all of the two or more related first objects undergo the first state change. As an example, a circuit switching device is shut down when all circuits related thereto are shut down. As another example, the production of a product is started when all manufacturing devices related thereto are started.

The system data13assigns each of the plurality of second objects a cost that changes in response to the second state change. The system data13may define costs before and after the second state change or may define the difference in the cost before and after the second state change. For example, the cost is a unit time cost that is incurred by a second object being ON. The plurality of second objects may be assigned the same cost or different costs. In addition, the system data13may assign a cost to each of some or all of the plurality of first objects. The cost of each first object may change in response to the first state change.

For example, each of the objects15-1to15-3has a cost of 1 before the second state change and a cost of 0 after the second state change. This means that, when the objects15-1to15-3are shut down, their unit time costs decrease by 1.

The system data13may be represented as a graph with a plurality of nodes and a plurality of edges. In this case, the plurality of first objects and the plurality of second objects are represented as nodes. The relations between the first objects and the second objects are represented by edges between the nodes. The cost of an object corresponds to an attribute that the node has. This graph has edges between nodes of different groups, but does not have edges between the nodes of the same group. That is, this graph is a bipartite graph.

The processing unit12generates schedule data17representing an operation sequence for the plurality of first objects on the basis of the system data13. To this end, the processing unit12calculates an index value for each of the plurality of second objects. For example, the processing unit12calculates an index value16-1for the object15-1, an index value16-2for the object15-2, and an index value16-3for the object15-3. The processing unit12determines the operation sequence for the plurality of first objects such that the second objects undergo the second state change preferentially in descending order of index values.

In calculating the index value for a second object, the processing unit12calculates the number of unchanged first objects that are yet to undergo the first state change among its one or more related first objects. In addition, the processing unit12calculates a change in total cost caused by performing the operation on the unchanged first objects. Then, the processing unit12calculates the index value that increases as the number of unchanged first objects decreases and increases as the change increases. The index value may be proportional to the change and inversely proportional to the number of unchanged first objects, and may be calculated by dividing the change by the number of unchanged first objects.

The total cost is a cost defined for the entire system using the current costs of the plurality of second objects. For example, the total cost is the sum of the current costs of the plurality of second objects. Note that if a cost is assigned to each of some or all of the first objects as well, the total cost may be defined further using the current costs of the first objects. For example, the total cost is the sum of the current costs of the plurality of first objects and the current costs of the plurality of second objects.

When the operation is performed on the unchanged first objects related to a second object, the unchanged first objects each undergo the first state change, which in turn causes the second object in question to undergo the second state change. Therefore, the cost of the second object in question changes, and the total cost changes accordingly. For example, the cost of the second object decreases, and the total cost decreases accordingly. Thus, the change in the total cost may sometimes be equal to the difference in the cost of the second object in question before and after the second state change.

Note that, in the case where a cost is assigned to each of some or all of the first objects as well, the costs of the first objects operated may change, and the total cost may further change accordingly. For example, the costs of the first objects operated may decrease, and the total cost may further decrease accordingly. Thus, the change in the total cost may sometimes be the sum of the difference in the cost of the second object in question and the differences in the cost of the first objects operated.

For example, assume that all objects14-1to14-4are yet to undergo the first state change and all objects15-1to15-3are yet to undergo the second state change. The number of unchanged first objects related to the object15-1is 3, and the change in the total cost caused by operating the three first objects is 1. Therefore, the index value16-1of the object15-1is calculated as ⅓=0.333.

Further, the number of unchanged first objects related to the object15-2is 2, and the change in the total cost caused by operating the two first objects is 1. Therefore, the index value16-2of the object15-2is calculated as ½=0.500. Still further, the number of unchanged first objects related to the object15-3is 1, and the change in the total cost caused by operating the one first object is 1. Therefore, the index value16-3of the object15-3is calculated as 1/1=1.000.

For example, the processing unit12selects the object15-3with the maximum index value from the objects15-1to15-3. The processing unit12then specifies the object14-4that needs to be operated in order to cause the second state change in the object15-3, and sets the object14-4in the first place in the operation sequence. In the case where two or more unchanged first objects are related to the selected second object, the processing unit12may arrange these two or more first objects in a random order or in descending order of their costs in the operation sequence.

Each time selecting one second object that undergoes the second state change, the processing unit12may recalculate the index value for each unselected second object that has not been selected. In this case, the processing unit12selects one second object that undergoes the second state change next, on the basis of the recalculated index values. For example, the processing unit12selects the second object with the maximum recalculated index value.

In recalculating the index values, the processing unit12regards the first objects that already have their placements in the operation sequence as having undergone the first state change and regards the second objects already selected as having undergone the second state change. In this connection, the processing unit12may recalculate the index value for each unselected second object each time selecting a certain number of second objects that undergo the second state change. In this case, for example, the processing unit12selects the certain number of second objects in descending order of index values.

For example, after the operation is performed on the object14-4, the index value of the object15-1is calculated as ⅓=0.333, and the index value of the object15-2is calculated as 1/1=1.000. Therefore, the processing unit12selects the object15-2next, and sets the object14-2in the second place in the operation sequence. Lastly, the processing unit12selects the object15-1, and sets the objects14-1and14-3in the third and fourth places in the operation sequence.

The processing unit12outputs the generated schedule data17. The processing unit12may store the schedule data17in a non-volatile storage device, may display it on a display device, or may send it to another information processing apparatus.

As described above, the information processing apparatus10of the first embodiment obtains the system data13. The system data13represents a system including a plurality of first objects that each undergo a first state change in response to an operation and a plurality of second objects that each undergo a second state change in response to the first state changes of its one or more related first objects. In addition, the system data13assigns each of the plurality of second objects a cost that changes in response to the second state change.

The information processing apparatus10calculates, for each second object, the number of unchanged first objects that are yet to undergo the first state change among the related first objects, on the basis of the system data13. In addition, the information processing apparatus10calculates the change in total cost defined for the system using the costs of the plurality of second objects, the change being caused by performing the operation on the unchanged first objects. The information processing apparatus10then calculates an index value that increases as the number of unchanged first objects decreases and increases as the change increases.

Then, the information processing apparatus10generates the schedule data17representing the operation sequence for the plurality of first objects such that the plurality of second objects undergo the second state change preferentially in descending order of index values.

In the manner described above, the schedule data17representing a preferable operation sequence for the plurality of first objects is generated in terms of the total cost. For example, the system cost obtained by integrating the unit time cost of the entire system over a predetermined period is reduced. This means streamlining the operation of the system during the transition period during which the first state change and the second state change occur.

In addition, as compared to conventional heuristics, the optimization accuracy is improved, which allows for the generation of the schedule data17representing a highly efficient schedule. For example, another scheduling method is considered, which counts, for each first object, the number of second objects that undergo a second state change when an operation is performed on the first object, and selects the first objects preferentially in descending order of the number of second objects. However, this scheduling method does not take into account such second objects that each undergo the second state change when two or more first objects are operated, which may result in low search accuracy in the early stage of the search where many unchanged first objects exist.

By contrast, the information processing apparatus10calculates an index value for each second object. A higher index value indicates that the total cost significantly changes by a small number of first objects being operated. Therefore, by causing the second objects to undergo the second state change preferentially in descending order of index values, the time efficiency of the operation on the first objects is improved.

In this connection, the information processing apparatus10may recalculate the index value for each unselected second object each time it selects one second object that undergoes the second state change. This allows for the creation of a highly efficient schedule even for lower-ranked objects in the operation sequence.

In addition, in the case where the same index value is calculated for two or more second objects, the information processing apparatus10may generate two or more patterns each representing the result of tentatively selecting a different one of the two or more second objects and recalculating the index value for each unselected second object. Then, by comparing the generated two or more patterns, the information processing apparatus10may retrospectively determine the operation sequence for the second objects with the same index value. This allows for the determination of the operation sequence for higher-ranked objects taking into account the optimization status of lower-ranked objects even in the case where it is difficult to determine the operation sequence for the higher-ranked objects alone, which results in creating an overall highly-efficient schedule.

In addition, the system data13may assign a cost to each first object, and the total cost of the system may be defined using the costs of the plurality of first objects and the costs of the plurality of second objects. This makes it possible to correctly model the system according to the types of the objects and define an appropriate optimization problem. Furthermore, an index value may be calculated by dividing the change in the total cost by the number of unchanged first objects. This allows for a simple representation of the relationship in which the index value is proportional to the change and is inversely proportional to the number of unchanged first objects.

Second Embodiment

A second embodiment will now be described.

An information processing apparatus100of the second embodiment is designed to model the relationships between two types of objects included in a system and solve an optimization problem to optimize an operation sequence of operations for one type of objects. The information processing apparatus100may be a client device or a server device. The information processing apparatus100may be called a computer, a scheduling apparatus, or an optimization apparatus. Note that the information processing apparatus100corresponds to the information processing apparatus10of the first embodiment.

FIG.2illustrates an example of the hardware configuration of the information processing apparatus according to the second embodiment.

The information processing apparatus100includes a CPU101, a RAM102, an HDD103, a GPU104, an input interface105, a media reader106, and a communication interface107, which are connected to a bus. The CPU101corresponds to the processing unit12of the first embodiment. The RAM102or HDD103corresponds to the storage unit11of the first embodiment.

The CPU101is a processor that executes program commands. The CPU101loads programs and data from the HDD103to the RAM102and executes the programs. The information processing apparatus100may be provided with a plurality of processors.

The RAM102is a volatile semiconductor memory that temporarily stores programs that are run by the CPU101, and data that is used by the CPU101in processing. The information processing apparatus100may be provided with a different type of volatile memory than RAM.

The HDD103is a non-volatile storage device that stores software programs such as operating system (OS), middleware, and application software, and data. The information processing apparatus100may be provided with another type of non-volatile storage device such as a flash memory or a solid state drive (SSD).

The GPU104performs image processing in collaboration with the CPU101and outputs images to a display device111connected to the information processing apparatus100. Examples of the display device111include a cathode ray tube (CRT) display, a liquid crystal display, an organic electro-luminescence (EL) display, and a projector. Another type of output device such as a printer may be connected to the information processing apparatus100.

The GPU104may be used as a general-purpose computing on graphics processing unit (GPGPU). The GPU104may be able to run programs in accordance with commands from the CPU101. The information processing apparatus100may be provided with a volatile semiconductor memory other than the RAM102as a GPU memory.

The input interface105receives an input signal from an input device112connected to the information processing apparatus100. Examples of the input device112include a mouse, a touch panel, and a keyboard. A plurality of input devices may be connected to the information processing apparatus100.

The media reader106is a reading device that reads programs and data from a storage medium113. Examples of the storage medium113include a magnetic disk, an optical disc, and a semiconductor memory. Magnetic disks include flexible disks (FDs) and HDDs. Optical discs include compact discs (CDs) and digital versatile discs (DVDs). The media reader106copies the programs and data from the storage medium113to another storage medium such as the RAM102or the HDD103. The read programs may be run by the CPU101.

The storage medium113may be a portable storage medium. The storage medium113may be used to distribute the programs and data. The storage medium113and HDD103may be referred to as computer-readable storage media.

The communication interface107communicates with other information processing apparatuses over a network114. The communication interface107may be a wired communication interface that is connected to a wired communication device such as a switch or a router, or may be a wireless communication interface that is connected to a wireless communication device such as a base station or an access point.

The following describes a graph obtained by modeling an optimization target system.

FIG.3illustrates a first example of a graph representing the relationships between objects.

The graph131is a bipartite graph with a plurality of nodes and a plurality of edges, in which the nodes are grouped into two types. The graph131may be a directed graph, in which the edges have direction, or an undirected graph, in which the edges have no direction. A user may create the graph131, or the information processing apparatus100may receive the graph131from another information processing apparatus.

The graph131includes nodes132-1to132-5and133-1to133-4. The nodes132-1to132-5represent different objects of the same type. The objects represented by the nodes132-1to132-5belong to a group A. In the following description, the objects belonging to the group A may be referred to as objects a. The nodes133-1to133-4represent different objects of the same type. The objects represented by the nodes133-1to133-4belong to a group B. In the following description, the objects belonging to the group B may be referred to as objects b.

An object may be a tangible object or a set of tangible objects, or may be an intangible object or a set of intangible objects. For example, an object may be a device, a building, a land, a set of devices, a person, or a group that is a set of people. Each object a in the group A undergoes a state change in response to an operation. In the second embodiment, changing a state may be called triggering or firing. The operation may be performed manually, or may be performed by an apparatus such as a computer according to a schedule. In the second embodiment, the objects a have two states: ON and OFF, and triggering indicates switching between ON and OFF.

Each object b in the group B is triggered in response to the triggering of its one or more related objects a. In the second embodiment, the objects b have two states: ON and OFF, and triggering indicates switching between ON and OFF. In the graph131, an object a related to an object b is represented by an edge. An object a may be related to two or more objects b, or an object b may be related to two or more objects a.

The node133-1is connected to the nodes132-1to132-3with edges. The node133-2is connected to the nodes132-2and132-4with edges. The node133-3is connected to the node132-4with an edge. The node133-4is connected to the nodes132-2and132-5with edges. In this connection, the objects in the group A are not related to each other, and therefore no edge exists between the nodes132-1to132-5. Similarly, the objects in the group B are not related to each other, and no edge exists between the nodes133-1to133-4. That is to say, the graph131is a bipartite graph.

As described above, an object b may be related to two or more objects a. In this case, a triggering condition for the object b may be AND or OR. The AND condition means that all of the two or more related objects a need to be triggered, whereas the OR condition means that at least one of the two or more related objects a needs to be triggered. Whether the triggering condition is AND or OR depends on an optimization target system. Therefore, the triggering condition is specified by the user. The second embodiment provides description of both an optimization under the AND condition and an optimization under the OR condition. In this connection, in the second embodiment, it is assumed that the same triggering condition is applied to all the objects b.

A cost C is defined for each object a in the group A. The cost C may change in response to the triggering of the object a, and may differ between the objects a. The cost C of an object a represents a unit time cost that is incurred by the object a per unit time. In the second embodiment, to simplify an optimization problem, the cost before or after triggering, serving as a base cost, is set to 0, and the cost C denotes the difference in the cost caused by the triggering.

In addition, a cost D is defined for each object b in the group B. The cost D may change in response to the triggering of the object b, and may differ between the objects b. The cost D of an object b represents a unit time cost that is incurred by the object b per unit time. In the second embodiment, to simplify the optimization problem, the cost before or after triggering, serving as a base cost, is set to 0, and the cost D denotes the difference in the cost caused by the triggering.

In the second embodiment, a typical shutdown sequence problem as follows will be considered as an example. At the start time, all objects a are ON, and all objects b are ON. At the end time, all objects a are OFF, and all objects b are OFF. In the transition period from the start time to the end time, the user operates the objects a one by one, one per unit time, to switch the state of each operated object a from ON to OFF. Each object b switches from ON to OFF when all or at least one of its one or more related objects a is switched to OFF.

The unit time cost of an object a being OFF is lower than or equal to that of the object a being ON. The cost C is the difference calculated by subtracting the unit time cost during OFF from the unit time cost during ON and has a value of 0 or greater. In the second embodiment, to simplify the description, the costs C of all objects a are set to 0. In addition, the unit time cost of an object b being OFF is lower than that of the object b being ON. The cost D is the difference calculated by subtracting the unit time cost during OFF from the unit time cost during ON and has a value of greater than 0. In the second embodiment, to simplify the description, the costs D of all objects b are set to 1.

The unit time cost of the entire system is the sum of the costs C of objects a that are yet to be triggered and the costs D of objects b that are yet to be triggered. The unit time cost at the start time is the sum of the costs C of all objects a and the costs D of all objects b. The unit time cost at the end time is 0. Both the triggering timing of each object b and a curve representing a temporal change in the unit time cost depend on the operation sequence for the group A. The information processing apparatus100determines an appropriate operation sequence for the group A that minimizes the system cost obtained by integrating the unit time cost over the period from the start time to the end time.

In this connection, the schedule optimization of the second embodiment is applicable to various optimization problems as exemplified as follows. In the case of a network equipment shutdown problem, the objects a are circuits, and the objects b are circuit switching devices. The unit time cost of each object b decreases from 1 to 0 in response to triggering. The triggering condition for the objects b is AND. The information processing apparatus100determines a sequence in which the circuits are to be shut down, such as to minimize the system cost.

In the case of a factory equipment shutdown problem, the objects a are manufacturing devices, and the objects b are products. The unit time profit of each object b decreases from 1 to 0 in response to triggering. The profit may be defined as a negative cost. The triggering condition for the objects b is OR. The information processing apparatus100determines a sequence in which the manufacturing devices are to be shut down, such as to maximize the system profit. In the case of a factory equipment re-startup problem, the objects a are manufacturing devices, and the objects b are products. The unit time profit of each object b increases from 0 to 1 in response to triggering. The triggering condition for the objects b is AND. The information processing apparatus100determines a sequence in which the manufacturing devices are to be started, such as to maximize the system profit.

FIG.4illustrates a first example of a temporal change in unit time cost.

A curve141corresponds to the above-described graph131and represents a change in the unit time cost of the entire system in the case where the triggering condition for the objects b is AND and the objects a are operated in the order of a1, a2, a3, a4, and a5.

At time 1, the object a1is triggered. The unit time cost does not change since the cost C1is 0 and no object b is triggered. At time 2, the object a2is triggered. The unit time cost does not change since the cost C2is 0 and no object b is triggered. At time 3, the object a3is triggered. At this point in time, the object b1is triggered. Since the cost D1is 1, the unit time cost decreases by 1.

Then, at time 4, the object a4is triggered. At this point in time, the objects b2and b3are triggered. Since the costs D2and D3are 1, the unit time cost decreases by 2. Lastly, at time 5, the object a5is triggered. At this point in time, the object b4is triggered. Since the cost D4is 1, the unit time cost decreases by 1. The area below the curve141represents the system cost. Note that the curve141is not a curve that minimizes the system cost.

FIG.5illustrates an example of a system that is a scheduling target.

As described above, a circuit-switched system is one example of an optimization target system. The graph131may be considered to represent the structure of the circuit-switched system. The circuit-switched system includes circuit switching devices21to27and circuits31to34. The circuits31to34are each a connection that connects two terminal devices via one or more circuit switching devices. The circuit switching devices21to27each transfer signals on one or more circuits.

The circuit31passes through the circuit switching devices21,25, and26. The circuit32passes through the circuit switching devices22to26. The circuit33passes through the circuit switching devices22,23, and27. The circuit34passes through the circuit switching devices25,26, and27. The circuits31to34correspond to objects a. The circuit switching devices21to27correspond to objects b. Each circuit switching device21to27incurs a unit time cost during operation. Each circuit switching device21to27is removable when there is no circuit that passes through it to transfer signals. The information processing apparatus100determines a sequence in which the circuits31to34are to be migrated to another system such that more circuit switching devices are removable early among the circuit switching devices21to27.

The following describes schedule search in the case where the triggering condition is AND.

The information processing apparatus100calculates T of Equation (1) for each object b that is yet to be triggered. Here, Abdenotes a set of objects a that are related to the object b, and RAdenotes a set of objects a that are already triggered. That is, T denotes the number of objects a that are yet to be triggered among the objects a related to the object b. In the case where a certain object b and another object b are triggered at the same time, T for the other object b is 0.

In addition, the information processing apparatus100calculates G of Equation (2) for each object b that is yet to be triggered. Here, Dbdenotes the cost of the object b, and Cadenotes the cost of an object a. Therefore, G is the sum of the cost Dbof the object b and the costs Caof the objects a that need to be operated. That is, G denotes a reduction in the unit time cost of the entire system, caused by operating all related objects a that are yet to be triggered.

Then, for each object b that is yet to be triggered, the information processing apparatus100calculates Zbof Equation (3) using the above T and G. BigZ is a sufficiently large positive constant. If T is 0, Zbis BigZ. If T is not 0, Zbis calculated by dividing G by T. That is, the higher G is, the higher Zb. The lower T is, the higher Zb.

The information processing apparatus100selects the object b with the maximum Zbas an object b to be triggered next. The information processing apparatus100then selects the object a that is related to the selected object b and is yet to be triggered, as an object a to be operated next. In the case where there are two or more related objects a that are yet to be triggered, these two or more objects a are operated in order.

FIG.6illustrates an example of visualizing an index Z.

The above-described Zbcorresponds to a downward slope (the value obtained by reversing the sign of the slope) on a two-dimensional plane where the horizontal axis represents time and the vertical axis represents the unit time cost of the system. The downward slope represents the average reduction in unit time cost per operation of an object a. To select the object b with the maximum Zbis equivalent to maximizing the average reduction.

For example, a point144represents the current time and the current unit time cost. A point145represents the triggering time of a certain object b to be triggered next and the unit time cost after the triggering. A point146represents the triggering time of an object b to be triggered next, different from the object b indicated by the point145, and the unit time cost after the triggering. A point147represents the triggering time of an object b to be triggered next, different from the objects b indicated by the points145and146, and the unit time cost after the triggering. Since triggering the objects b needs different numbers of objects a to be operated, the points145to147have different coordinates on the horizontal axis.

With respect to the object b indicated by the point145, the number of objects a to be operated is small, and the reduction in the unit time cost is also small. With respect to the object b indicated by the point146, the reduction in the unit time cost is large, but the number of objects a to be operated is large. With respect to the object b indicated by the point147, there is a good balance between the number of objects a to be operated and the reduction in the unit time cost, and the point147has the maximum downward slope from the point144. Therefore, the information processing apparatus100selects the object b indicated by the point147.

Each time selecting one object b to be triggered next, the information processing apparatus100recalculates Zbfor each remaining object b. At this time, the objects a that need to be operated to trigger the selected object b are regarded as being already triggered. The information processing apparatus100repeats a process of recalculating Zbfor each object b that is yet to be triggered and selecting the object b with the maximum Zbuntil all objects b are triggered.

In this connection, there may be two or more objects b with the maximum Zb. In this case, with respect to each of the two or more objects b, the information processing apparatus100continues to search for an operation sequence for the group A, tentatively selecting the object b. This means that the information processing apparatus100branches the search path for the operation sequence. In the case where the search path branches, the information processing apparatus100evaluates the created operation sequences in terms of the system cost in the middle of the search, and performs pruning by discarding search paths that are found to be less advantageous than other search paths.

As a result, one operation sequence finally remains for the group A. Note that the information processing apparatus100may prune search paths as needed so as not to create too many search path branches. For example, the information processing apparatus100may randomly discard a certain percentage of the search path branches or randomly discard a certain number of search path branches when the number of search path branches exceeds a threshold.

FIG.7illustrates a first example of schedule search.

A table151contains one or more records, each with OA, OB, and Q. In the case where the search path branches, the table151contains two or more records. OAis a permutation of objects a and indicates an operation sequence for the objects a. OBis a permutation of objects b and indicates a triggering sequence for the objects b. Q denotes the evaluation value of the operation sequence in the middle of search and is the cumulative unit time cost of the entire system from the start time to the current time. The lower Q is, the higher the evaluation of the operation sequence. A table152contains Zbcalculated for each object b belonging to the group B.

With respect to the above-described graph131, the information processing apparatus100initializes QAto empty, QBto empty, and Q to 0. The information processing apparatus100calculates Zbfor each of the objects b1to b4. Zbof the object b1is calculated as ⅓=0.333, Zbof the object b2is calculated as ½=0.500, Zbof the object b3is calculated as 1/1=1.000, and Zbof the object b4is calculated as ½=0.500.

The information processing apparatus100selects the object b3with the maximum Zb, and then selects the object a4that needs to be operated in order to trigger the object b3. The information processing apparatus100adds the object b3at the end of QB, and adds the object a4at the end of OA. In addition, the information processing apparatus100detects that the unit time cost from the start time to the triggering time of the object b3is 4, and adds this unit time cost to Q.

After that, the information processing apparatus100recalculates Zbfor each of the objects b1, b2, and b4. At this time, the objects a4and b3are regarded as being already triggered. Zbof the object b1is calculated as ⅓=0.333, Zbof the object b2is calculated as 1/1=1.000, and Zbof the object b4is calculated as ½=0.500.

The information processing apparatus100selects the object b2with the maximum Zb, and then selects the object a2that needs to be operated in order to trigger the object b2. The information processing apparatus100adds the object b2at the end of QB, and adds the object a2at the end of OA. In addition, the information processing apparatus100detects that the unit time cost from the triggering time of the object b3to the triggering time of the object b2is 3, and adds this unit time cost to Q.

After that, the information processing apparatus100recalculates Zbfor each of the objects b1and b4. At this time, the objects a2, a4, b2, and b3are regarded as being already triggered. Zbof the object b1is calculated as ½=0.500, and Zbof the object b4is calculated as 1/1=1.000.

The information processing apparatus100selects the object b4with the maximum Zb, and then selects the object a5that needs to be operated in order to trigger the object b4. The information processing apparatus100adds the object b4at the end of QB, and adds the object a5at the end of OA. In addition, the information processing apparatus100detects that the unit time cost from the triggering time of the object b2to the triggering time of the object b4is 2, and adds this unit time cost to Q.

Lastly, the information processing apparatus100selects the remaining object b1, and then selects the objects a1and a3that need to be operated in order to trigger the object b1. The information processing apparatus100adds the object b1at the end of QB, and adds the objects a1and a3at the end of OA. In this connection, two or more objects a, when added to OA, are arranged in descending order of their costs Ca. If there are objects a with the same cost Ca, they may be arranged in a random order.

In addition, the information processing apparatus100detects that the unit time costs in the temporal change from the triggering time of the object b4to the triggering time of the object b1are 1 and 1, and adds the sum of these unit time costs to Q. In the manner described above, the operation sequence for the group A is determined to be objects a4, a2, a5, a1, and a3. The final Q corresponds to the estimated value of the system cost. Note that in the case where the triggering condition is AND and two or more objects b are triggered at the same time in response to the triggering of a certain object a, Q may fail to represent a correct system cost.

FIG.8illustrates a second example of a temporal change in unit time cost.

A curve142corresponds to the graph131and represents a change in unit time cost in the case where the triggering condition for the objects b is AND and the objects a are operated in the order of a4, a2, a5, a1, and a3. At time 1, the object a4is triggered. At this point in time, the object b3is triggered, and the unit time cost decreases by 1. At time 2, the object a2is triggered. At this point in time, the object b2is triggered, and the unit time cost decreases by 1.

Then, at time 3, the object a5is triggered. At this point in time, the object b4is triggered, and the unit time cost decreases by 1. At time 4, the object a1is triggered. At this point in time, the unit time cost does not change. Then, at time 5, the object a3is triggered. At this point in time, the object b1is triggered, and the unit time cost decreases by 1. In the case of the curve141illustrated inFIG.4, the system cost is 16. On the other hand, in the case of the curve142illustrated inFIG.8, the system cost is 11, lower than that of the curve141.

The following describes schedule search in the case where the triggering condition is OR.

FIG.9illustrates a second example of a graph representing the relationships between objects.

The following describes schedule search under an OR condition with reference to the graph134. The graph134includes nodes135-1to135-3and136-1to136-13. The nodes135-1to135-3represent objects a1to a3belonging to a group A. The nodes136-1to136-13represent objects b1to b13belonging to a group B. Each of the objects a1to a3has a cost Caof 0, and each of the objects b1to b13has a cost Dbof 1. The objects b1to b6are related to the object a1. The objects b4to b10are related to the object a2. The objects beto b13are related to the object a3.

In the case where the triggering condition is AND, Zbis calculated for each object b. On the other hand, in the case where the triggering condition is OR, Zais calculated for each object a. The information processing apparatus100calculates Zaof Equation (4) for each object a that is yet to be triggered. Here, b′ denotes an object b that is yet to be triggered among the objects b related to the object a. Therefore, Zais the sum of the cost Caof the object a and the costs Dbof the objects b that are newly triggered in response to the triggering of the object a. That is, Zadenotes a reduction in the unit time cost of the entire system, caused by the triggering of the object a.

The information processing apparatus100selects the object a with the maximum Zaas an object a to be operated next. The information processing apparatus100then selects the object b that is related to the selected object a and is yet to be triggered as an object b to be triggered next. Note that, in the case where there are two or more related objects b that are yet to be triggered, the two or more objects b are actually triggered at the same time. Therefore, these objects b may be arranged in a random order in the permutation.

Each time selecting one object a to be operated next, the information processing apparatus100recalculates Zafor each remaining object a. At this time, the objects b related to the selected object a are regarded as being already triggered. The information processing apparatus100repeats a process of recalculating Zafor each object a that is yet to be triggered and selecting the object a with the maximum Zauntil all objects a are selected.

In this connection, there may be two or more objects a with the maximum Za. In this case, with respect to each of the two or more objects a, the information processing apparatus100continues to search for an operation sequence for the group A, tentatively selecting the object a. In the case where the information processing apparatus100branches the search path, the information processing apparatus100evaluates the created operation sequences in terms of the system cost in the middle of the search, and performs pruning by discarding search paths that are found to be less advantageous than other search paths, as in the case where the triggering condition is AND. Note that the information processing apparatus100may prune search paths as needed so as not to create too many search path branches.

FIG.10illustrates a second example of schedule search.

A table153contains one or more records, each with OA, OB, and Q. In the case where the search path branches, the table153contains two or more records. A table154contains Zacalculated for each object a belonging to the group A.

With respect to the above-described graph134, the information processing apparatus100initializes QAto empty, QBto empty, and Q to 0. The information processing apparatus100calculates Zafor each of the objects a1to a3included in the graph134. Zaof the object a1is calculated as 6, Zaof the object a2is calculated as 7, and Zaof the object b3is calculated as 6.

The information processing apparatus100selects the object a2with the maximum Za, and then selects the objects b4to b10that are triggered in response to the triggering of the object a2. The information processing apparatus100adds the object a2at the end of OA, and adds the objects b4to b10at the end of QB. Here, the objects b4to b10may be arranged in any order in QB. In addition, the information processing apparatus100detects that the unit time cost from the start time to the triggering time of the object a2is 13, and adds this unit time cost to Q.

After that, the information processing apparatus100recalculates Zafor each of the objects a1and a3. Zaof the object a1is calculated as 3, and Zaof the object a3is calculated as 3. Here, both the objects a1and a3have the maximum Za. Therefore, the information processing apparatus100creates two records based on the record of the table153.

The first record is about the case where the information processing apparatus100selects the object a1and also selects the objects b1to b3that are newly triggered in response to the triggering of the object a1. The information processing apparatus100adds the object a1at the end of OAand adds the objects b1to b3at the end of QB. Here, the objects b1to b3may be arranged in any order in QB. In addition, the information processing apparatus100detects that the unit time cost from the triggering time of the object a2to the triggering time of the object a1is 6, and adds this unit time cost to Q.

The second record is about the case where the information processing apparatus100selects the object a3and also selects the objects b11to b13that are newly triggered in response to the triggering of the object a3. The information processing apparatus100adds the object a3at the end of OAand adds the objects b11to b13at the end of QB. Here, the objects b11to b13may be arranged in any order in QB. In addition, the information processing apparatus100detects that the unit time cost from the triggering time of the object a2to the triggering time of the object a3is 6, and adds this unit time cost to Q.

At this point in time, the two permutations OAhave the same evaluation value Q, and there is no superiority or inferiority between the two permutations OA. The information processing apparatus100therefore continues the search using the two permutations OA.

For the first record, the information processing apparatus100selects the object a3and then selects the objects b11to b13that are newly triggered in response to the triggering of the object a3. The information processing apparatus100adds the object a3at the end of OAand adds the objects b11to b13at the end of QB. Here, the objects b11to b13may be arranged in any order in QB. In addition, the information processing apparatus100detects that the unit time cost from the triggering time of the object a1to the triggering time of the object as is 3, and adds this unit time cost to Q.

For the second record, the information processing apparatus100selects the object a1and then selects the objects b1to b3that are newly triggered in response to the triggering of the object a1. The information processing apparatus100adds the object a1at the end of OAand adds the objects b1to b3at the end of QB. Here, the objects b1to b3may be arranged in any order in QB. In addition, the information processing apparatus100detects that the unit time cost from the triggering time of the object a3to the triggering time of the object a1is 3, and adds this unit time cost to Q.

Even at the end time, the two permutations OAhave the same evaluation value Q, and there is no superiority or inferiority between the two permutations OA. Therefore, for example, the information processing apparatus100determines based on the first record that the operation sequence for the group A is a sequence of the objects a2, a1, and a3. The final Q corresponds to the system cost. Unlike the case where the triggering condition is AND, Q represents a correct system cost.

FIG.11illustrates a third example of a temporal change in unit time cost.

A curve143corresponds to the graph134and represents a change in unit time cost in the case where the triggering condition for the objects b is OR and the objects a are operated in the order of a2, a1, and a3. At time 1, the object a2is triggered. At this point in time, the objects b4to b10are triggered, and the unit time cost decreases by 7. At time 2, the object a1is triggered. At this point in time, the objects b1to b3are triggered, and the unit time cost decreases by 3. Then, at time 3, the object a3is triggered. At this point in time, the objects b11to b13are triggered, and the unit time cost decreases by 3. In the case of the curve143, the system cost is 22.

FIG.12illustrates examples of a system cost comparison.

A table155illustrates results of comparing the scheduling method under the AND condition described in the second embodiment with the heuristics taught in the aforementioned U.S. Patent Application Publication No. 2022/0094571. An optimization target system is a circuit-switched system including a plurality of circuits and a plurality of circuit switching devices.

A first comparison example relates to a system with 300 circuits and 25 circuit switching devices. With the heuristics taught in the aforementioned U.S. Patent Application Publication No. 2022/0094571, a schedule that provides a system cost of 6166 is created. With the scheduling method of the second embodiment, a schedule that provides a system cost of 5202 is created. A ratio of the latter system cost to the former system cost is approximately 84%, meaning that the second embodiment exhibits an improved optimization accuracy.

A second comparison example relates to a system with 595 circuits and 35 circuit switching devices. With the heuristics taught in the aforementioned U.S. Patent Application Publication No. 2022/0094571, a schedule that provides a system cost of 18245 is created. With the scheduling method of the second embodiment, a schedule that provides a system cost of 14284 is created. A ratio of the latter system cost to the former system cost is approximately 78%, meaning that the second embodiment exhibits an improved optimization accuracy.

The following describes the functions and processing procedures of the information processing apparatus100.

FIG.13illustrates an example of the functions of the information processing apparatus according to the second embodiment.

The information processing apparatus100includes a graph receiving unit121, a graph storage unit122, a search unit123, a schedule storage unit124, and a schedule sending unit125. The graph storage unit122and schedule storage unit124are implemented by using, for example, the RAM102or HDD103. The graph receiving unit121and schedule sending unit125are implemented by using, for example, the CPU101, communication interface107, and programs. The search unit123is implemented by using, for example, the CPU101and programs.

The graph receiving unit121receives graph data representing a bipartite graph such as the graph131or134. The graph data includes a plurality of nodes representing objects and a plurality of edges connecting the plurality of nodes. In addition, the graph data includes costs that are respectively assigned to the nodes. In addition, the graph data includes a flag indicating whether the triggering condition is AND or OR. For example, the graph data is generated by the user so as to represent an optimization target system. The graph receiving unit121may accept the graph data from the user or may receive the graph data from another information processing apparatus. The graph receiving unit121may provide a user interface to assist the user in generating the graph data.

The graph storage unit122stores the graph data received by the graph receiving unit121. The search unit123executes a scheduling algorithm under AND relationship or a scheduling algorithm under OR relationship, which will be described later, depending on the flag included in the graph data. The search unit123generates schedule data and stores it in the schedule storage unit124. The schedule data represents an operation sequence for the objects belonging to the group A indicated in the graph data, and a system cost that is the cumulative unit time cost from the start time to the end time.

The schedule storage unit124stores the schedule data generated by the search unit123. The schedule sending unit125outputs the generated schedule data. The schedule sending unit125may display the schedule data on the display device111or may send the schedule data to another information processing apparatus.

FIG.14is a flowchart illustrating an example of a procedure for scheduling under AND relationship.

S10: The search unit123sets aside two storage regions: “stack 1” and “stack 2.” The search unit123creates a record (OA={ }, OB={ }, Q=0) for the initial state and stores the record in the stack 1. This initializes the stacks 1 and 2.

S11: The search unit123selects an object b to be triggered next from the group B. At this time, two or more candidates may be selected. A record indicating the result of selecting the object b is stored in the stack 2. A procedure for the object selection will be described later.

S12: The search unit123organizes the records stored in the stack 2 and moves records that need to be kept to the stack 1. At this time, the search unit123may delete records that each indicate a permutation of objects b that is less advantageous than other records, or may randomly delete some records for adjusting the number of records. A procedure for the stack organization will be described later.

S13: The search unit123determines whether the length of the permutation representing the triggering sequence for the objects b is equal to the size of the group B (the number of objects b included in the group B). If the length of the permutation is equal to the size of the group B, the process proceeds to step S14. If the length of the permutation is less than the size of the group B, the process proceeds back to step S11.

S14: At this point in time, only one record is stored in the stack 1. The search unit123calculates a system cost based on the operation sequence for the objects a indicated in the stored record. A procedure for the system cost calculation will be described later.

FIG.15is a flowchart illustrating an example of a procedure for object selection under AND relationship.

The object selection under AND relationship is performed at above-described step S11.

S20: The search unit123determines whether the stack 1 is empty. If the stack 1 is empty, the object selection is completed. If the stack 1 is not empty, the process proceeds to step S21.

S21: The search unit123extracts one record from the stack 1 and then extracts OA, OB, and Q from the record. The search unit123sets now RAequal to the set of elements included in the extracted OA, now OAequal to the extracted OA, now OBequal to the extracted OB, and now Q equal to the extracted Q.

S22: The search unit123calculates, for each object b that is yet to be triggered, T of Equation (1) and G of Equation (2), and then calculates Zbof Equation (3) using the calculated T and G.

S23: The search unit123specifies the maximum value maxZ among the values Zbof the objects b that are yet to be triggered, calculated at step S22.

S24: The search unit123selects one object b that is yet to be triggered. The search unit123determines whether Zbof the selected object b is maxZ specified at step S23. If Zbis maxZ, the process proceeds to step S25. If Zbis lower than maxZ, the process proceeds to step S29.

S25: The search unit123calculates a set nextA of objects a that need to be triggered additionally in order to trigger the object b, with Equation (5).

S26: The search unit123sorts the elements of nextA in descending order of their costs Ca.

S27: The search unit123adds the elements of nextA to nowRA, and calculates nextRA. In addition, the search unit123adds a string of elements sorted at step S26at the end of nowOA, and calculates nextOA. In addition, the search unit123adds the selected object b at the end of nowOB, and calculates nextOB.

In addition, the search unit123calculates nextQ with Equation (6). In Equation (6), najdenotes the j-th element of the element string sorted at step S26, and C(naj) denotes the cost of the object naj. The second term of the right side is the sum of the costs of the objects a that are yet to be triggered. The third term of the right side is the stepwise sum of the unit time costs of the objects a that are triggered this time. The fourth term of the right side is the sum of the costs of the objects b that are yet to be triggered.

S28: The search unit123creates a record (nextOA, nextOB, nextQ) and stores the created record in the stack 2.

S29: The search unit123determines whether all objects b that are yet to be triggered have been selected at step S24. If all the objects b have been selected, the process proceeds back to step S20. Otherwise, the process proceeds back to step S24.

FIG.16is a flowchart illustrating an example of a procedure for stack organization.

The stack organization is performed at above-described step S12.

S30: The search unit123determines whether the stack 2 is empty. If the stack 2 is empty, the stack organization is completed. If the stack 2 is not empty, the process proceeds to step S31.

S31: The search unit123extracts one record from the stack 2 and then extracts OA, OB, and Q from the record. The search unit123sets curOAequal to the extracted OA, curOBequal to the extracted OB, and curQ equal to the extracted Q.

S32: The search unit123determines whether a record with OAincluding all elements included in curOAexists in the stack 1. If such a record exists in the stack 1, the process proceeds to step S33. Otherwise, the process proceeds to step S36.

S33: The search unit123determines whether Q of the record found at step S32is lower than curQ. If Q is lower than curQ, the process proceeds back to step S30. If Q is higher than or equal to curQ, the process proceeds to step S34.

S34: The search unit123determines whether Q of the record found at step S32is higher than curQ. If Q is higher than curQ, the process proceeds to step S35. If Q is equal to curQ, the process proceeds to step S36.

S35: The search unit123deletes the record found at step S32from the stack 1.

S36: The search unit123creates a record (curOA, curOB, curQ) and stores the created record in the stack 1. Then, the process proceeds back to step S30.

FIG.17is a flowchart illustrating an example of a procedure for system cost calculation.

S40: The search unit123initializes S to 0, and L to an empty set. In addition, the search unit123initializes U as in Equation (7). Here, the initialization value of U is the sum of the costs Caof all objects a and the costs Dbof all objects b.

S41: The search unit123extracts a record from the stack 1 and extracts OAfrom the record. At the start of the system cost calculation, only one record exists in the stack 1.

S42: The search unit123adds U to S.

S43: The search unit123extracts one object a from the beginning of OA, and subtracts the cost Caof the extracted object a from U.

S44: The search unit123searches for an object b that is triggered in response to the triggering of the object a extracted at step S43. If such an object b to be triggered is found, the search unit123subtracts the cost Dbof the object b to be triggered from U.

S45: The search unit123adds the extracted object a at the end of L.

S46: The search unit123determines whether all objects a have been extracted from OA. If all the objects a have been extracted, the process proceeds to step S47. Otherwise, the process proceeds back to step S42.

S47: The search unit123generates schedule data indicating the permutation L representing the operation sequence for the objects a, and the system cost S, and outputs the schedule data.

FIG.18is a flowchart illustrating an example of a procedure for scheduling under OR relationship.

S50: The search unit123sets aside two storage regions: “stack 1” and “stack 2.” The search unit123creates a record (OA={ }, OB={ }, Q=0) for the initial state and stores the record in the stack 1. This initializes the stacks 1 and 2.

S51: The search unit123selects an object a to be triggered next from the group A. At this time, two or more candidates may be selected. A record indicating the result of selecting the object a is stored in the stack 2. A procedure for the object selection will be described later.

S52: The search unit123organizes the records stored in the stack 2 and moves records that need to be kept to the stack 1. At this time, the search unit123may delete records that each indicate a permutation of objects a that is less advantageous than other records, or may randomly delete some records for adjusting the number of records. A procedure for the stack organization is the same as described inFIG.16.

S53: The search unit123determines whether the length of the permutation representing the triggering sequence for the objects a is equal to the size of the group A (the number of objects a included in the group A). If the length of the permutation is equal to the size of the group A, the process proceeds to step S54. If the length of the permutation is less than the size of the group A, the process proceeds back to step S51.

S54: At this point in time, only one record is stored in the stack 1. The search unit123calculates a system cost based on the operation sequence for the objects a indicated in the stored record. A procedure for the system cost calculation is the same as described inFIG.17. Note that the search unit123may use Q included in the record as the system cost S.

FIG.19is a flowchart illustrating an example of a procedure for object selection under OR relationship.

The object selection under OR relationship is executed at above-described step S51.

S60: The search unit123determines whether the stack 1 is empty. If the stack 1 is empty, the object selection is completed. If the stack 1 is not empty, the process proceeds to step S61.

S61: The search unit123extracts one record from the stack 1 and then extracts OA, OB, and Q from the record. The search unit123sets nowRAequal to the set of elements included in the extracted OA, nowOAequal to the extracted OA, nowOBequal to the extracted OB, and nowQ equal to the extracted Q.

S62: The search unit123calculates Zaof Equation (4) for each object a that is yet to be triggered.

S63: The search unit123specifies the maximum value maxZ among the values Zaof the objects a that are yet to be triggered, calculated at step S62.

S64: The search unit123selects one object a that is yet to be triggered. The search unit123determines whether Zaof the selected object a is maxZ specified at step S63. If Zais maxZ, the process proceeds to step S65. If Zais lower than maxZ, the process proceeds to step S68.

S65: The search unit123calculates a set nextB of objects b that are newly triggered in response to the triggering of the selected object a. The set nextB is such a set of objects b that are not included in nowOBand that Abincludes the above object a.

S66: The search unit123adds the selected object a at the end of nowOAand calculates nextOA. In addition, the search unit123adds nextB at the end of nowOBand calculates nextOB. Here, the objects b may be arranged in any order.

In addition, the search unit123calculates nextQ with Equation (8). In Equation (8), the second term of the right side is the sum of the costs of the objects a that are yet to be triggered at the point in time before the object a selected at step S64is triggered. The third term of the right side is the sum of the costs of the objects b that are yet to be triggered at the point in time before the object a selected at step S64is triggered.

S67: The search unit123creates a record (nextOA, nextOB, nextQ) and stores the created record in the stack 2.

S68: The search unit123determines whether all objects a that are yet to be triggered have been selected at step S64. If all the objects a have been selected, the process proceeds back to step S60. Otherwise, the process proceeds to step S64.

As described above, the information processing apparatus100of the second embodiment generates schedule data representing an operation sequence for the objects a of the group A on the basis of the graph data obtained by modeling a system. At this time, the information processing apparatus100searches for the operation sequence that achieves a reduced system cost in the transition period during which all objects b of the group B undergo a state change. This results in generating highly efficient, useful schedule data.

The information processing apparatus100is able to apply the algorithm described in the second embodiment to network equipment shutdown problems, factory equipment shutdown problems, factory equipment re-startup problems, and other various optimization problems. In addition, the information processing apparatus100searches for an operation sequence for the objects a using an algorithm that differs between the case where a condition to cause the state change in the objects b is AND and the case where the condition is OR. This allows for the generation of appropriate schedule data that meets the system requirement.

In the case of the AND condition, the information processing apparatus100calculates the index value Zbfor each object b, and determines the operation sequence for the objects a such that the object b with the maximum Zbundergoes the state change next. The index value Zbis inversely proportional to the number of objects a that need to be operated in order to cause the state change in the object b, and is proportional to the reduction in the unit time cost caused by the operation. Thus, the efficiency of the operation is evaluated, and the optimization accuracy is improved.

In the case of the OR condition, the information processing apparatus100calculates the index value Zafor each object a, and determines the operation sequence such that the object a with the maximum Zais operated next. The index value Zadenotes the reduction in the unit time cost caused by operating the object a. Thus, the efficiency of the operation is evaluated, and the optimization accuracy is improved.

In addition, in the case where there are two or more objects with the maximum index value, the information processing apparatus100searches for a subsequent operation sequence for each of the two or more objects, and narrows down the operation sequence candidates on the basis of the superiority or inferiority of the subsequent operation sequences. This reduces the risk of failing to detect a preferable operation sequence that is more advantageous than other operation sequences in the late stage of the search. In addition, if there are many candidate branches, the information processing apparatus100randomly discards candidates. This ensures that schedule data is generated within a realistic computation time and with a computational load.

In one aspect, a highly efficient schedule is created.