IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v181y2010i1p443-46210.1007-s10479-010-0757-3.html
   My bibliography  Save this article

Solving the Rectangular assignment problem and applications

Author

Listed:

Abstract

The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k-cardinality LAP and the LAP with outsourcing by transformation. We introduce a transformation to solve the machine replacement LAP. We describe improvements of a LAP-algorithm for the rectangular problem, in general and slightly adapted for these variants, based on the structure of the corresponding cost matrices. For these problem instances, we compared the best special codes from literature to our codes, which are more general and easier to implement. The improvements lead to more efficient and robust codes, making them competitive on all problem instances and often showing much shorter computing times. Copyright The Author(s) 2010

Suggested Citation

  • J. Bijsterbosch & A. Volgenant, 2010. "Solving the Rectangular assignment problem and applications," Annals of Operations Research, Springer, vol. 181(1), pages 443-462, December.
    • Handle: RePEc:spr:annopr:v:181:y:2010:i:1:p:443-462:10.1007/s10479-010-0757-3
    DOI: 10.1007/s10479-010-0757-3
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-010-0757-3
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-010-0757-3?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. Robert E. Machol & Michael Wien, 1976. "Technical Note—A “Hard” Assignment Problem," Operations Research, INFORMS, vol. 24(1), pages 190-192, February.
    2. Mosheiov, Gur & Yovel, Uri, 2006. "Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs," European Journal of Operational Research, Elsevier, vol. 172(2), pages 528-544, July.
    3. Volgenant, A., 2004. "Solving the k-cardinality assignment problem by transformation," European Journal of Operational Research, Elsevier, vol. 157(2), pages 322-331, September.
    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. Yuli Zhang & Zuo-Jun Max Shen & Shiji Song, 2018. "Exact Algorithms for Distributionally β -Robust Machine Scheduling with Uncertain Processing Times," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 662-676, November.

    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. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    2. Huynh Tuong, Nguyen & Soukhal, Ameur, 2010. "Due dates assignment and JIT scheduling with equal-size jobs," European Journal of Operational Research, Elsevier, vol. 205(2), pages 280-289, September.
    3. Amnon Rosenmann, 2022. "Computing the sequence of k-cardinality assignments," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1265-1283, September.
    4. Gerstl, Enrique & Mosheiov, Gur, 2013. "Due-window assignment with identical jobs on parallel uniform machines," European Journal of Operational Research, Elsevier, vol. 229(1), pages 41-47.
    5. Shabtay, Dvir & Steiner, George & Zhang, Rui, 2016. "Optimal coordination of resource allocation, due date assignment and scheduling decisions," Omega, Elsevier, vol. 65(C), pages 41-54.
    6. Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.
    7. G Mosheiov & A Sarig, 2011. "A note: a due-window assignment problem on parallel identical machines," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 238-241, January.
    8. Sang, Yao-Wen & Wang, Jun-Qiang & Sterna, Małgorzata & Błażewicz, Jacek, 2023. "Single machine scheduling with due date assignment to minimize the total weighted lead time penalty and late work," Omega, Elsevier, vol. 121(C).
    9. Oron, Daniel & Shabtay, Dvir & Steiner, George, 2015. "Single machine scheduling with two competing agents and equal job processing times," European Journal of Operational Research, Elsevier, vol. 244(1), pages 86-99.
    10. Oğuzhan Ahmet Arik, 2023. "A heuristic for single machine common due date assignment problem with different earliness/tardiness weights," OPSEARCH, Springer;Operational Research Society of India, vol. 60(3), pages 1561-1574, September.
    11. Shabtay, Dvir, 2016. "Optimal restricted due date assignment in scheduling," European Journal of Operational Research, Elsevier, vol. 252(1), pages 79-89.
    12. Zhijun Xu & Dehua Xu, 2018. "Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time," Journal of Scheduling, Springer, vol. 21(4), pages 461-482, August.
    13. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.

    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:spr:annopr:v:181:y:2010:i:1:p:443-462:10.1007/s10479-010-0757-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.