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.