Author
Çankaya, Emre, Ekici, Ali, Özener, Okan Örsan
Publication Date
2023-04
Publication Place
-
Springer
Subject
Label printing problem, Construct-improve heuristic, Set covering, Mixed-integer linear model
Type
Periodical
Language
English
Digital
Yes
Manuscript
No
Library
Özyeğin University
Library Asset ID
1134-5764
Record ID
a04b31bb-c2e8-4c5c-a396-263c3642aef6
Library Location
Industrial Engineering
Date
2023-04
Sample Text
In this paper, we study the label printing problem (LPP) which has applications in the printing industry. In LPP, the demand for a set of labels is satisfied by printing the labels using templates with multiple slots. Given a fixed number of templates, the decisions in LPP are determining (i) the assignment of labels to the slots of the templates (which we call template designs), and (ii) the number of prints made using each template design. The objective is to satisfy the demand with minimum waste. We consider two variants of LPP where (i) each label can be assigned to the slot(s) of a single template, and (ii) each label can be assigned to the slot(s) of multiple templates. To address LPP, we propose a novel sampling-based construct-improve heuristic where we first generate "good" template designs and then choose the ones to be used and determine the number of prints made through a set covering-type mathematical model. Then, we improve the solution using some improvement ideas that utilize a strengthened linear integer model for the problem. Using the instances from the literature, we show that the proposed heuristic provides better results compared to the benchmark algorithm. We also find optimal solutions for some of the instances from the literature using the strengthened linear integer model. With the help of the optimal solutions found we identify some problems in the previously reported results in a related study. Finally, we observe that the proposed heuristic approach not only provides better solutions but also runs in less amount of time compared to the benchmark algorithm on the large instances.
DOI
10.1007/s11750-022-00624-6
Cilt
31
