Multi-apprentice learning for meta-heuristics parameter tuning in a multi agent scheduling system

The scheduling problem is considered in complexity theory as a NP-hard combinatorial optimization problem. Meta-heuristics proved to be very useful in the resolution of this class of problems. However, these techniques require parameter tuning which is a very hard task to perform. A Case-based Reasoning module is proposed in order to solve the parameter tuning problem in a Multi-Agent Scheduling System. A computational study is performed in order to evaluate the proposed CBR module performance.

Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors—such a platform is referred to as two-type platform. We present two low degree polynomial time-complexity algorithms, SA and SA-P, each providing the following guarantee. For a given two-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then (i) using SA, it is guaranteed to find such an assignment where the same restriction on task migration applies but given a platform in which processors are 1+α/2 times faster and (ii) SA-P succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which processors are 1+α times faster. The parameter 0<α≤1 is a property of the task set; it is the maximum of all the task utilizations that are no greater than 1. We evaluate average-case performance of both the algorithms by generating task sets randomly and measuring how much faster processors the algorithms need (which is upper bounded by 1+α/2 for SA and 1+α for SA-P) in order to output a feasible task assignment (intra-migrative for SA and non-migrative for SA-P). In our evaluations, for the vast majority of task sets, these algorithms require significantly smaller processor speedup than indicated by their theoretical bounds. Finally, we consider a special case where no task utilization in the given task set can exceed one and for this case, we (re-)prove the performance guarantees of SA and SA-P. We show, for both of the algorithms, that changing the adversary from intra-migrative to a more powerful one, namely fully-migrative, in which tasks can migrate between processors of any type, does not deteriorate the performance guarantees. For this special case, we compare the average-case performance of SA-P and a state-of-the-art algorithm by generating task sets randomly. In our evaluations, SA-P outperforms the state-of-the-art by requiring much smaller processor speedup and by running orders of magnitude faster.

Symmetry and order parameter dynamics of the human odometer

Bipedal gaits have been classified on the basis of the group symmetry of the minimal network of identical differential equations (alias cells) required to model them. Primary bipedal gaits (e.g., walk, run) are characterized by dihedral symmetry, whereas secondary bipedal gaits (e.g., gallop-walk, gallop- run) are characterized by a lower, cyclic symmetry. This fact has been used in tests of human odometry (e.g., Turvey et al. in P Roy Soc Lond B Biol 276:4309–4314, 2009, J Exp Psychol Hum Percept Perform 38:1014–1025, 2012). Results suggest that when distance is measured and reported by gaits from the same symmetry class, primary and secondary gaits are comparable. Switching symmetry classes at report compresses (primary to secondary) or inflates (secondary to primary) measured distance, with the compression and inflation equal in magnitude. The present research (a) extends these findings from overground locomotion to treadmill locomotion and (b) assesses a dynamics of sequentially coupled measure and report phases, with relative velocity as an order parameter, or equilibrium state, and difference in symmetry class as an imperfection parameter, or detuning, of those dynamics. The results suggest that the symmetries and dynamics of distance measurement by the human odometer are the same whether the odometer is in motion relative to a stationary ground or stationary relative to a moving ground.