OPERATION-PLAN SCHEDULING DEVICE AND ITS METHOD

摘要

A new operation is added to an operation plan while reducing the change amount in switch costs before and after change. An operation-plan scheduling device according to one embodiment is provided with a reader to read an operation plan, switch-cost information, information of an additional operation; a graph-network creator to create a graph network by setting intervals between operations allocated to the operation executors as an interval vertices, connecting edges among an entry vertex, an interval vertex, and an exit vertex, and setting weight variables on the edges; a path selector to select a path based on edge weight sums of the paths from the entry vertex to the exit vertex of the graph network; and an operation-plan creator to exchange operations between the operation executors in accordance with the selected path and allocate the additional operation to the interval created by the exchange.

主权项

1. An operation-plan scheduling device comprising a computer including a processor, comprising:
a reader implemented by the computer to read an operation plan allocating plural operations to plural operation executors, information of switch costs depending on the operations before and after switching is made in a case in which the operation executor switches the operations, and information of an additional operation having start time and one of process time and end time; a graph-network creator implemented by the computer to create a graph network,
setting interval vertices corresponding intervals of time between the operations allocated to the operation executors ,connecting an edge from the interval vertex corresponding to the one of the intervals to the interval vertex corresponding to the other interval when between the operation executors, the intervals intersect with each other and end time of the one of the intervals is earlier than end time of the other interval,connecting an edge from an entry vertex to the interval vertex corresponding to the interval, when the start time of the additional operation is included in the interval, connecting an edge from the interval including the end time of the additional operation or from the interval vertex corresponding to the interval thereafter to an exit vertex,setting an edge weight on the edge, the edge weight based on the switch costs between the operations before and after the interval in the tail of the edge, between the operations before and after the interval in the head of the edge, and between the operation before the interval in the head and the operation after the interval in the tail,setting an edge weight on the edge connected from the entry vertex to the interval vertex, the edge weight based on the switch costs between the operations before and after the interval corresponding to the interval vertex and between the operation before the interval and the additional operation, andsetting an edge weight on the edge connected from the interval vertex to the exit vertex, the edge weight based on the switch costs between the operations before and after the interval corresponding .to the interval vertex and between the additional operation and the operation after the interval; a path selector implemented by the computer to select a path from plural paths from the entry vertex to the exit vertex in the graph network, based on an edge-weight sum of each path; and an operation-plan creator implemented by the computer to generate an interval having a length equal to or more than the process time of the additional operation for the operation executor belonging to the interval corresponding to the interval vertex next to the entry vertex and allocate the additional operation to the generated interval to update the operation plan wherein the operation-plan creator generates the interval by tracking the interval vertices after the next interval vertex of the entry vertex in the selected path and repeating to replace all the following operations after the interval corresponding to the next interval vertex with all the following operations after the interval corresponding to the tracked interval vertex each time the following interval vertex is tracked.