Catalogo Articoli (Spogli Riviste)
OPAC HELP
Titolo: Scheduling batches with sequential job processing for twomachine flow andopen shops
Autore: Glass, CA; Potts, CN; Strusevich, VA;
 Indirizzi:
 City Univ London, Sch Math, London EC1V 0HB, England City Univ London London England EC1V 0HB Math, London EC1V 0HB, England Univ Southampton, Fac Math Studies, Southampton SO17 1BJ, Hants, England Univ Southampton Southampton Hants England SO17 1BJ 7 1BJ, Hants, England Univ Greenwich, Sch Comp & Math Sci, London SE10 9LS, England Univ Greenwich London England SE10 9LS ath Sci, London SE10 9LS, England
 Titolo Testata:
 INFORMS JOURNAL ON COMPUTING
fascicolo: 2,
volume: 13,
anno: 2001,
pagine: 120  137
 SICI:
 10919856(200121)13:2<120:SBWSJP>2.0.ZU;2X
 Fonte:
 ISI
 Lingua:
 ENG
 Soggetto:
 MINIMIZE; SETUP; TIME;
 Keywords:
 productionscheduling; openshop; flowshop; analysis of algorithms : computational complexity; suboptimal algorithms;
 Tipo documento:
 Article
 Natura:
 Periodico
 Settore Disciplinare:
 Engineering, Computing & Technology
 Citazioni:
 21
 Recensione:
 Indirizzi per estratti:
 Indirizzo: Glass, CA City Univ London, Sch Math, London EC1V 0HB, England City Univ London London England EC1V 0HB don EC1V 0HB, England



 Citazione:
 C.A. Glass et al., "Scheduling batches with sequential job processing for twomachine flow andopen shops", INFORMS J C, 13(2), 2001, pp. 120137
Abstract
In this paper, we study a problem of scheduling and batching on two machines in a flowshop and openshop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, andall jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flowshop problem is shown to be strongly NPhard. We demonstratethat there is an optimal solution with the same batches on the two machines; we refer to these as consistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worstcase performance ratio of 4/3. For theopenshop, we show that the problem is NPhard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. Thisallows a pseudopolynomial algorithm to he derived, and various heuristic methods to be suggested.
ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 26/01/20 alle ore 16:11:02