IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v39y1992i2p247-264.html
   My bibliography  Save this article

Real‐time task scheduling with overheads considered

Author

Listed:
  • Christian L. Cesar
  • Peter G. Jessel

Abstract

n periodic tasks are to be processed by a single machine, where each task i has a maximum request rate or periodicity Fi, a processing time Ei, a deadline Di, relative to each request of task i, a task‐request interrupt overhead Ii, and a task‐independent scheduling overhead S. Two scheduling strategies are considered for sequencing the execution of an arbitrary arrangement of task requests in time: the preemptive and the nonpreemptive earliest‐deadline algorithms. Necessary and sufficient conditions are derived for establishing whether a given set of tasks can be scheduled by each scheduling strategy. The conditions are given in the form of limited simulations of a small number of well‐defined task‐request arrangements. If all simulations succeed, the schedule is feasible for the given set of tasks. If any simulation fails, the schedule is infeasible. While interrupt handling and scheduling overheads can be handled by such simulations, context switching overhead resulting from preemption cannot. A counterexample illustrates how the simulations fail to uncover unschedulable task sets when context switching overhead is considered.

Suggested Citation

  • Christian L. Cesar & Peter G. Jessel, 1992. "Real‐time task scheduling with overheads considered," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 247-264, March.
    • Handle: RePEc:wly:navres:v:39:y:1992:i:2:p:247-264
    DOI: 10.1002/1520-6750(199203)39:23.0.CO;2-S
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199203)39:23.0.CO;2-S
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199203)39:23.0.CO;2-S?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. E. L. Lawler, 1973. "Optimal Sequencing of a Single Machine Subject to Precedence Constraints," Management Science, INFORMS, vol. 19(5), pages 544-546, January.
    2. W. A. Horn, 1974. "Some simple scheduling algorithms," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 21(1), pages 177-185, March.
    3. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    4. Albert Schild & Irwin J. Fredman, 1961. "On Scheduling Tasks with Associated Linear Loss Functions," Management Science, INFORMS, vol. 7(3), pages 280-285, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bachtenkirch, David & Bock, Stefan, 2022. "Finding efficient make-to-order production and batch delivery schedules," European Journal of Operational Research, Elsevier, vol. 297(1), pages 133-152.
    2. Rubing Chen & Jinjiang Yuan, 2020. "Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices," 4OR, Springer, vol. 18(2), pages 177-196, June.
    3. Briskorn, Dirk & Davari, Morteza & Matuschke, Jannik, 2021. "Single-machine scheduling with an external resource," European Journal of Operational Research, Elsevier, vol. 293(2), pages 457-468.
    4. Johnny C. Ho & Yih‐Long Chang, 1991. "Heuristics for minimizing mean tardiness for m parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(3), pages 367-381, June.
    5. Hongmin Li & Woonghee T. Huh & Matheus C. Sampaio & Naiping Keng, 2021. "Planning Production and Equipment Qualification under High Process Flexibility," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3369-3390, October.
    6. Shabtay, Dvir & Gilenson, Miri, 2023. "A state-of-the-art survey on multi-scenario scheduling," European Journal of Operational Research, Elsevier, vol. 310(1), pages 3-23.
    7. Stanisław Gawiejnowicz, 2020. "A review of four decades of time-dependent scheduling: main results, new topics, and open problems," Journal of Scheduling, Springer, vol. 23(1), pages 3-47, February.
    8. Rubing Chen & Jinjiang Yuan & C.T. Ng & T.C.E. Cheng, 2019. "Single‐machine scheduling with deadlines to minimize the total weighted late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 582-595, October.
    9. Enrique Gerstl & Gur Mosheiov, 2020. "Single machine scheduling to maximize the number of on-time jobs with generalized due-dates," Journal of Scheduling, Springer, vol. 23(3), pages 289-299, June.
    10. T.C.E. Cheng & Svetlana A. Kravchenko & Bertrand M.T. Lin, 2017. "Preemptive parallel‐machine scheduling with a common server to minimize makespan," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(5), pages 388-398, August.
    11. Marieke Quant & Marc Meertens & Hans Reijnierse, 2008. "Processing games with shared interest," Annals of Operations Research, Springer, vol. 158(1), pages 219-228, February.
    12. José R. Correa & Maurice Queyranne, 2012. "Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(5), pages 384-395, August.
    13. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    14. Qiuping Yu & Gad Allon & Achal Bassamboo & Seyed Iravani, 2018. "Managing Customer Expectations and Priorities in Service Systems," Management Science, INFORMS, vol. 64(8), pages 3942-3970, August.
    15. Vink, Wouter & Kuiper, Alex & Kemper, Benjamin & Bhulai, Sandjai, 2015. "Optimal appointment scheduling in continuous time: The lag order approximation method," European Journal of Operational Research, Elsevier, vol. 240(1), pages 213-219.
    16. Lili Liu & Guochun Tang & Baoqiang Fan & Xingpeng Wang, 2015. "Two-person cooperative games on scheduling problems in outpatient pharmacy dispensing process," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 938-948, November.
    17. van Beek, Andries & Malmberg, Benjamin & Borm, Peter & Quant, Marieke & Schouten, Jop, 2021. "Cooperation and Competition in Linear Production and Sequencing Processes," Discussion Paper 2021-011, Tilburg University, Center for Economic Research.
    18. Ramachandra, Girish & Elmaghraby, Salah E., 2006. "Sequencing precedence-related jobs on two machines to minimize the weighted completion time," International Journal of Production Economics, Elsevier, vol. 100(1), pages 44-58, March.
    19. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    20. Gabriel Zayas‐Cabán & Emmett J. Lodree & David L. Kaufman, 2020. "Optimal Control of Parallel Queues for Managing Volunteer Convergence," Production and Operations Management, Production and Operations Management Society, vol. 29(10), pages 2268-2288, October.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:39:y:1992:i:2:p:247-264. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.