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. 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.
    2. 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.

    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. Hanen Akrout & Bassem Jarboui & Patrick Siarry & Abdelwaheb Rebaï, 2012. "A GRASP based on DE to solve single machine scheduling problem with SDST," Computational Optimization and Applications, Springer, vol. 51(1), pages 411-435, January.
    3. Louis-Philippe Bigras & Michel Gamache & Gilles Savard, 2008. "Time-Indexed Formulations and the Total Weighted Tardiness Problem," INFORMS Journal on Computing, INFORMS, vol. 20(1), pages 133-142, February.
    4. 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.
    5. Rubing Chen & Jinjiang Yuan, 2019. "Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines," Journal of Scheduling, Springer, vol. 22(5), pages 595-601, October.
    6. S-O Shim & Y-D Kim, 2007. "Minimizing total tardiness in an unrelated parallel-machine scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 346-354, March.
    7. 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.
    8. 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.
    9. 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.
    10. Natashia Boland & Riley Clement & Hamish Waterer, 2016. "A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 14-30, February.
    11. 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.
    12. Qiulan Zhao & Lingfa Lu & Jinjiang Yuan, 2016. "Rescheduling with new orders and general maximum allowable time disruptions," 4OR, Springer, vol. 14(3), pages 261-280, September.
    13. 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.
    14. Lee, Young Hoon & Pinedo, Michael, 1997. "Scheduling jobs on parallel machines with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 100(3), pages 464-474, August.
    15. 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.
    16. 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.
    17. 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.
    18. Hariri, A. M. A. & Potts, C. N., 1997. "A branch and bound algorithm for the two-stage assembly scheduling problem," European Journal of Operational Research, Elsevier, vol. 103(3), pages 547-556, December.
    19. Jorge M. S. Valente & Rui A. F. S. Alves, 2003. "Heuristics for the Early/Tardy Scheduling Problem with Release Dates," FEP Working Papers 130, Universidade do Porto, Faculdade de Economia do Porto.
    20. 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.

    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.