DIPARTIMENTO DI MATEMATICA PURA E
APPLICATA
Università degli Studi di L'Aquila
22 Febbraio 2001
Algoritmi di Ottimizzazione Discreta e Applicazioni
Aula 1.7 Coppito 1
Programma:
10.00 Claudio Arbib, Università di L'Aquila
INTRODUZIONE AL WORKSHOP
10.15 Arianna Alfieri, Politecnico di Torino
METODI
DI GENERAZIONE DI COLONNE PER LA SCHEDULAZIONE IN AMBITO FERROVIARIO
10.45 Gaia Nicosia, Università di Roma Tre
OTTIMIZZAZIONE MULTICRITERIO ON-LINE
11.15 Fabrizio Marinelli, Università di L'Aquila
UN
SISTEMA DI CONTROLLO DELLA MOVIMENTAZIONE DI SEMILAVORATI IN UNA CELLA
MANIFATTURIERA FLESSIBILE
11.45 Paolo Detti, Università di Siena
SCHEDULAZIONE
DI MACCHINE DI TAGLIO IN UN'INDUSTRIA DI ABBIGLIAMENTO
12.15 Gianfranco Ciaschetti, Università di
L'Aquila
IL PROBLEMA DEGLI STAMPI: UN APPROCCIO CON GENERAZIONE
DI COLONNE
15.00 Carlo Meloni, Università di Roma Tre
UN
ALGORITMO GENETICO PER IL PROBLEMA DI COORDINAMENTO DELLA SEQUENZA TRA 2 STADI
DI UN SISTEMA DI PRODUZIONE
15.30 Renato Bruni, Università di Roma "La Sapienza"
LOGICA ED OTTIMIZZAZIONE PER INDIVIDUAZIONE E CORREZIONE DI ERRORI
IN GRANDI MOLI DI DATI
16.00 Marco Pranzo, Università di Roma Tre
SEQUENZIAMENTO DELLE OPERAZIONI NEI SISTEMI MANIFATTURIERI
16.30 Nicola Apollonio, Università di Roma "La Sapienza"
UN ALGORITMO GHIOTTO CON PROGNOSI PER UN PROBLEMA DI COPERTURA DI
CAMMINI PER SPIGOLI
Abstract
Metodi di Generazione di Colonne per la Schedulazione in Ambito
Ferroviario
Il caso dei
macchinisti olandesi
Arianna Alfieri
Dipartimento di Sistemi di Produzione ed
Economia dell'Azienda
Politecnico di Torino
aalfieri@athena.polito.it
La schedulazione dei macchinisti ferroviari riguarda la costruzione di un insieme di turni di lavoro (sequenze di viaggi tra stazioni diverse), a costo minimo, da assegnare ai macchinisti. L'ammissibilità di un turno di lavoro è vincolata da diverse regole. Assumendo di avere a disposizione tutti i turni ammissibili, è immediato formulare il problema come un problema di set-covering ma, nonostante la semplicità di questo modello, la presenza delle regole (vincoli) sopra citate può rendere difficile anche la semplice costruzione di una soluzione ammissibile. La possibilità di modellare un problema applicativo in termini di set-covering rende naturale la ricerca di procedure di soluzione basate sulla generazione di colonne. Il nostro primo approccio è stato quello di tentare la generazione esplicita delle colonne, più semplice da un punto di vista teorico e di implementazione. Ma l'enorme numero di colonne ammissibili rende praticamente impossibile (per i tempi di calcolo coinvolti) raggiungere la soluzione ottima. I difetti di questo approccio hanno quindi indirizzato lo studio verso un metodo di generazione implicita, del quale verranno presentati gli aspetti più rilevanti.
Ottimizzazione Multicriterio On-Line
Michele Flammini
Dipartimento di Matematica Pura
e Applicata
Università degli Studi di L'Aquila
flammini@univaq.it
Gaia Nicosia
Dipartimento di Informatica e
Automazione
Università di Roma Tre
nicosia@dia.uniroma3.it
In questo lavoro vengono affrontati problemi di ottimizzazione
bicriterio. In particolare viene proposto un metodo per valutare la qualità
degli algoritmi on-line attraverso l'utilizzo di alcune funzioni, dette funzioni
di selezione, che permettono di individuare una soluzione off-line Pareto ottima
con cui confrontarsi.
In questo contesto si affronta il problema del
$k$-server, in cui sono dati un grafo $G$ con due diversi pesi sugli archi, e
$k$ serventi che devono spostarsi sui nodi di $G$. Ad ogni istante viene
"richiesto" un nodo e uno dei serventi deve immediatamente essere spostato su
questo nodo. L'obiettivo è di minimizzare la distanza totale percorsa dai
serventi rispetto ad entrambe le pesature degli archi. Per questo problema viene
proposto ed analizzato un algoritmo universale che può essere applicato anche ad
altri problemi multicriterio con caratteristiche simili. Viene inoltre
effettuata un'analisi dettagliata delle proprietà di diverse funzioni di
selezione.
Un Sistema di Controllo Della Movimentazione di Semilavorati in una Cella Manifatturiera Flessibile
Fabrizio Marinelli
Dipartimento di Matematica Pura e
Applicata
Università degli Studi di L'Aquila
marinell@univaq.it
We consider the problem of moving parts in a manufacturing system devoted to the production of aluminium profiles. Among the process steps, we focus the attention on the heating treatment. It is carried out in a flexible manufacturing cell composed by 4 electrical ovens and a bridge crane as material handling device. Different part types incoming in the cell must be consolidated, i.e. partitioned according to similar characteristics, before being sent to the ovens. Moreover, the intermediate buffers in the plant are all served by the bridge crane. So, the material handling device is critical in terms of both throughput and robustness and it is desirable to limit the number and duration of its operations to a minimum. An on-line algorithm has been designed, implemented and tested to control the bridge crane movements in order to fulfill a given transportation demand with a minimum number of missions. The actual utilization and a simulation study show the benefits of the algorithm.
Scheduling Cutting Machines in a Clothing Industry
Paolo Detti
Dipartimento di Ingegneria
dell'Informazione
Università degli Studi di Siena
detti@dii.unisi.it
In a clothing industry, clothes are produced by assembling fabric cutouts. Fabric rolls on a line, and is cut by automated machines arranged along the line. A fabric cutout $f_j$, requiring a cutting time $p_j$, is available for cutting on the first machine at a release date $r_{1j}$, and must be completed, on the same machine, within a dead line $d_{1j}$. On machine $i$, $i= 2,\ldots,m$, release dates and dead lines related to the cutout $f_j$ are respectively $r_{ij}= r_{1j}+\Delta (i-1)$ and $d_{ij}= d_{1j}+\Delta (i-1)$, where $\Delta$ is a constant factor depending on the speed rate of the fabric. A set--up time occurs on a machine when switching from one cutout to another. At the beginning of the production period the number of the cutouts and their spatial configuration on the fabric are not available. The problem of on--line assigning and scheduling cutouts to the cutting machines is addressed. An off--line approach is also proposed.
The Moulding Problem: a Column Generation Approach
Gianfranco Ciaschetti
Dipartimento di Matematica Pura e
Applicata
Università degli Studi di L'Aquila
ciasc@univaq.it
In plastic printing industries interesting and peculiar scheduling problems with sequence dependent set--up times arise: namely, there's the need to assign jobs to moulds and machines in order to optimise with respect to a given objective function, such as makespan, lateness or number of tardy jobs. Each job is a batch of similar parts to be produced until a fixed due--date, and it can be splitted in more parts or pre-empted depending upon the particular scheduling constraints. Only a subset of the available moulds are "compatible" with each job, and the choice of the mould determines the processing time of that job. More precisely, the parallel compressor machines all have the same shot frequency (and each mould $k$ has a given capacity $C_k$ representing the number of similar parts produced per machine shot. There is a major set--up when a new mould has to be mounted onto a machine, and a minor set--up when a new job is going to be produced with the same mould. In this work, we develop a column generation algorithm for the $P, | s_k, s_{ij}, p_{jk} | \sum{U_j}$ problem, where $k$ stands for mould index, $i$ and $j$ for job index, $s_k$ and $s_{ij}$ for major and minor set--ups respectively, and $U_j$ is the tardiness characteristic function of job $j$. The column generation procedure is based on a set--partitioning formulation with time--windows, and gives raise to reasonably good solutions for real big instances (up to thousands of jobs and hundreds of mouds). Computational results show the comparison between this approach and other classical approaches such as decomposition and PLI algorithms based on compact formulations.
A Genetic Algorithm for the Sequence Coordination Problem Between Two--Stage of a Production System
Carlo Meloni
Dipartimento di Informatica e
Automazione
Università Roma Tre
meloni@dia.uniroma3.it
In this talk we deal with the coordination issues in
multi--stage production systems and supply chains.
Supply chain management is
a relevant topic in logistics and operations management research, even though
the \emph{scheduling} of a supply chain did not yet receive the same attention
so far.
At the operational level, a number of interesting coordination
problems exists, which have not yet been effectively modeled. These problems
concern the way in which two consecutive stages should organize their internal
work taking into account the requirements of the other stage. A central problem
of operations management for multi--stage production systems is to decide how to
sequence different parts which have to be processed in each stage, and what
tools and materials to allocate to each stage in order to minimize the overall
number of setups.
Mainly, the focus of this talk is on the sequence
coordination problem in a two--stage production system. An example arising in a
real production system is presented, and a graph theoretical model for the
problem is proposed. The model lead to a more general problem on graphs, i.e.
theminimum dominating trail set problem (MDTS problem). This problem may be
stated as follows:given a graph $G= (V,E)$, find a minimum cardinality
collection $\Sigma$ of trails that altogheter dominates the edges of the graph,
i.e. every edge $e \in E$ has at least one endpoint on some trail (path) of
$\Sigma$.
Theoretical bounds for the problem
are proposed. A heuristic approach based on a genetic algorithm scheme is
proposed. A special genetic representation of the problem is considered, and a
set of genetic operators is proposed. The computational experiments concern a
wide set of instances (and also consider real industrial data) and provide a way
for an evaluation of the proposed heuristic.
Logica ed Ottimizzazione per Individuazione e Correzione Di Errori in Grandi Moli di Dati
Renato Bruni
Dipartimento di Informatica e
Sistemistica
Università di Roma "La Sapienza"
bruni@dis.uniroma1.it
In tutti i casi in cui occorra trattare una grande mole di dati, sorge il problema di considerare solo dati non affetti da errori. Per individuare automaticamente record di dati inconsistenti o fuori range, vengono allora utilizzate delle regole (vincoli di integrità, edit) con le quali passare al vaglio i dati grezzi. Tale metodologia è estremamente diffusa in campo statistico o nel campo delle basi di dati. Sorgono però problemi di inconsistenza e ridondanza nell'insieme stesso delle regole. Tali problemi possono essere ricondotti a problemi di Soddisfacibilità di formule logiche proposizionali ed efficientemente risolti. Una volta validato, l'insieme delle regole serve per individuare i dati errati. Se, come generalmente avviene, la raccolta dati ha un costo, occorre procedere alla correzione degli errori. Tali problemi possono essere ricondotti a problemi di Set Covering ed efficientemente risolti. L'utilizzo di dette formulazioni presenta notevoli vantaggi rispetto ad altri metodi esistenti.
Sequenziamento delle Operazioni nei Sistemi Manifatturieri
Marco Pranzo
Dipartimento di Informatica e
Automazione
Università di Roma Tre
mpranzo@dia.uniroma3.it
In questa presentazione descriveremo una metodologia generale
per affrontare problemi di scheduling con vincoli di {\em blocking} e di {\em
no-wait}.
Nel contesto manifatturiero il vincolo di {\em blocking}
rappresenta risorse a capacità unitaria, permettendo di modellare buffer con
capacità limitata tra le macchine. Mentre il vincolo di {\em no-wait} permette
di rappresentare la situazione in cui due o più lavorazioni consecutive diun job
siano da effettuare senza attese.
Il problema verrà rappresentato per mezzo
delGrafo delle Alternative, $G= (V,C,A)$, in cui $V$ è l'insieme composto dai
nodi del grafo, $C$ è un insieme di archi {\em congiuntivi} orientati e pesati e
$A$ è un insieme di coppie di archi {\em alternativi}. Una selezione $S$ è un
insieme di archi ottenuto scegliendo esattamente un arco per ogni coppia di $A$.
La selezione è ammissibile se il grafo risultante $G= (V,C \cup S)$ è privo di
cicli positivi. Questo modello generalizza il noto Grafo Disgiuntivo di Roy e
Sussman.
La metodologia verrà applicata in particolare ad un problema
manifatturiero estremamente vincolato come lo scheduling di una linea di
produzione dell'acciaio. Esamineremo in particolare la Linea Inox delle
acciaierie di Terni. La produzione avviene a lotti e ogni lotto è composto da un
certo numero di siviere, che devono ricevere una serie di lavorazioni (fusione
delle materie prime, raffinamento del fuso e colatura in semilavorati).
La
linea in questione è modellabile come un flow shop con buffer a capacità
limitata tra le macchine, con vincoli di deperimento nei buffer e con un vincolo
di lavorazione senza interruzioni sulla macchina di colatura continua.
Infine
verranno presentati i risultati, ottenuti con degli algoritmi euristici sul
grafo delle alternative e verificati su un simulatore dettagliato. I risultati
così ottenuti sono stati confrontati con le sequenze calcolate manualmente,
risultando paragonabili sul piano della robustezza e decisamente migliori per
quanto riguarda i tempi di calcolo ed il makespan complessivo.
Futuri sviluppi
riguardano l'implementazione di un sistema integrato in grado di modellare
tramite il grafo delle alternative problemi di scheduling in tempo reale
fortemente vincolati e lo sviluppo di efficaci algoritmi di ricerca locale,
quali Tabu Search o altre metaeuristiche.
Un Algoritmo Ghiotto con Prognosi per un Problema di Copertura di Cammini per Spigoli.
Nicola Apollonio
Dipartimento di Probabilità, Statistica e
Statistiche Applicate
Università di Roma "La Sapienza"
apolloni@rosd.sta.uniroma1.it
Dato un grafo $G$, un intero $t$ non superiore al numero degli spigoli di $G$, una famiglia $\Theta(G)$ di cammini elementari su $G$ (riguardati come sottoinsiemi di linee di $G$) ed una funzione di peso $w:\Theta(G)\to \nabla_+$, siamo interessati a determinare un sottoinsieme di non più di $t$ spigoli che collettivamente siano attraversati da un insieme di cammini di peso complessivamente massimo. Tale problema può riscriversi come quello di massimizzare una funzione submodulare definita sull'insieme degli spigoli di $G$ e soggetta ad un vincolo di cardinalità: come è noto, in questo caso l'algoritmo ghiotto risulta 0.63-approssimato. In questo lavoro presenteremo una procedura alternativa all'algoritmo ghiotto e discuteremo le sue prestazioni nel caso peggiore. Saranno inoltre presentati alcuni risultati sperimentali preliminari.