IDEAS home Printed from https://ideas.repec.org/a/taf/tprsxx/v54y2016i22p6718-6735.html
   My bibliography  Save this article

Lagrangean relaxation approach to joint optimization for production planning and scheduling of synchronous assembly lines

Author

Listed:
  • Yu-Wei An
  • Hong-Sen Yan

Abstract

This paper focuses on simultaneous optimisation of production planning and scheduling problem over a time period for synchronous assembly lines. Differing from traditional top-down approaches, a mixed integer programming model which jointly considers production planning and detailed scheduling constraints is formulated, and a Lagrangian relaxation method is developed for the proposed model, whereby the integrated problem is decomposed into planning, batch sequencing, tardiness and earliness sub-problems. The scheduling sub-problem is modelled as a time-dependent travelling salesman problem, which is solved using a dynasearch algorithm. A proposition of Lagrangian multipliers is established to accelerate the convergence speed of the proposed algorithm. The average direction strategy is employed to solve the Lagrangian dual problem. Test results demonstrate that the proposed model and algorithm are effective and efficient.

Suggested Citation

  • Yu-Wei An & Hong-Sen Yan, 2016. "Lagrangean relaxation approach to joint optimization for production planning and scheduling of synchronous assembly lines," International Journal of Production Research, Taylor & Francis Journals, vol. 54(22), pages 6718-6735, November.
    • Handle: RePEc:taf:tprsxx:v:54:y:2016:i:22:p:6718-6735
    DOI: 10.1080/00207543.2016.1157271
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2016.1157271
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/00207543.2016.1157271?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. Marshall L. Fisher, 1981. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 27(1), pages 1-18, January.
    2. Laporte, Gilbert, 1992. "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(2), pages 231-247, June.
    3. Richard K. Congram & Chris N. Potts & Steef L. van de Velde, 2002. "An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 14(1), pages 52-67, February.
    4. Alexandre Dolgui & Anton Eremeev & Mikhail Kovalyov & Pavel Kuznetsov, 2010. "Multi-product lot sizing and scheduling on unrelated parallel machines," IISE Transactions, Taylor & Francis Journals, vol. 42(7), pages 514-524.
    5. Rong, Aiying & Lahdelma, Risto & Luh, Peter B., 2008. "Lagrangian relaxation based algorithm for trigeneration planning with storages," European Journal of Operational Research, Elsevier, vol. 188(1), pages 240-257, July.
    6. Angel, E. & Bampis, E., 2005. "A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem," European Journal of Operational Research, Elsevier, vol. 162(1), pages 281-289, April.
    7. X. Zhao & P. B. Luh & J. Wang, 1999. "Surrogate Gradient Algorithm for Lagrangian Relaxation," Journal of Optimization Theory and Applications, Springer, vol. 100(3), pages 699-712, March.
    8. J. B. Lasserre, 1992. "An Integrated Model for Job-Shop Planning and Scheduling," Management Science, INFORMS, vol. 38(8), pages 1201-1211, August.
    9. Gondzio, J. & Sarkissian, R. & Vial, J.-P., 1997. "Using an interior point method for the master problem in a decomposition approach," European Journal of Operational Research, Elsevier, vol. 101(3), pages 577-587, September.
    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. Arianna Alfieri & Shuyu Zhou & Rosario Scatamacchia & Steef L. van de Velde, 2021. "Dynamic programming algorithms and Lagrangian lower bounds for a discrete lot streaming problem in a two-machine flow shop," 4OR, Springer, vol. 19(2), pages 265-288, June.
    2. Lorena, Luiz Antonio N. & Goncalves Narciso, Marcelo, 2002. "Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems," European Journal of Operational Research, Elsevier, vol. 138(3), pages 473-483, May.
    3. X.H. Guan & Q.Z. Zhai & F. Lai, 2002. "New Lagrangian Relaxation Based Algorithm for Resource Scheduling with Homogeneous Subproblems," Journal of Optimization Theory and Applications, Springer, vol. 113(1), pages 65-82, April.
    4. Lixin Tang & Gongshu Wang & Jiyin Liu & Jingyi Liu, 2011. "A combination of Lagrangian relaxation and column generation for order batching in steelmaking and continuous‐casting production," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(4), pages 370-388, June.
    5. Wang, Tingsong & Xing, Zheng & Hu, Hongtao & Qu, Xiaobo, 2019. "Overbooking and delivery-delay-allowed strategies for container slot allocation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 433-447.
    6. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    7. M Diaby & A L Nsakanda, 2006. "Large-scale capacitated part-routing in the presence of process and routing flexibilities and setup costs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(9), pages 1100-1112, September.
    8. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    9. Mutsunori Yagiura & Toshihide Ibaraki & Fred Glover, 2004. "An Ejection Chain Approach for the Generalized Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 133-151, May.
    10. Wang, Jiangjiang & Zhai, Zhiqiang (John) & Jing, Youyin & Zhang, Chunfa, 2010. "Optimization design of BCHP system to maximize to save energy and reduce environmental impact," Energy, Elsevier, vol. 35(8), pages 3388-3398.
    11. Rong, Aiying & Lahdelma, Risto, 2017. "An efficient model and algorithm for the transmission-constrained multi-site combined heat and power system," European Journal of Operational Research, Elsevier, vol. 258(3), pages 1106-1117.
    12. S Bilgin & M Azizoǧlu, 2006. "Capacity and tool allocation problem in flexible manufacturing systems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(6), pages 670-681, June.
    13. Weijun Xie & Yanfeng Ouyang & Sze Chun Wong, 2016. "Reliable Location-Routing Design Under Probabilistic Facility Disruptions," Transportation Science, INFORMS, vol. 50(3), pages 1128-1138, August.
    14. Peter Francis & Karen Smilowitz & Michal Tzur, 2006. "The Period Vehicle Routing Problem with Service Choice," Transportation Science, INFORMS, vol. 40(4), pages 439-454, November.
    15. Park, Moon-Won & Kim, Yeong-Dae, 2000. "A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints," European Journal of Operational Research, Elsevier, vol. 123(3), pages 504-518, June.
    16. Shangyao Yan & Chun-Ying Chen & Chuan-Che Wu, 2012. "Solution methods for the taxi pooling problem," Transportation, Springer, vol. 39(3), pages 723-748, May.
    17. L Tang & H Xuan, 2006. "Lagrangian relaxation algorithms for real-time hybrid flowshop scheduling with finite intermediate buffers," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(3), pages 316-324, March.
    18. Jenny Carolina Saldana Cortés, 2011. "Programación semidefinida aplicada a problemas de cantidad económica de pedido," Documentos CEDE 8735, Universidad de los Andes, Facultad de Economía, CEDE.
    19. Niels Agatz & Paul Bouman & Marie Schmidt, 2018. "Optimization Approaches for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 52(4), pages 965-981, August.
    20. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).

    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:taf:tprsxx:v:54:y:2016:i:22:p:6718-6735. 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: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TPRS20 .

    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.