IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v40y2020i4d10.1007_s10878-020-00649-2.html
   My bibliography  Save this article

Minimizing maximum delivery completion time for order scheduling with rejection

Author

Listed:
  • Ren-Xia Chen

    (Zhongyuan University of Technology)

  • Shi-Sheng Li

    (Zhongyuan University of Technology)

Abstract

We study an order scheduling problem with rejection, in which each order consists of multiple product types and each product type should be manufactured on a dedicated machine. The aim is to find a solution to minimize a linear sum of the maximum delivery completion time of the accepted orders and the total penalty of the rejected orders. Even if the delivery times of all orders are zero, the problem is shown to be binary $$\mathcal{NP}$$ NP -hard in the two-machine case and it is shown to be unary $$\mathcal{NP}$$ NP -hard when the number of machines is arbitrary. Three approximation algorithms are proposed and their worst-case performance ratios are analyzed. For the scenario where the number of machines is fixed, a pseudo-polynomial dynamic programming algorithm and a fully polynomial time approximation scheme are devised for it.

Suggested Citation

  • Ren-Xia Chen & Shi-Sheng Li, 2020. "Minimizing maximum delivery completion time for order scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1044-1064, November.
    • Handle: RePEc:spr:jcomop:v:40:y:2020:i:4:d:10.1007_s10878-020-00649-2
    DOI: 10.1007/s10878-020-00649-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-020-00649-2
    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-020-00649-2?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. Lee, Ik Sun, 2013. "Minimizing total tardiness for the order scheduling problem," International Journal of Production Economics, Elsevier, vol. 144(1), pages 128-134.
    2. Naderi, Bahman & Roshanaei, Vahid, 2020. "Branch-Relax-and-Check: A tractable decomposition method for order acceptance and identical parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 286(3), pages 811-827.
    3. Chang Sup Sung & Sang Hum Yoon, 1998. "Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines," International Journal of Production Economics, Elsevier, vol. 54(3), pages 247-255, May.
    4. Somaye Geramipour & Ghasem Moslehi & Mohammad Reisi-Nafchi, 2017. "Maximizing the profit in customer’s order acceptance and scheduling problem with weighted tardiness penalty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 89-101, January.
    5. Wang, Guoqing & Cheng, T.C. Edwin, 2007. "Customer order scheduling to minimize total weighted completion time," Omega, Elsevier, vol. 35(5), pages 623-626, October.
    6. Reza Ahmadi & Uttarayan Bagchi & Thomas A. Roemer, 2005. "Coordinated scheduling of customer orders for quick response," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(6), pages 493-512, September.
    7. Carlier, Jacques, 1982. "The one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 11(1), pages 42-47, September.
    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. Framinan, Jose M. & Perez-Gonzalez, Paz, 2018. "Order scheduling with tardiness objective: Improved approximate solutions," European Journal of Operational Research, Elsevier, vol. 266(3), pages 840-850.
    10. 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.
    11. Joseph Leung & Haibing Li & Michael Pinedo, 2008. "Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time," Annals of Operations Research, Springer, vol. 159(1), pages 107-123, March.
    12. Zhongshun Shi & Zewen Huang & Leyuan Shi, 2018. "Customer order scheduling on batch processing machines with incompatible job families," International Journal of Production Research, Taylor & Francis Journals, vol. 56(1-2), pages 795-808, January.
    13. Liqi Zhang & Lingfa Lu, 2016. "Parallel-machine scheduling with release dates and rejection," 4OR, Springer, vol. 14(2), pages 165-172, June.
    14. Framinan, Jose M. & Perez-Gonzalez, Paz & Fernandez-Viagas, Victor, 2019. "Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures," European Journal of Operational Research, Elsevier, vol. 273(2), pages 401-417.
    15. Zhang, Liqi & Lu, Lingfa & Yuan, Jinjiang, 2009. "Single machine scheduling with release dates and rejection," European Journal of Operational Research, Elsevier, vol. 198(3), pages 975-978, November.
    16. Ou, Jinwen & Zhong, Xueling & Wang, Guoqing, 2015. "An improved heuristic for parallel machine scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 241(3), pages 653-661.
    17. Imed Kacem & Hans Kellerer & Maryam Seifaddini, 2016. "Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 970-981, October.
    18. Xueling Zhong & Zhangming Pan & Dakui Jiang, 2017. "Scheduling with release times and rejection on two parallel machines," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 934-944, April.
    19. Lin, B.M.T. & Kononov, A.V., 2007. "Customer order scheduling to minimize the number of late jobs," European Journal of Operational Research, Elsevier, vol. 183(2), pages 944-948, December.
    20. Wagneur, E. & Sriskandarajah, C., 1993. "Openshops with jobs overlap," European Journal of Operational Research, Elsevier, vol. 71(3), pages 366-378, December.
    21. C. N. Potts, 1980. "Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times," Operations Research, INFORMS, vol. 28(6), pages 1436-1441, December.
    22. Xianzhao Zhang & Dachuan Xu & Donglei Du & Chenchen Wu, 2018. "Approximation algorithms for precedence-constrained identical machine scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 35(1), pages 318-330, January.
    23. Xiuli Wang & Guodong Huang & Xiuwu Hu & T C Edwin Cheng, 2015. "Order acceptance and scheduling on two identical parallel machines," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(10), pages 1755-1767, October.
    24. Cheng He & Joseph Y.-T. Leung & Kangbok Lee & Michael L. Pinedo, 2016. "Improved algorithms for single machine scheduling with release dates and rejections," 4OR, Springer, vol. 14(1), pages 41-55, March.
    25. Xueling Zhong & Jinwen Ou, 2017. "Improved approximation algorithms for parallel machine scheduling with release dates and job rejection," 4OR, Springer, vol. 15(4), pages 387-406, 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. Lingfa Lu & Liqi Zhang, 2023. "Scheduling problems with rejection to minimize the k-th power of the makespan plus the total rejection cost," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-17, August.

    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. Framinan, Jose M. & Perez-Gonzalez, Paz & Fernandez-Viagas, Victor, 2019. "Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures," European Journal of Operational Research, Elsevier, vol. 273(2), pages 401-417.
    2. 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.
    3. Xiaofei Liu & Weidong Li, 2020. "Approximation Algorithm for the Single Machine Scheduling Problem with Release Dates and Submodular Rejection Penalty," Mathematics, MDPI, vol. 8(1), pages 1-11, January.
    4. Lung-Yu Li & Jian-You Xu & Shuenn-Ren Cheng & Xingong Zhang & Win-Chin Lin & Jia-Cheng Lin & Zong-Lin Wu & Chin-Chia Wu, 2022. "A Genetic Hyper-Heuristic for an Order Scheduling Problem with Two Scenario-Dependent Parameters in a Parallel-Machine Environment," Mathematics, MDPI, vol. 10(21), pages 1-22, November.
    5. Xiaofei Liu & Man Xiao & Weidong Li & Yaoyu Zhu & Lei Ma, 2023. "Algorithms for single machine scheduling problem with release dates and submodular penalties," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-18, May.
    6. Tarhan, İstenç & Oğuz, Ceyda, 2022. "A matheuristic for the generalized order acceptance and scheduling problem," European Journal of Operational Research, Elsevier, vol. 299(1), pages 87-103.
    7. Xiaofei Liu & Weidong Li & Yaoyu Zhu, 2021. "Single Machine Vector Scheduling with General Penalties," Mathematics, MDPI, vol. 9(16), pages 1-16, August.
    8. Weidong Li & Qianna Cui, 2018. "Vector scheduling with rejection on a single machine," 4OR, Springer, vol. 16(1), pages 95-104, March.
    9. Chun-Lung Chen, 2023. "An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints," Mathematics, MDPI, vol. 11(6), pages 1-14, March.
    10. Baruch Mor & Gur Mosheiov, 2021. "A note: flowshop scheduling with linear deterioration and job-rejection," 4OR, Springer, vol. 19(1), pages 103-111, March.
    11. Mohamadreza Dabiri & Mehdi Yazdani & Bahman Naderi & Hassan Haleh, 2022. "Modeling and solution methods for hybrid flow shop scheduling problem with job rejection," Operational Research, Springer, vol. 22(3), pages 2721-2765, July.
    12. Xueling Zhong & Jinwen Ou, 2017. "Improved approximation algorithms for parallel machine scheduling with release dates and job rejection," 4OR, Springer, vol. 15(4), pages 387-406, December.
    13. Husam Dauod & Nieqing Cao & Debiao Li & Jaehee Kim & Sang Won Yoon & Daehan Won, 2023. "An Order Scheduling Heuristic to Minimize the Total Collation Delays and the Makespan in High-Throughput Make-to-Order Manufacturing Systems," SN Operations Research Forum, Springer, vol. 4(2), pages 1-23, June.
    14. 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.
    15. Imed Kacem & Hans Kellerer, 2024. "Minimizing the maximum lateness for scheduling with release times and job rejection," Journal of Combinatorial Optimization, Springer, vol. 48(3), pages 1-22, October.
    16. Zhong, Xueling & Fan, Jie & Ou, Jinwen, 2022. "Coordinated scheduling of the outsourcing, in-house production and distribution operations," European Journal of Operational Research, Elsevier, vol. 302(2), pages 427-437.
    17. Jinwen Ou & Xueling Zhong & Xiangtong Qi, 2016. "Scheduling parallel machines with inclusive processing set restrictions and job rejection," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(8), pages 667-681, December.
    18. Xueling Zhong & Zhangming Pan & Dakui Jiang, 2017. "Scheduling with release times and rejection on two parallel machines," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 934-944, April.
    19. Gur Mosheiov & Assaf Sarig & Vitaly Strusevich, 2020. "Minmax scheduling and due-window assignment with position-dependent processing times and job rejection," 4OR, Springer, vol. 18(4), pages 439-456, December.
    20. Xiaofei Liu & Peiyin Xing & Weidong Li, 2020. "Approximation Algorithms for the Submodular Load Balancing with Submodular Penalties," Mathematics, MDPI, vol. 8(10), pages 1-12, October.

    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:40:y:2020:i:4:d:10.1007_s10878-020-00649-2. 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.