scientific article; zbMATH DE number 3843474
A time scheduling problem is studied involving n operations and m machines. Each operation can be performed on any machine. Sequential relations among operations are described by an oriented graph G with number of nodes equal to the number of operations (an arc from a node u to a node v means that operation v could be started only after operation u is finished). It is supposed that processing time for each operation on any machine is equal to 1. In general the problem of finding an optimal schedule (minimizing total processing time) is NP-complete. The author gives simple formulas for evaluating lower bounds of the length (total processing time) of feasible schedules under various assumptions on the graph G.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3313595)