Many classical synchronization problems such as the assembly line crew scheduling problem (ALCS), some data association problems or multisensor tracking problems can be formulated as finding intra-column rearrangements for a single matrix representing costs, distances, similarities or time requirements. In this paper, we consider an extension of these problems to the case of multiple matrices, reflecting various possible instances (scenarios). To approximate optimal rearrangements, we introduce the Block Swapping Algorithm (BSA) and a further customization of it that we call the customized Block Swapping Algorithm (Cust BSA). A numerical study shows that the two algorithms we propose – in particular Cust BSA – yield high-quality solutions and also deal efficiently with high-dimensional set-ups.

On some synchronization problems with multiple instances / D. Cornilly, G. Puccetti, L. Ruschendorf, S. Vanduffel. - In: JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS. - ISSN 0377-0427. - 400(2022), pp. 113697.1-113697.15. [10.1016/j.cam.2021.113697]

On some synchronization problems with multiple instances

G. Puccetti;
2022

Abstract

Many classical synchronization problems such as the assembly line crew scheduling problem (ALCS), some data association problems or multisensor tracking problems can be formulated as finding intra-column rearrangements for a single matrix representing costs, distances, similarities or time requirements. In this paper, we consider an extension of these problems to the case of multiple matrices, reflecting various possible instances (scenarios). To approximate optimal rearrangements, we introduce the Block Swapping Algorithm (BSA) and a further customization of it that we call the customized Block Swapping Algorithm (Cust BSA). A numerical study shows that the two algorithms we propose – in particular Cust BSA – yield high-quality solutions and also deal efficiently with high-dimensional set-ups.
Assembly line crew scheduling (ALCS); Multidimensional assignment problems; Rearrangement algorithm; Swapping algorithm
Settore SECS-S/06 - Metodi mat. dell'economia e Scienze Attuariali e Finanziarie
Settore MAT/06 - Probabilita' e Statistica Matematica
Article (author)
File in questo prodotto:
File Dimensione Formato  
cprv22.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 718.96 kB
Formato Adobe PDF
718.96 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
SSRN-id3681186.pdf

accesso aperto

Descrizione: Preprint liberamente distribuibile
Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 734.62 kB
Formato Adobe PDF
734.62 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/863130
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact