IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v59y2011i6p1504-1511.html
   My bibliography  Save this article

Revised Delivery-Time Quotation in Scheduling with Tardiness Penalties

Author

Listed:
  • George Steiner

    (DeGroote School of Business, McMaster University, Hamilton, Ontario L8S 4M4, Canada)

  • Rui Zhang

    (DeGroote School of Business, McMaster University, Hamilton, Ontario L8S 4M4, Canada)

Abstract

There are many situations in supply chain scheduling when the supplier finds it impossible to meet the promised due dates for some orders. We present a model for the rescheduling of orders with simultaneous assignment of attainable revised due dates to minimize due date escalation and tardiness penalties for the supplier. We show that the problem is equivalent to minimizing the total tardiness with rejection with respect to the original due dates. We prove that the problem is (N-script)(P-script)-hard and present a pseudopolynomial algorithm for it. We also present a fully polynomial time approximation scheme for the problem. Finally, we discuss the implications of our solution for setting fair tardiness penalties when due dates have to be renegotiated because of the delays.

Suggested Citation

  • George Steiner & Rui Zhang, 2011. "Revised Delivery-Time Quotation in Scheduling with Tardiness Penalties," Operations Research, INFORMS, vol. 59(6), pages 1504-1511, December.
    • Handle: RePEc:inm:oropre:v:59:y:2011:i:6:p:1504-1511
    DOI: 10.1287/opre.1110.0948
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.0948
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.0948?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. Nicholas G. Hall & Chris N. Potts, 2003. "Supply chain scheduling: Batching and delivery," Operations Research, INFORMS, vol. 51(4), pages 566-584, August.
    2. Kenneth R. Baker & Gary D. Scudder, 1990. "Sequencing with Earliness and Tardiness Penalties: A Review," Operations Research, INFORMS, vol. 38(1), pages 22-36, February.
    3. Slotnick, Susan A. & Sobel, Matthew J., 2005. "Manufacturing lead-time rules: Customer retention versus tardiness costs," European Journal of Operational Research, Elsevier, vol. 163(3), pages 825-856, June.
    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. Peihai Liu & Xiwen Lu, 2020. "New approximation algorithms for machine scheduling with rejection on single and parallel machine," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 929-952, November.
    2. Esaignani Selvarajah & Rui Zhang, 2014. "Supply chain scheduling to minimize holding costs with outsourcing," Annals of Operations Research, Springer, vol. 217(1), pages 479-490, June.
    3. Sang, Yao-Wen & Wang, Jun-Qiang & Sterna, Małgorzata & Błażewicz, Jacek, 2023. "Single machine scheduling with due date assignment to minimize the total weighted lead time penalty and late work," Omega, Elsevier, vol. 121(C).
    4. Koulamas, Christos & Kyparisis, George J., 2023. "A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 305(3), pages 999-1017.
    5. Liqi Zhang & Lingfa Lu & Jinjiang Yuan, 2016. "Two-machine open-shop scheduling with rejection to minimize the makespan," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(2), pages 519-529, March.
    6. Liqi Zhang & Lingfa Lu & Shisheng Li, 2016. "New results on two-machine flow-shop scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1493-1504, May.
    7. 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.
    8. Lingfa Lu & Liqi Zhang, 2017. "Single-machine scheduling with production and rejection costs to minimize the maximum earliness," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 331-342, August.
    9. Shi-Sheng Li & Ren-Xia Chen, 2017. "Scheduling with Rejection and a Deteriorating Maintenance Activity on a Single Machine," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(02), pages 1-17, April.
    10. Christos Koulamas & George Steiner, 2021. "New results for scheduling to minimize tardiness on one machine with rejection and related problems," Journal of Scheduling, Springer, vol. 24(1), pages 27-34, February.
    11. Na Geng & Letian Chen & Ran Liu & Yanhong Zhu, 2017. "Optimal patient assignment for W queueing network in a diagnostic facility setting," International Journal of Production Research, Taylor & Francis Journals, vol. 55(19), pages 5609-5631, October.
    12. Liqi Zhang & Lingfa Lu, 2016. "Parallel-machine scheduling with release dates and rejection," 4OR, Springer, vol. 14(2), pages 165-172, June.

    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. Dvir Shabtay & George Steiner, 2007. "Optimal Due Date Assignment and Resource Allocation to Minimize the Weighted Number of Tardy Jobs on a Single Machine," Manufacturing & Service Operations Management, INFORMS, vol. 9(3), pages 332-350, March.
    2. Rasti-Barzoki, Morteza & Hejazi, Seyed Reza, 2013. "Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains," European Journal of Operational Research, Elsevier, vol. 228(2), pages 345-357.
    3. Koulamas, Christos & Kyparisis, George J., 2023. "A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 305(3), pages 999-1017.
    4. George Steiner & Rui Zhang, 2011. "Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries," Annals of Operations Research, Springer, vol. 191(1), pages 171-181, November.
    5. Xingong, Zhang & Yong, Wang, 2015. "Single-machine scheduling CON/SLK due window assignment problems with sum-of-processed times based learning effect," Applied Mathematics and Computation, Elsevier, vol. 250(C), pages 628-635.
    6. Yang, Xianyan & Li, Feng & Liu, Zhixue & Xu, Zhou, 2024. "New exact and heuristic algorithms for general production and delivery integration," European Journal of Operational Research, Elsevier, vol. 316(2), pages 419-442.
    7. Qian, Jianbo & Steiner, George, 2013. "Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine," European Journal of Operational Research, Elsevier, vol. 225(3), pages 547-551.
    8. Dvir Shabtay & George Steiner, 2008. "The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times," Annals of Operations Research, Springer, vol. 159(1), pages 25-40, March.
    9. Beatriz Andres & Vicente Javier Blanes, 2020. "A Negotiation Approach to Support the Strategies Alignment Process in Collaborative Networks," Sustainability, MDPI, vol. 12(7), pages 1-30, April.
    10. Ullrich, Christian A., 2013. "Integrated machine scheduling and vehicle routing with time windows," European Journal of Operational Research, Elsevier, vol. 227(1), pages 152-165.
    11. Xin Feng & Yongxi Cheng & Feifeng Zheng & Yinfeng Xu, 2016. "Online integrated production–distribution scheduling problems without preemption," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1569-1585, May.
    12. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    13. Huynh Tuong, Nguyen & Soukhal, Ameur & Billaut, Jean-Charles, 2010. "A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines," European Journal of Operational Research, Elsevier, vol. 202(3), pages 646-653, May.
    14. Liang Tang & Zhihong Jin & Xuwei Qin & Ke Jing, 2019. "Supply chain scheduling in a collaborative manufacturing mode: model construction and algorithm design," Annals of Operations Research, Springer, vol. 275(2), pages 685-714, April.
    15. Wang, Gang, 2024. "Order assignment and two-stage integrated scheduling in fruit and vegetable supply chains," Omega, Elsevier, vol. 124(C).
    16. Kolahan, F. & Liang, M., 1998. "An adaptive TS approach to JIT sequencing with variable processing times and sequence-dependent setups," European Journal of Operational Research, Elsevier, vol. 109(1), pages 142-159, August.
    17. Han, Bin & Zhang, Wenjun & Lu, Xiwen & Lin, Yingzi, 2015. "On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: Minimizing the makespan and delivery cost," European Journal of Operational Research, Elsevier, vol. 244(3), pages 704-714.
    18. Selvarajah, Esaignani & Steiner, George, 2006. "Batch scheduling in a two-level supply chain--a focus on the supplier," European Journal of Operational Research, Elsevier, vol. 173(1), pages 226-240, August.
    19. Esaignani Selvarajah & Rui Zhang, 2014. "Supply chain scheduling to minimize holding costs with outsourcing," Annals of Operations Research, Springer, vol. 217(1), pages 479-490, June.
    20. Lemos, R.F. & Ronconi, D.P., 2015. "Heuristics for the stochastic single-machine problem with E/T costs," International Journal of Production Economics, Elsevier, vol. 168(C), pages 131-142.

    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:inm:oropre:v:59:y:2011:i:6:p:1504-1511. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.