A two-phase heuristic algorithm for the label printing problem

Emre Çankaya, Ali Ekici () and Okan Örsan Özener
Additional contact information
Emre Çankaya: Ozyegin University
Ali Ekici: Ozyegin University
Okan Örsan Özener: Ozyegin University

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2023, vol. 31, issue 1, No 4, 110-138

Abstract: Abstract 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.

Keywords: Label printing problem; Construct-improve heuristic; Set covering; Mixed-integer linear model; 90C11; 90B35; 90C59 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-022-00624-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:31:y:2023:i:1:d:10.1007_s11750-022-00624-6

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-022-00624-6

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().