IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v7y2019i9p819-d264520.html
   My bibliography  Save this article

Transportation and Batching Scheduling for Minimizing Total Weighted Completion Time

Author

Listed:
  • Hongjun Wei

    (School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China)

  • Jinjiang Yuan

    (School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China)

  • Yuan Gao

    (School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China)

Abstract

We consider the coordination of transportation and batching scheduling with one single vehicle for minimizing total weighted completion time. The computational complexity of the problem with batch capacity of at least 2 was posed as open in the literature. For this problem, we show the unary NP-hardness for every batch capacity at least 3 and present a polynomial-time 3-approximation algorithm when the batch capacity is at least 2.

Suggested Citation

  • Hongjun Wei & Jinjiang Yuan & Yuan Gao, 2019. "Transportation and Batching Scheduling for Minimizing Total Weighted Completion Time," Mathematics, MDPI, vol. 7(9), pages 1-10, September.
    • Handle: RePEc:gam:jmathe:v:7:y:2019:i:9:p:819-:d:264520
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/7/9/819/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/7/9/819/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Allahverdi, Ali, 2015. "The third comprehensive survey on scheduling problems with setup times/costs," European Journal of Operational Research, Elsevier, vol. 246(2), pages 345-378.
    2. J. A. Hoogeveen & T. Kawaguchi, 1999. "Minimizing Total Completion Time in a Two-Machine Flowshop: Analysis of Special Cases," Mathematics of Operations Research, INFORMS, vol. 24(4), pages 887-910, November.
    3. Michele Ciavotta & Carlo Meloni & Marco Pranzo, 2016. "Speeding up a Rollout algorithm for complex parallel machine scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4993-5009, August.
    4. Nicholas Hall & Chris Potts, 2005. "The Coordination of Scheduling and Batch Deliveries," Annals of Operations Research, Springer, vol. 135(1), pages 41-64, March.
    5. Zhi-Long Chen, 2010. "Integrated Production and Outbound Distribution Scheduling: Review and Extensions," Operations Research, INFORMS, vol. 58(1), pages 130-148, February.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. 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.
    3. Nodari Vakhania & Badri Mamporia, 2020. "Fast Algorithms for Basic Supply Chain Scheduling Problems," Mathematics, MDPI, vol. 8(11), pages 1-19, November.
    4. Hosseini, Amir & Otto, Alena & Pesch, Erwin, 2024. "Scheduling in manufacturing with transportation: Classification and solution techniques," European Journal of Operational Research, Elsevier, vol. 315(3), pages 821-843.
    5. Elimam, A.A. & Dodin, B., 2013. "Project scheduling in optimizing integrated supply chain operations," European Journal of Operational Research, Elsevier, vol. 224(3), pages 530-541.
    6. Hua Gong & Lixin Tang & Joseph Y.T. Leung, 2016. "Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(6), pages 492-502, September.
    7. Gao, Su & Qi, Lian & Lei, Lei, 2015. "Integrated batch production and distribution scheduling with limited vehicle capacity," International Journal of Production Economics, Elsevier, vol. 160(C), pages 13-25.
    8. Liang-Liang Fu & Mohamed Ali Aloulou & Christian Artigues, 2018. "Integrated production and outbound distribution scheduling problems with job release dates and deadlines," Journal of Scheduling, Springer, vol. 21(4), pages 443-460, August.
    9. B.G. Khairov & D.T. Novikov & T.A. Prokof'yeva & I.O. Protsenko & S.M. Khairova, 2017. "Reflexive Governance of Import Substitution Mechanism in Clusters," European Research Studies Journal, European Research Studies Journal, vol. 0(3A), pages 470-483.
    10. Sağlam, Ümit & Banerjee, Avijit, 2018. "Integrated multiproduct batch production and truck shipment scheduling under different shipping policies," Omega, Elsevier, vol. 74(C), pages 70-81.
    11. Michael Geurtsen & Jelle Adan & Alp Akçay, 2024. "Integrated maintenance and production scheduling for unrelated parallel machines with setup times," Flexible Services and Manufacturing Journal, Springer, vol. 36(3), pages 1046-1079, September.
    12. Wan, Long & Zhang, An, 2014. "Coordinated scheduling on parallel machines with batch delivery," International Journal of Production Economics, Elsevier, vol. 150(C), pages 199-203.
    13. Ed Burton & David John Edwards & Chris Roberts & Nicholas Chileshe & Joseph H. K. Lai, 2021. "Delineating the Implications of Dispersing Teams and Teleworking in an Agile UK Construction Sector," Sustainability, MDPI, vol. 13(17), pages 1-21, September.
    14. Jianxin Fang & Brenda Cheang & Andrew Lim, 2023. "Problems and Solution Methods of Machine Scheduling in Semiconductor Manufacturing Operations: A Survey," Sustainability, MDPI, vol. 15(17), pages 1-44, August.
    15. Wang, Ling & Sun, Lin-Yan & Sun, Lin-Hui & Wang, Ji-Bo, 2010. "On three-machine flow shop scheduling with deteriorating jobs," International Journal of Production Economics, Elsevier, vol. 125(1), pages 185-189, May.
    16. Yunqiang Yin & Doudou Li & Dujuan Wang & T. C. E. Cheng, 2021. "Single-machine serial-batch delivery scheduling with two competing agents and due date assignment," Annals of Operations Research, Springer, vol. 298(1), pages 497-523, March.
    17. Azeddine Cheref & Alessandro Agnetis & Christian Artigues & Jean-Charles Billaut, 2017. "Complexity results for an integrated single machine scheduling and outbound delivery problem with fixed sequence," Journal of Scheduling, Springer, vol. 20(6), pages 681-693, December.
    18. Hrabec, Dušan & Hvattum, Lars Magnus & Hoff, Arild, 2022. "The value of integrated planning for production, inventory, and routing decisions: A systematic review and meta-analysis," International Journal of Production Economics, Elsevier, vol. 248(C).
    19. Shahvari, Omid & Logendran, Rasaratnam, 2016. "Hybrid flow shop batching and scheduling with a bi-criteria objective," International Journal of Production Economics, Elsevier, vol. 179(C), pages 239-258.
    20. Vinicius M. Ton & Nathália C. O. da Silva & Angel Ruiz & José E. Pécora & Cassius T. Scarpin & Valérie Bélenger, 2024. "Real-time management of intra-hospital patient transport requests," Health Care Management Science, Springer, vol. 27(2), pages 208-222, June.

    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:gam:jmathe:v:7:y:2019:i:9:p:819-:d:264520. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.