IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v123y2010i1p179-186.html
   My bibliography  Save this article

Scheduling on identical machines with batch arrivals

Author

Listed:
  • Chung, Tsui-Ping
  • Liao, Ching-Jong
  • Su, Ling-Huey

Abstract

In the scheduling literature, it is often assumed that jobs arrive either simultaneously or individually. However, this assumption is invalid in most practical situations because jobs usually arrive in batches, e.g., the final testing house in the manufacturing of semiconductor. The concept of batch arrivals has been mentioned in some studies, but it has not been explored from an operational viewpoint. This paper first addresses an identical parallel machine problem with batch arrivals to minimize the total completion time. Since the problem is NP-hard, a heuristic based on binary integer program is proposed. Computational results show that the proposed heuristic can efficiently obtain good solutions for medium and large size problems with an average percentage error of 2.12 from the lower bound.

Suggested Citation

  • Chung, Tsui-Ping & Liao, Ching-Jong & Su, Ling-Huey, 2010. "Scheduling on identical machines with batch arrivals," International Journal of Production Economics, Elsevier, vol. 123(1), pages 179-186, January.
    • Handle: RePEc:eee:proeco:v:123:y:2010:i:1:p:179-186
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925-5273(09)00278-3
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. R. Nessah & Farouk Yalaoui & C. Chu, 2008. "A branch and bound algorithm to minimize total weighted completion time on identical parallel machines with job release date," Post-Print hal-00580602, HAL.
    2. Wang, Xiuli & Cheng, T.C.E., 2009. "Heuristics for parallel-machine scheduling with job class setups and delivery to multiple customers," International Journal of Production Economics, Elsevier, vol. 119(1), pages 199-206, May.
    3. Nicholas G. Hall & Chris N. Potts, 2003. "Supply chain scheduling: Batching and delivery," Operations Research, INFORMS, vol. 51(4), pages 566-584, August.
    4. Azizoglu, Meral & Kirca, Omer, 1999. "On the minimization of total weighted flow time with identical and uniform parallel machines," European Journal of Operational Research, Elsevier, vol. 113(1), pages 91-100, February.
    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. 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.

    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. Xiangtong Qi, 2005. "A logistics scheduling model: Inventory cost reduction by batching," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 312-320, June.
    2. Rabia Nessah & Chengbin Chu, 2010. "Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods," Annals of Operations Research, Springer, vol. 181(1), pages 359-375, December.
    3. Berghman, Lotte & Leus, Roel, 2015. "Practical solutions for a dock assignment problem with trailer transportation," European Journal of Operational Research, Elsevier, vol. 246(3), pages 787-799.
    4. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    5. Kerem Bülbül & Halil Şen, 2017. "An exact extended formulation for the unrelated parallel machine total weighted completion time problem," Journal of Scheduling, Springer, vol. 20(4), pages 373-389, August.
    6. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    7. Yalaoui, F. & Chu, C., 2006. "New exact method to solve the Pm/rj/[summation operator]Cj schedule problem," International Journal of Production Economics, Elsevier, vol. 100(1), pages 168-179, March.
    8. 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.
    9. Sun Lee, Ik & Yoon, S.H., 2010. "Coordinated scheduling of production and delivery stages with stage-dependent inventory holding costs," Omega, Elsevier, vol. 38(6), pages 509-521, December.
    10. 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.
    11. 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.
    12. Dunstall, Simon & Wirth, Andrew, 2005. "A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines," European Journal of Operational Research, Elsevier, vol. 167(2), pages 283-296, December.
    13. Kramer, Arthur & Dell’Amico, Mauro & Iori, Manuel, 2019. "Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines," European Journal of Operational Research, Elsevier, vol. 275(1), pages 67-79.
    14. Yeung, Wing-Kwan & Choi, Tsan-Ming & Cheng, T.C.E., 2011. "Supply chain scheduling and coordination with dual delivery modes and inventory storage cost," International Journal of Production Economics, Elsevier, vol. 132(2), pages 223-229, August.
    15. 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.
    16. 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.
    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. Daniel Kowalczyk & Roel Leus, 2018. "A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 768-782, November.
    19. 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.
    20. George Steiner & Rui Zhang, 2011. "Revised Delivery-Time Quotation in Scheduling with Tardiness Penalties," Operations Research, INFORMS, vol. 59(6), pages 1504-1511, December.

    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:eee:proeco:v:123:y:2010:i:1:p:179-186. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    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.