Digitale Bibliotheek
Sluiten Bladeren door artikelen uit een tijdschrift
 
<< vorige    volgende >>
     Tijdschrift beschrijving
       Alle jaargangen van het bijbehorende tijdschrift
         Alle afleveringen van het bijbehorende jaargang
           Alle artikelen van de bijbehorende aflevering
                                       Details van artikel 2 van 10 gevonden artikelen
 
 
  An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times
 
 
Titel: An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times
Auteur: Billaut, Jean-Charles
Gribkovskaia, Irina
Strusevich, Vitaly
Verschenen in: IIE transactions
Paginering: Jaargang 40 (2008) nr. 4 pagina's 478-493
Jaar: 2008-04
Inhoud: We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.
Uitgever: Taylor & Francis
Bronbestand: Elektronische Wetenschappelijke Tijdschriften
 
 

                             Details van artikel 2 van 10 gevonden artikelen
 
<< vorige    volgende >>
 
 Koninklijke Bibliotheek - Nationale Bibliotheek van Nederland