Constructions of permutation arrays for certain scheduling cost measures
Joseph Seffi Naor, Ron M. Roth · Random Structures and Algorithms · 1995
Abstract Constructions of permutation arrays are presented that are optimal or nearly‐optimal with respect to two cost measures: the so‐called longest‐jump measure and the longest‐monotone‐greedy‐subsequence measure. These measures arise in the context of scheduling problems in asynchronous, shared memory, multiprocessor machines.