IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v199y2009i3p695-701.html
   My bibliography  Save this article

The one machine scheduling problem: Insertion of a job under the real-time constraint

Author

Listed:
  • Duron, C.
  • Ould Louly, M.A.
  • Proth, J.-M.

Abstract

We consider a single resource that performs a set of jobs, each job being defined by its operation time and its due date. Jobs are not preemptive, which means that a job that starts cannot be interrupted before completion. These jobs have been scheduled so as to minimize the total tardiness, and the schedule is known. A new job appears in the system at the current point in time that is called time 0. Its operation period and its due date are known only at the time of its appearance that is at time 0. For this particular job, the due date cannot be violated. The execution order of the jobs from the given schedule cannot be changed, but they can be postponed if needed. The objective is to insert the new job in the given schedule in order not to violate the deadline while minimizing the increase of the total tardiness resulting from the postponement of some scheduled jobs required by the insertion of the new job. A new job of the same kind appears from time to time in this system. We suppose that when a new job arises, the previous new job (if any) has been scheduled. Thus, the insertion process applies at unexpected points in time and the deadline is short, which means that this process must run in real-time. The proposed algorithm is composed of two parts: an offline part that prepares the real-time computation and an online part that runs in real-time.

Suggested Citation

  • Duron, C. & Ould Louly, M.A. & Proth, J.-M., 2009. "The one machine scheduling problem: Insertion of a job under the real-time constraint," European Journal of Operational Research, Elsevier, vol. 199(3), pages 695-701, December.
    • Handle: RePEc:eee:ejores:v:199:y:2009:i:3:p:695-701
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00458-X
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Chris N. Potts & Luk N. Van Wassenhove, 1985. "A Branch and Bound Algorithm for the Total Weighted Tardiness Problem," Operations Research, INFORMS, vol. 33(2), pages 363-377, April.
    2. Koulamas, Christos & Kyparisis, George J., 2001. "Single machine scheduling with release times, deadlines and tardiness objectives," European Journal of Operational Research, Elsevier, vol. 133(2), pages 447-453, January.
    3. Akturk, M. Selim & Ozdemir, Deniz, 2001. "A new dominance rule to minimize total weighted tardiness with unequal release dates," European Journal of Operational Research, Elsevier, vol. 135(2), pages 394-412, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yingfeng Zhang & Dong Xi & Haidong Yang & Fei Tao & Zhe Wang, 2019. "Cloud manufacturing based service encapsulation and optimal configuration method for injection molding machine," Journal of Intelligent Manufacturing, Springer, vol. 30(7), pages 2681-2699, October.
    2. Liu, Weihua & Liang, Zhicheng & Ye, Zi & Liu, Liang, 2016. "The optimal decision of customer order decoupling point for order insertion scheduling in logistics service supply chain," International Journal of Production Economics, Elsevier, vol. 175(C), pages 50-60.

    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. Su, Ling-Huey & Chen, Chung-Jung, 2008. "Minimizing total tardiness on a single machine with unequal release dates," European Journal of Operational Research, Elsevier, vol. 186(2), pages 496-503, April.
    2. Haiyan Wang & Chung‐Yee Lee, 2005. "Production and transport logistics scheduling with two transport mode choices," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(8), pages 796-809, December.
    3. H. A. J. Crauwels & C. N. Potts & L. N. Van Wassenhove, 1998. "Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 10(3), pages 341-350, August.
    4. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    5. Roberto Cordone & Pierre Hosteins & Giovanni Righini, 2018. "A Branch-and-Bound Algorithm for the Prize-Collecting Single-Machine Scheduling Problem with Deadlines and Total Tardiness Minimization," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 168-180, February.
    6. Og[breve]uz, Ceyda & Sibel Salman, F. & Bilgintürk YalçIn, Zehra, 2010. "Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, Elsevier, vol. 125(1), pages 200-211, May.
    7. Yagiura, Mutsunori & Ibaraki, Toshihide, 1996. "The use of dynamic programming in genetic algorithms for permutation problems," European Journal of Operational Research, Elsevier, vol. 92(2), pages 387-401, July.
    8. Wang, Xiuli & Xie, Xingzi & Cheng, T.C.E., 2013. "Order acceptance and scheduling in a two-machine flowshop," International Journal of Production Economics, Elsevier, vol. 141(1), pages 366-376.
    9. Borgonjon, Tessa & Maenhout, Broos, 2022. "An exact approach for the personnel task rescheduling problem with task retiming," European Journal of Operational Research, Elsevier, vol. 296(2), pages 465-484.
    10. Shiwei Chang & Hirofumi Matsuo & Guochun Tang, 1990. "Worst‐case analysis of local search heuristics for the one‐machine total tardiness problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(1), pages 111-121, February.
    11. Jouglet, Antoine & Savourey, David & Carlier, Jacques & Baptiste, Philippe, 2008. "Dominance-based heuristics for one-machine total cost scheduling problems," European Journal of Operational Research, Elsevier, vol. 184(3), pages 879-899, February.
    12. Valente, Jorge M.S., 2007. "Improving the performance of the ATC dispatch rule by using workload data to determine the lookahead parameter value," International Journal of Production Economics, Elsevier, vol. 106(2), pages 563-573, April.
    13. J M S Valente & R A F S Alves, 2005. "Improved lower bounds for the early/tardy scheduling problem with no idle time," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(5), pages 604-612, May.
    14. Ronconi, Débora P. & Henriques, Luís R.S., 2009. "Some heuristic algorithms for total tardiness minimization in a flowshop with blocking," Omega, Elsevier, vol. 37(2), pages 272-281, April.
    15. Bilge, Umit & Kurtulan, Mujde & Kirac, Furkan, 2007. "A tabu search algorithm for the single machine total weighted tardiness problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1423-1435, February.
    16. A Volgenant & I Y Zwiers, 2007. "Partial enumeration in heuristics for some combinatorial optimization problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(1), pages 73-79, January.
    17. Chengbin Chu, 1992. "A branch‐and‐bound algorithm to minimize total tardiness with different release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 265-283, March.
    18. Simon Thevenin & Nicolas Zufferey & Marino Widmer, 2016. "Order acceptance and scheduling with earliness and tardiness penalties," Journal of Heuristics, Springer, vol. 22(6), pages 849-890, December.
    19. Cheng, T. C. E. & Ng, C. T. & Yuan, J. J. & Liu, Z. H., 2005. "Single machine scheduling to minimize total weighted tardiness," European Journal of Operational Research, Elsevier, vol. 165(2), pages 423-443, September.
    20. Hanane Krim & Nicolas Zufferey & Jean-Yves Potvin & Rachid Benmansour & David Duvivier, 2022. "Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times," Journal of Scheduling, Springer, vol. 25(1), pages 89-105, February.

    More about this item

    Keywords

    Real-time Scheduling Single machine;

    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:eee:ejores:v:199:y:2009:i:3:p:695-701. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.