IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v42y2021i2d10.1007_s10878-021-00709-1.html
   My bibliography  Save this article

A note on the single machine CON and CONW problems with lot scheduling

Author

Listed:
  • Baruch Mor

    (Ariel University)

  • Gur Mosheiov

    (The Hebrew University)

Abstract

We study extensions of the classical single machine common due-date (CON) and common due-window (CONW) assignment problems to the setting of lot scheduling. In the CON problem, all the jobs share a common due-date, and jobs completed prior to or after the due-date are penalized according to their earliness/tardiness. In CONW, there exists a time interval, such that jobs completed within this interval are not penalized. In both cases the due-date/due-window are decision variables. In lot scheduling, a number of customer orders of different sizes may be processed in the same lot. We allow order splitting between consecutive lots. The objective is to find the order allocation to lots, such that the total cost of earliness, tardiness and due-date/due-window is minimized. Given $$n$$ n orders, and under the very realistic assumption that the lot capacity is of the order of $$n$$ n , we introduce polynomial time dynamic programming algorithms for both extensions. Our numerical tests indicate that both algorithms can easily solve medium-size problems.

Suggested Citation

  • Baruch Mor & Gur Mosheiov, 2021. "A note on the single machine CON and CONW problems with lot scheduling," Journal of Combinatorial Optimization, Springer, vol. 42(2), pages 327-338, August.
    • Handle: RePEc:spr:jcomop:v:42:y:2021:i:2:d:10.1007_s10878-021-00709-1
    DOI: 10.1007/s10878-021-00709-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-021-00709-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-021-00709-1?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
    ---><---

    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. Baruch Mor & Gur Mosheiov, 2017. "A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance," Journal of Combinatorial Optimization, Springer, vol. 33(4), pages 1454-1468, May.
    2. Gordon, Valery & Proth, Jean-Marie & Chu, Chengbin, 2002. "A survey of the state-of-the-art of common due date assignment and scheduling research," European Journal of Operational Research, Elsevier, vol. 139(1), pages 1-25, May.
    3. S. S. Panwalkar & M. L. Smith & A. Seidmann, 1982. "Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem," Operations Research, INFORMS, vol. 30(2), pages 391-399, April.
    4. Kerem Bülbül & Safia Kedad-Sidhoum & Halil Şen, 2019. "Single-machine common due date total earliness/tardiness scheduling with machine unavailability," Journal of Scheduling, Springer, vol. 22(5), pages 543-565, October.
    5. Liman, Surya D. & Panwalkar, Shrikant S. & Thongmee, Sansern, 1996. "Determination of common due window location in a single machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 93(1), pages 68-74, August.
    6. Janiak, Adam & Janiak, Władysław A. & Krysiak, Tomasz & Kwiatkowski, Tomasz, 2015. "A survey on scheduling problems with due windows," European Journal of Operational Research, Elsevier, vol. 242(2), pages 347-357.
    7. Xiaoyun Xiong & Dujuan Wang & T.C. Edwin Cheng & Chin-Chia Wu & Yunqiang Yin, 2018. "Single-machine scheduling and common due date assignment with potential machine disruption," International Journal of Production Research, Taylor & Francis Journals, vol. 56(3), pages 1345-1360, February.
    8. Baruch Mor, 2019. "Minmax scheduling problems with common due-date and completion time penalty," Journal of Combinatorial Optimization, Springer, vol. 38(1), pages 50-71, July.
    9. Baruch Mor & Gur Mosheiov & Dana Shapira, 2021. "Single machine lot scheduling with optional job-rejection," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 1-11, January.
    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. 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).
    2. 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.
    3. Gur Mosheiov & Assaf Sarig, 2024. "The minmax due-date assignment problem with acceptable lead-times," Annals of Operations Research, Springer, vol. 343(1), pages 401-410, December.
    4. Gur Mosheiov & Assaf Sarig, 2023. "A note on lot scheduling on a single machine to minimize maximum weighted tardiness," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-11, July.

    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. 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.
    2. Shabtay, Dvir & Mosheiov, Gur & Oron, Daniel, 2022. "Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work," European Journal of Operational Research, Elsevier, vol. 303(1), pages 66-77.
    3. Hui Zhu & Min Li & Zhangjin Zhou & Yun You, 2016. "Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3475-3490, June.
    4. Baruch Mor & Gur Mosheiov, 2021. "Minmax due-date assignment on a two-machine flowshop," Annals of Operations Research, Springer, vol. 305(1), pages 191-209, October.
    5. Baruch Mor, 2019. "Minmax scheduling problems with common due-date and completion time penalty," Journal of Combinatorial Optimization, Springer, vol. 38(1), pages 50-71, July.
    6. Min Ji & Xin Zhang & Xiaoying Tang & T.C.E. Cheng & Guiyi Wei & Yuanyuan Tan, 2016. "Group scheduling with group-dependent multiple due windows assignment," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1244-1256, February.
    7. Baruch Mor, 2022. "Minmax common flow-allowance problems with convex resource allocation and position-dependent workloads," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 79-97, January.
    8. Oğuzhan Ahmet Arik, 2023. "A heuristic for single machine common due date assignment problem with different earliness/tardiness weights," OPSEARCH, Springer;Operational Research Society of India, vol. 60(3), pages 1561-1574, September.
    9. G Mosheiov & A Sarig, 2008. "A due-window assignment problem with position-dependent processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(7), pages 997-1003, July.
    10. Lei Pan & Xinyu Sun & Ji-Bo Wang & Li-Han Zhang & Dan-Yang Lv, 2023. "Due date assignment single-machine scheduling with delivery times, position-dependent weights and deteriorating jobs," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-16, May.
    11. Leyvand, Yaron & Shabtay, Dvir & Steiner, George, 2010. "A unified approach for scheduling with convex resource consumption functions using positional penalties," European Journal of Operational Research, Elsevier, vol. 206(2), pages 301-312, October.
    12. Feng Li & Zhi-Long Chen & Zhi-Long Chen, 2017. "Integrated Production, Inventory and Delivery Problems: Complexity and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 232-250, May.
    13. Lin, Shih-Wei & Chou, Shuo-Yan & Ying, Kuo-Ching, 2007. "A sequential exchange approach for minimizing earliness-tardiness penalties of single-machine scheduling with a common due date," European Journal of Operational Research, Elsevier, vol. 177(2), pages 1294-1301, March.
    14. Andreas C. Nearchou & Sotiris L. Omirou, 2024. "Self-Adaptive Biased Differential Evolution for Scheduling Against Common Due Dates," SN Operations Research Forum, Springer, vol. 5(2), pages 1-29, June.
    15. Koulamas, Christos & Gupta, Sushil & Kyparisis, George J., 2010. "A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times," European Journal of Operational Research, Elsevier, vol. 205(2), pages 479-482, September.
    16. Mor, Baruch & Mosheiov, Gur, 2016. "Minsum and minmax scheduling on a proportionate flowshop with common flow-allowance," European Journal of Operational Research, Elsevier, vol. 254(2), pages 360-370.
    17. Huynh Tuong, Nguyen & Soukhal, Ameur, 2010. "Due dates assignment and JIT scheduling with equal-size jobs," European Journal of Operational Research, Elsevier, vol. 205(2), pages 280-289, September.
    18. Biskup, Dirk & Feldmann, Martin, 2005. "On scheduling around large restrictive common due windows," European Journal of Operational Research, Elsevier, vol. 162(3), pages 740-761, May.
    19. Gordon, Valery & Proth, Jean-Marie & Chu, Chengbin, 2002. "A survey of the state-of-the-art of common due date assignment and scheduling research," European Journal of Operational Research, Elsevier, vol. 139(1), pages 1-25, May.
    20. Gerstl, Enrique & Mosheiov, Gur, 2013. "Due-window assignment with identical jobs on parallel uniform machines," European Journal of Operational Research, Elsevier, vol. 229(1), pages 41-47.

    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:spr:jcomop:v:42:y:2021:i:2:d:10.1007_s10878-021-00709-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.