Scheduling under the network of temporo-spatial proximity relationships

In this paper, we discuss and introduce to the scheduling field a novel optimization objective - half perimeter proximity measure in scheduling under the network of temporo-spatial proximity relationships. The presented approach enables to qualitatively express various reasons of scheduling certain jobs in close proximity, without resorting to quantitative, precisely defined consequences of such scheduling. Based on the correspondence between scheduling and rectangle packing problems in VLSI, we present an incremental Sequence Pair neighborhood evaluation algorithm, as an essential tool for complex solution-search methods for both proximity scheduling and physical layout synthesis of integrated circuits. A numerical experiment showed that such an incremental approach is considerably faster than the naive approach, performing evaluation of a solution from scratch each time, at the cost of small approximation error.