• Libraries
    • Log in to:
    View Item 
    •   MSpace Home
    • Faculty of Graduate Studies (Electronic Theses and Practica)
    • FGS - Electronic Theses and Practica
    • View Item
    •   MSpace Home
    • Faculty of Graduate Studies (Electronic Theses and Practica)
    • FGS - Electronic Theses and Practica
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Applications and extensions of the bin packing problem

    Thumbnail
    View/Open
    Master Thesis - Applications and Extensions of the Bin Packing Problem (754.8Kb)
    Date
    2021-08
    Author
    Nikbakht, Pooya
    Metadata
    Show full item record
    Abstract
    Bin packing is a classic optimization problem with many applications and variants. In its basic form, the goal is to pack items of different sizes in the range (0,1] into the minimum number of unit capacity bins. In doing so, an "offline" algorithm has access to all items before packing them, while an "online" algorithm receives items one by one and places each item into a bin without any knowledge about the forthcoming items. In this thesis, we study two variants of bin packing: square packing, and fault-tolerant bin packing. Our goal is to design the algorithms that work well under the worst-case scenarios, where algorithms are evaluated based on the approximation factor (in offline setting), and competitive ratio (in online setting). In the "square packing problem", items are squares of various side lengths, and bins are unit squares. We study this problem in both offline and online settings. Unlike previous work, we allow an algorithm to rotate items by any degree. This modification is consistent with the applications of square packing in stock cutting. We prove that the offline problem is NP-Hard and provide an asymptotic polynomial-time approximation scheme (APTAS) under an augmented resource setting. For the online setting, we present an online algorithm with a competitive ratio of at most 2.306. We also introduce an online algorithm with a competitive ratio of at most 1.897 for a related problem where the goal is to pack "tans" (half-square triangles) into unit squares. In the "fault-tolerant bin packing problem", items represent replicas of tenants, and bins are uniform capacity servers. As servers fail regularly, a valid packing should tolerate the failure of a certain number of bins. Applications of this problem are online as tenant hosting requests are made sequentially. The best existing online algorithm has a competitive ratio of at most 2, which works in a setting where bins fail only after packing process is concluded. We study a more practical setting where the bin failures might happen during the packing process, and introduce an algorithm with an improved competitive ratio of at most 1.75 for this general setting.
    URI
    http://hdl.handle.net/1993/36164
    Collections
    • FGS - Electronic Theses and Practica [25522]

    Related items

    Showing items related by title, author, creator and subject.

    • Social welfare services and problem drinking : a comparative study of the use of social welfare services by problem drinking families and non-problem drinking families known to the main family agencies in the City of Winnipeg in September, 1962 

      Allard, T. S. (1963)
      This study took place in Winnipeg, Manitoba between October, 1962 and May, 1963, and was focused on the use of services by families active with one or more of the five main family agencies in this city, for the purpose of ...
    • Postpartum depression : the process of clinical inquiry into the health problem and clinical problem-solving for community health nurses 

      Brett, Janet L. (1987)
    • Shifting attentions in mathematics: developing problem solving abilities through problem-solving groups 

      McIntosh, Blaine (2011-08-12)
      The purpose of this study was to improve problem solving attitudes and abilities in students of mathematics through the exploration of John Mason’s general problem solving strategy and the use of problem solving groups, ...

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of MSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Login

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV