{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:41:11Z","timestamp":1760244071603,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2009,11,26]],"date-time":"2009-11-26T00:00:00Z","timestamp":1259193600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Non-preemptive schedulers, despite their many discussed drawbacks, remain a very popular choice for practitioners of real-time and embedded systems. The non-preemptive \u2018thrift\u2019 cyclic scheduler\u2014variations of which can be found in other application areas\u2014has recently received considerable attention for the implementation of such embedded systems. A thrift scheduler provides a flexible and compact implementation model for periodic task sets with comparatively small overheads; additionally, it can overcome several of the problems associated with traditional \u2018cyclic executives\u2019. However, severe computational difficulties can still arise when designing schedules for non-trivial task sets. This paper is concerned with an optimization version of the offset-assignment problem, in which the objective is to assign task offsets such that the required CPU clock speed is minimized whilst ensuring that task overruns do not occur; it is known that the decision version of this problem is complete for \u03a32p. The paper first considers the problemof candidate solution verification\u2014itself strongly coNP-Complete\u2014and a fast, exact algorithm for this problem is proposed; it is shown that for any fixed number of tasks, its execution time is polynomial. The paper then proposes two heuristic algorithms of pseudopolynomial complexity for solving the offset-assignment problem, and considers how redundant choices of offset combinations can be eliminated to help speed up the search. The performance of these algorithms is then experimentally evaluated, before conclusions are drawn.<\/jats:p>","DOI":"10.3390\/a2041449","type":"journal-article","created":{"date-parts":[[2009,11,28]],"date-time":"2009-11-28T06:03:28Z","timestamp":1259388208000},"page":"1449-1472","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exact and Heuristic Algorithms for Thrift Cyclic Scheduling"],"prefix":"10.3390","volume":"2","author":[{"given":"Michael  J.","family":"Short","sequence":"first","affiliation":[{"name":"Embedded Systems Laboratory, University of Leicester, Leicester, UK"}]}],"member":"1968","published-online":{"date-parts":[[2009,11,26]]},"reference":[{"key":"ref_1","unstructured":"Buttazo, G. (2005). Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Springer Verlag."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF02341919","article-title":"The cyclic executive model and Ada","volume":"1","author":"Baker","year":"1989","journal-title":"Real-Time Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF00365463","article-title":"Software architecture for hard real-time applications: Cyclic executives vs. fixed priority executives","volume":"4","author":"Locke","year":"1992","journal-title":"Real-Time Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1008198310125","article-title":"Fixed priority scheduling versus pre-run-time scheduling","volume":"18","author":"Xu","year":"2000","journal-title":"Real-Time Syst."},{"key":"ref_5","unstructured":"Bate, I.J. (1998). Scheduling and Timing Analysis for Safety Critical Real-Time Systems. [PhD. Dissertation, Department of Computer Science, University of York]."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Short, M., Pont, M.J., and Fang, J. (2008, January July). Exploring the impact of pre-emption on dependability in time-triggered embedded systems: A pilot study. Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS 2008), Prague, Czech Republic.","DOI":"10.1109\/ECRTS.2008.14"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1293","DOI":"10.1016\/j.conengprac.2008.03.007","article-title":"Assessment of performance and dependability in embedded control systems: methodology and case study","volume":"16","author":"Short","year":"2008","journal-title":"Contr. Eng. Pract."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0967-0661(94)00072-O","article-title":"Generating feasible cyclic schedules","volume":"3","author":"Burns","year":"1995","journal-title":"Contr. Eng. Pract."},{"key":"ref_9","unstructured":"Pont, M.J. (2001). Patterns For Time Triggered Embedded Systems, ACM Press(Addison Wesley)."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1109\/TII.2008.916053","article-title":"Automatically configuring time-triggered schedulers for use with resource-constrained, single-processor embedded systems","volume":"4","author":"Gendy","year":"2008","journal-title":"IEEE Trans. Ind. Inf."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01995675","article-title":"Algorithms and complexity concerning the preemptive scheduling of periodic tasks on one processor","volume":"2","author":"Baruah","year":"1990","journal-title":"Real-Time Syst."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1023\/A:1021782503695","article-title":"Scheduling of offset free systems","volume":"24","author":"Goossens","year":"2003","journal-title":"Real-Time Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0207001","article-title":"An application of Bin-Packing to multiprocessor scheduling","volume":"7","author":"Coffman","year":"1978","journal-title":"SIAM J. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1109\/32.392979","article-title":"Guaranteeing real-time requirements with resource-based calibration of periodic processes","volume":"21","author":"Gerber","year":"1995","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/s100090100054","article-title":"Worst-case execution-time analysis for embedded real-time systems","volume":"4","author":"Engblom","year":"2001","journal-title":"J. Softw. Tools Technol. Transf."},{"key":"ref_16","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A guide to the Theory of NP-Completeness, W.H. Freeman."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","article-title":"Bounds on multiprocessing timing anomalies","volume":"17","author":"Graham","year":"1969","journal-title":"SIAM J. Appl. Math."},{"key":"ref_18","unstructured":"Knuth, D.E. (1973). The Art of Computer Programming, Addison-Wesley. [2nd ed.]. Vol. 2."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1016\/0165-6074(89)90128-2","article-title":"Algorithms and complexity of the periodic maintenance problem","volume":"27","author":"Mok","year":"1989","journal-title":"Microprocess. Microprogram."},{"key":"ref_20","unstructured":"Short, M. (, January July). Some complexity results concerning the non-preemptive \u2018thrift\u2019 cyclic scheduler. Proceedings of the 6th International Conference on Informatics in Control, Robotics and Automation (ICINCO 2009), Milan, Italy."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/j.ejor.2009.03.011","article-title":"A note on the efficient scheduling of periodic information monitoring requests","volume":"201","author":"Short","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1016\/j.ejor.2003.09.036","article-title":"Vehicle minimization for periodic deliveries","volume":"165","author":"Campbell","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1016\/j.ejor.2005.01.057","article-title":"Efficient scheduling of periodic information monitoring requests","volume":"173","author":"Zeng","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_24","unstructured":"Leiserson, C., Prokop, H., and Randall, K.H. Available online: http:\/\/supertech.csail.mit.edu\/papers\/debruijn.pdf."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Niedermeier, D. (2006). Invitation to fixed-parameter algorithms, Oxford University.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/4\/1449\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:11:47Z","timestamp":1760220707000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/4\/1449"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11,26]]},"references-count":25,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2009,12]]}},"alternative-id":["a2041449"],"URL":"https:\/\/doi.org\/10.3390\/a2041449","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2009,11,26]]}}}