A two-phase heuristic algorithm for the label printing problem

Name: A two-phase heuristic algorithm for the label printing problem
Author: Çankaya, Emre, Ekici, Ali, Özener, Okan Örsan

İsim	A two-phase heuristic algorithm for the label printing problem
Yazar	Çankaya, Emre, Ekici, Ali, Özener, Okan Örsan
Basım Tarihi:	2023-04
Basım Yeri	- Springer
Konu	Label printing problem, Construct-improve heuristic, Set covering, Mixed-integer linear model
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	1134-5764
Kayıt Numarası	a04b31bb-c2e8-4c5c-a396-263c3642aef6
Lokasyon	Industrial Engineering
Tarih	2023-04
Örnek Metin	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

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

A two-phase heuristic algorithm for the label printing problem

Yazar Çankaya, Emre, Ekici, Ali, Özener, Okan Örsan

Basım Tarihi 2023-04

Basım Yeri - Springer

Konu Label printing problem, Construct-improve heuristic, Set covering, Mixed-integer linear model

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 1134-5764

Kayıt Numarası a04b31bb-c2e8-4c5c-a396-263c3642aef6

Lokasyon Industrial Engineering

Tarih 2023-04

Örnek Metin 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