## 1 Introduction
To overcome this limitation, the non-preemptive 'thrift' scheduler (or 'TTC' scheduler) has been proposed [9]. This scheduling algorithm does not allow the use of inserted idle-time, and essentially maintains a system of congruences to replace the lookup table, and is presented in pseudo code in Figure 1. As can be seen, when tasks are released by the scheduler, they are immediately dispatched on a first-come, first-served basis (FCFS). In general, generating a feasible schedule for a thrift scheduler reduces to assigning offsets (delays) to each task [9, 10], resulting in an asynchronous schedule. However, previous investigations into the complexity of deciding the feasibility of asynchronous schedules have shown it to be a strongly coNP-Complete problem, at least in the case of the preemptive schedulers [11]. Moreover, as [PERSON] [12] has commented, when attempting to assign offsets to preemptively schedule a task set, that there seems to be no way to avoid enumerating and searching an exponential amount of offset combinations; in fact the decision version of this particular problem is known to be complete for \(\Sigma_{2}{}^{p}\), even when preemption is allowed [11]. Unsurprisingly, similar results have been demonstrated for the non-preemptive thrift cyclic scheduler, in which certain task parameters are allowed to be either integer or fractional [20, 21]. The thrift scheduling algorithm has also been suggested for use in domains other than that of embedded systems, for example the processing of information requests in mission critical security applications [22], and the underlying model has also proved to be identical (in most aspects) to scheduling problems described in other application areas, for example the periodic vehicle delivery problem [23]. The underlying concept in these formulations is that there exists a periodic (indefinitely repeating) system of actions to be performed (tasks to execute, information to be serviced, items to deliver) in which the temporal separation of actions must _exactly_ correspond to the actions' periodicity requirements; the optimization goal is to assign individual start times ('offsets') to each action, such that the number of actions to be simultaneously performed over the system lifetime is minimized. The application of heuristics for this assignment of offsets in such problems--for example using greedy approaches such as the 'First-Fit Decreasing' (FFD) algorithm--is an attractive option; a severe drawback of recent works has been the limitation that in each step of the FFD procedure, it is required to evaluate the quality of a partial candidate solution; which is itself strongly coNP-Hard [20]. In most cases, previous studies have severely limited the choice of task periods to attempt to circumvent this problem. For example, in [10] [PERSON] & [PERSON] describe a heuristic optimization  
Figure 1: Thrift scheduling algorithm, in pseudo-code. procedure to generate feasible thrift schedules. Although the technique works reasonably well in practice, it is required to limit the ratio of minimum to maximum periods in the task set to 1:10. A similar restriction on periods is enforced by [PERSON] [11], who investigates heuristic methods for preemptive schedules. In other domains, similar restrictions are placed on the various parameters in question [22, 23]. For many applications, this restriction is clearly unrealistic. Although it has been argued that in many cases, a task set with either coprime or non-harmonic periods is not representative of real-world applications (e.g., [10, 14])--this is true only for closely related transactions, such as filtering and updating a single control loop. In reality, for economic, topological and efficiency reasons, a single processor may well be performing multiple--not physically related--functions. As such, the periods are dictated by many factors and there is likely to be little, if any, harmonic coupling between transactions [5, 8].