IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v61y2014i4p269-285.html
   My bibliography  Save this article

Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations

Author

Listed:
  • Lixin Tang
  • Hua Gong
  • Jiyin Liu
  • Feng Li

Abstract

We study a single batching machine scheduling problem with transportation and deterioration considerations arising from steel production. A set of jobs are transported, one at a time, by a vehicle from a holding area to the single batching machine. The machine can process several jobs simultaneously as a batch. The processing time of a job will increase if the duration from the time leaving the holding area to the start of its processing exceeds a given threshold. The time needed to process a batch is the longest of the job processing times in the batch. The problem is to determine the job sequence for transportation and the job batching for processing so as to minimize the makespan and the number of batches. We study four variations (P1, P2, P3, P4) of the problem with different treatments of the two criteria. We prove that all the four variations are strongly NP‐hard and further develop polynomial time algorithms for their special cases. For each of the first three variations, we propose a heuristic algorithm and analyze its worst‐case performance. For P4, which is to find the Pareto frontier, we provide a heuristic algorithm and an exact algorithm based on branch and bound. Computational experiments show that all the heuristic algorithms perform well on randomly generated problem instances, and the exact algorithm for P4 can obtain Pareto optimal schedules for small‐scale instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 269–285, 2014

Suggested Citation

  • Lixin Tang & Hua Gong & Jiyin Liu & Feng Li, 2014. "Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(4), pages 269-285, June.
    • Handle: RePEc:wly:navres:v:61:y:2014:i:4:p:269-285
    DOI: 10.1002/nav.21582
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21582
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.21582?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. Leung, Joseph Y.-T. & Ng, C.T. & Cheng, T.C. Edwin, 2008. "Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1090-1099, June.
    2. Chung-Yee Lee & Reha Uzsoy & Louis A. Martin-Vega, 1992. "Efficient Algorithms for Scheduling Semiconductor Burn-In Operations," Operations Research, INFORMS, vol. 40(4), pages 764-775, August.
    3. Chung‐Lun Li & Jinwen Ou, 2005. "Machine scheduling with pickup and delivery," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(7), pages 617-630, October.
    4. Zhi-Long Chen, 2010. "Integrated Production and Outbound Distribution Scheduling: Review and Extensions," Operations Research, INFORMS, vol. 58(1), pages 130-148, February.
    5. Al-Anzi, Fawaz S. & Allahverdi, Ali & Kovalyov, Mikhail Y., 2007. "Batching deteriorating items with applications in computer communication and reverse logistics," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1002-1011, November.
    6. Potts, Chris N. & Kovalyov, Mikhail Y., 2000. "Scheduling with batching: A review," European Journal of Operational Research, Elsevier, vol. 120(2), pages 228-249, 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. Zhou, Shengchao & Jin, Mingzhou & Du, Ni, 2020. "Energy-efficient scheduling of a single batch processing machine with dynamic job arrival times," Energy, Elsevier, vol. 209(C).
    2. Zhang, Hongbin & Yang, Yu & Wu, Feng, 2024. "Scheduling a set of jobs with convex piecewise linear cost functions on a single-batch-processing machine," Omega, Elsevier, vol. 122(C).
    3. Sun, X.T. & Chung, S.H. & Chan, Felix T.S. & Wang, Zheng, 2018. "The impact of liner shipping unreliability on the production–distribution scheduling of a decentralized manufacturing system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 242-269.
    4. 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.
    5. Florian Jaehn & Sergey Kovalev & Mikhail Y. Kovalyov & Erwin Pesch, 2014. "Multiproduct batching and scheduling with buffered rework: The case of a car paint shop," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(6), pages 458-471, September.

    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. Nodari Vakhania & Badri Mamporia, 2020. "Fast Algorithms for Basic Supply Chain Scheduling Problems," Mathematics, MDPI, vol. 8(11), pages 1-19, November.
    2. Li, Kai & Jia, Zhao-hong & Leung, Joseph Y.-T., 2015. "Integrated production and delivery on parallel batching machines," European Journal of Operational Research, Elsevier, vol. 247(3), pages 755-763.
    3. Melouk, Sharif & Damodaran, Purushothaman & Chang, Ping-Yu, 2004. "Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing," International Journal of Production Economics, Elsevier, vol. 87(2), pages 141-147, January.
    4. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    5. Xu, Jun & Wang, Jun-Qiang & Liu, Zhixin, 2022. "Parallel batch scheduling: Impact of increasing machine capacity," Omega, Elsevier, vol. 108(C).
    6. Jing Fan & Hui Shi, 0. "A three-stage supply chain scheduling problem based on the nursing assistants’ daily work in a hospital," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-13.
    7. Lin, Ran & Wang, Jun-Qiang & Liu, Zhixin & Xu, Jun, 2023. "Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions," European Journal of Operational Research, Elsevier, vol. 309(1), pages 53-64.
    8. Lin, Ran & Wang, Jun-Qiang & Oulamara, Ammar, 2023. "Online scheduling on parallel-batch machines with periodic availability constraints and job delivery," Omega, Elsevier, vol. 116(C).
    9. Eduardo Queiroga & Rian G. S. Pinheiro & Quentin Christ & Anand Subramanian & Artur A. Pessoa, 2021. "Iterated local search for single machine total weighted tardiness batch scheduling," Journal of Heuristics, Springer, vol. 27(3), pages 353-438, June.
    10. Yuan Gao & Jinjiang Yuan, 2019. "Unbounded parallel-batch scheduling under agreeable release and processing to minimize total weighted number of tardy jobs," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 698-711, October.
    11. Kovalyov, M. Y. & Potts, C. N. & Strusevich, V. A., 2004. "Batching decisions for assembly production systems," European Journal of Operational Research, Elsevier, vol. 157(3), pages 620-642, September.
    12. Nicholas G. Hall & Zhixin Liu, 2010. "Capacity Allocation and Scheduling in Supply Chains," Operations Research, INFORMS, vol. 58(6), pages 1711-1725, December.
    13. Chung Keung Poon & Wenci Yu, 2005. "On-Line Scheduling Algorithms for a Batch Machine with Finite Capacity," Journal of Combinatorial Optimization, Springer, vol. 9(2), pages 167-186, March.
    14. Zhang, Hongbin & Yang, Yu & Wu, Feng, 2024. "Scheduling a set of jobs with convex piecewise linear cost functions on a single-batch-processing machine," Omega, Elsevier, vol. 122(C).
    15. Li, Shuguang, 2017. "Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan," European Journal of Operational Research, Elsevier, vol. 260(1), pages 12-20.
    16. Lin, B.M.T. & Cheng, T.C.E. & Chou, A.S.C., 2007. "Scheduling in an assembly-type production chain with batch transfer," Omega, Elsevier, vol. 35(2), pages 143-151, April.
    17. Lixin Tang & Feng Li & Jiyin Liu, 2015. "Integrated scheduling of loading and transportation with tractors and semitrailers separated," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(5), pages 416-433, August.
    18. Jing Fan & Hui Shi, 2021. "A three-stage supply chain scheduling problem based on the nursing assistants’ daily work in a hospital," Journal of Combinatorial Optimization, Springer, vol. 42(4), pages 896-908, November.
    19. Damodaran, Purushothaman & Kumar Manjeshwar, Praveen & Srihari, Krishnaswami, 2006. "Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms," International Journal of Production Economics, Elsevier, vol. 103(2), pages 882-891, October.
    20. Stanisław Gawiejnowicz, 2020. "A review of four decades of time-dependent scheduling: main results, new topics, and open problems," Journal of Scheduling, Springer, vol. 23(1), pages 3-47, February.

    More about this item

    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:wly:navres:v:61:y:2014:i:4:p:269-285. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.