6533b822fe1ef96bd127d96a

RESEARCH PRODUCT

Scheduling under the network of temporo-spatial proximity relationships

subject

description

We discuss and introduce to the schedulingeld a novel, qualitative optimization model - scheduling under the network of temporo-spatial proximity relationships.We introduce a half perimeter proximity measure as an objective of scheduling.We present and evaluate an incremental Sequence Pair neighborhood evaluation algorithm, applicable to both scheduling and rectangle packing problems in VLSI industry. 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.