Max-plus algebra and incremental scheduling problems in manufacturing systems

An approach is presented to deal with scheduling problems where a large set of assignment/sequencing decisions is considered to be fixed, but a considerable number of such decisions is still to be taken. It is assumed that a nominal `semi-schedule´ is available, consisting in the task sequences to be executed by the various machines. Then, a set of allowed perturbations is taken into account, consisting in binary alternatives concerning the assignment and the sequencing of the tasks. The use of computational tools coming from max-plus algebra provides an effective way to write the performance indexes in terms of the decision variables representing the binary alternatives