IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v191y2008i3p957-971.html
   My bibliography  Save this article

Soft car sequencing with colors: Lower bounds and optimality proofs

Author

Listed:
  • Benoist, Thierry

Abstract

This paper is a study of the car sequencing problem, when feature spacing constraints are soft and colors of vehicles are taken into account. Both pseudo-polynomial algorithms and lower bounds are presented for parts of the problem or family of instances. With this set of lower bounds, we establish the optimality (up to the first non-trivial criteria) of 54% of best known solutions for the benchmark used for the Roadef Challenge 2005. We also prove that the optimal penalty for a single ratio constraint N/P can be computed in O(P) and that determining the feasibility of a car sequencing instance limited to a pair of simple ratio constraints can be achieved by dynamic programming. Finally, we propose a solving algorithm exploiting these results within a local search approach. To achieve this goal, a new meta-heuristic (star relinking) is introduced, designed for the optimization of an aggregation of criteria, when the optimization of each single criterion is a polynomial problem.

Suggested Citation

  • Benoist, Thierry, 2008. "Soft car sequencing with colors: Lower bounds and optimality proofs," European Journal of Operational Research, Elsevier, vol. 191(3), pages 957-971, December.
    • Handle: RePEc:eee:ejores:v:191:y:2008:i:3:p:957-971
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00449-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. John J. Bartholdi & James B. Orlin & H. Donald Ratliff, 1980. "Cyclic Scheduling via Integer Programs with Circular Ones," Operations Research, INFORMS, vol. 28(5), pages 1074-1085, October.
    2. M Gravel & C Gagné & W L Price, 2005. "Review and comparison of three methods for the solution of the car sequencing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(11), pages 1287-1295, November.
    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. Golle, Uli & Rothlauf, Franz & Boysen, Nils, 2014. "Car sequencing versus mixed-model sequencing: A computational study," European Journal of Operational Research, Elsevier, vol. 237(1), pages 50-61.
    2. Eivind Jahren & Roberto Asín Achá, 2018. "A column generation approach and new bounds for the car sequencing problem," Annals of Operations Research, Springer, vol. 264(1), pages 193-211, May.
    3. Uli Golle & Franz Rothlauf & Nils Boysen, 2015. "Iterative beam search for car sequencing," Annals of Operations Research, Springer, vol. 226(1), pages 239-254, March.

    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. Aykin, Turgut, 2000. "A comparative evaluation of modeling approaches to the labor shift scheduling problem," European Journal of Operational Research, Elsevier, vol. 125(2), pages 381-397, September.
    2. Yuan Sun & Samuel Esler & Dhananjay Thiruvady & Andreas T. Ernst & Xiaodong Li & Kerri Morgan, 2024. "Instance space analysis for the car sequencing problem," Annals of Operations Research, Springer, vol. 341(1), pages 41-69, October.
    3. Boysen, Nils & Fliedner, Malte, 2007. "Comments on "Solving real car sequencing problems with ant colony optimization"," European Journal of Operational Research, Elsevier, vol. 182(1), pages 466-468, October.
    4. Elif Elcin Gunay & Ufuk Kula, 2017. "A stochastic programming model for resequencing buffer content optimisation in mixed-model assembly lines," International Journal of Production Research, Taylor & Francis Journals, vol. 55(10), pages 2897-2912, May.
    5. Michael J. Brusco & Larry W. Jacobs, 2000. "Optimal Models for Meal-Break and Start-Time Flexibility in Continuous Tour Scheduling," Management Science, INFORMS, vol. 46(12), pages 1630-1641, December.
    6. Elizabeth Baldwin & Paul Klemperer, 2019. "Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities," Econometrica, Econometric Society, vol. 87(3), pages 867-932, May.
    7. Joaquín Bautista & Jordi Pereira & Belarmino Adenso-Díaz, 2008. "A Beam Search approach for the optimization version of the Car Sequencing Problem," Annals of Operations Research, Springer, vol. 159(1), pages 233-244, March.
    8. Delorme, Xavier & Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y., 2019. "Minimizing the number of workers in a paced mixed-model assembly line," European Journal of Operational Research, Elsevier, vol. 272(1), pages 188-194.
    9. C Gagné & M Gravel & S Morin & W L Price, 2008. "Impact of the pheromone trail on the performance of ACO algorithms for solving the car-sequencing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1077-1090, August.
    10. Yann Ferrand & Michael Magazine & Uday S. Rao & Todd F. Glass, 2011. "Building Cyclic Schedules for Emergency Department Physicians," Interfaces, INFORMS, vol. 41(6), pages 521-533, December.
    11. Tristan Becker & Maximilian Schiffer & Grit Walther, 2022. "A General Branch-and-Cut Framework for Rotating Workforce Scheduling," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1548-1564, May.
    12. Michael J. Brusco & Larry W. Jacobs, 1998. "Personnel Tour Scheduling When Starting-Time Restrictions Are Present," Management Science, INFORMS, vol. 44(4), pages 534-547, April.
    13. Boysen, Nils & Fliedner, Malte & Scholl, Armin, 2009. "Sequencing mixed-model assembly lines: Survey, classification and model critique," European Journal of Operational Research, Elsevier, vol. 192(2), pages 349-373, January.
    14. Tristan Becker, 2020. "A decomposition heuristic for rotational workforce scheduling," Journal of Scheduling, Springer, vol. 23(5), pages 539-554, October.
    15. de Werra, D., 1996. "Extensions of coloring models for scheduling purposes," European Journal of Operational Research, Elsevier, vol. 92(3), pages 474-492, August.
    16. Bentz, Cédric & Costa, Marie-Christine & Létocart, Lucas & Roupin, Frédéric, 2009. "Multicuts and integral multiflows in rings," European Journal of Operational Research, Elsevier, vol. 196(3), pages 1251-1254, August.
    17. Uli Golle & Franz Rothlauf & Nils Boysen, 2015. "Iterative beam search for car sequencing," Annals of Operations Research, Springer, vol. 226(1), pages 239-254, March.
    18. Arjan Akkermans & Gerhard Post & Marc Uetz, 2021. "Solving the shift and break design problem using integer linear programming," Annals of Operations Research, Springer, vol. 302(2), pages 341-362, July.
    19. Solnon, Christine & Cung, Van Dat & Nguyen, Alain & Artigues, Christian, 2008. "The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF'2005 challenge problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 912-927, December.
    20. Legato, Pasquale & Monaco, M. Flavia, 2004. "Human resources management at a marine container terminal," European Journal of Operational Research, Elsevier, vol. 156(3), pages 769-781, August.

    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:eee:ejores:v:191:y:2008:i:3:p:957-971. 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/eor .

    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.