Detta arbete undersöker Bicluster Graph Editing Problem (BGEP) och hur det kan tillämpas för att lösa Manufacturing Cell Formation Problem (MCFP). Vi utvecklar en exakt metod för BGEP som består av en Branch-and-Cut-strategi kombinerad med en speciell separationsalgoritm baserad på dynamisk programmering. Vi beskriver också ett nytt förbehandlingsförfarande för BGEP som härleds från teoretiska resultat på vertex avstånd i inmatningskurvan. Beräkningsexperiment som utförs på slumpmässigt genererade fall med olika svårighetsgrader visar att vår separationsalgoritm accelererar konvergenshastigheten, och vårt förbehandlingsförfarande är effektivt för fall med låg densitet. Andra bidrag till detta arbete är att avslöja likheterna mellan BGEP och MCFP. Vi visar att BGEP och MCFP har samma lösningsutrymme. Detta faktum leder till förslaget om två nya exakta metoder för MCFP baserade på matematiska formuleringar för BGEP. Båda metoderna använder gruppeffektmåttet som objektiv funktion. Upp till författarnas kunskap är dessa de första exakta metoderna som använder en sådan åtgärd för att optimalt lösa fall av MCFP. Den första metoden består av att iterativt köra flera samtal till en parameteriserad version av BGEP, och den andra är en linjärisering av en ny fraktionerad-linjär modell för MCFP. Beräkningsexperiment utförda på fall av MCFP som finns i litteraturen visar att våra exakta metoder för MCFP kan bevisa flera tidigare okända optima.
REF minskade cellbildningsproblemet till ett annat biklusterproblem -bicluster grafredigeringsproblem och föreslog en exakt metod och en linjär programmeringsmodell som ger bra beräkningsresultat för grupperingseffektivitetsmålet.
On Solving Manufacturing Cell Formation via Bicluster Editing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}