Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Scheduling batches with sequential job processing for two-machine 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:
1091-9856(200121)13:2<120:SBWSJP>2.0.ZU;2-X
Fonte:
ISI
Lingua:
ENG
Soggetto:
MINIMIZE; SETUP; TIME;
Keywords:
production-scheduling; open-shop; flow-shop; 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 two-machine flow andopen shops", INFORMS J C, 13(2), 2001, pp. 120-137

Abstract

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop 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 flow-shop problem is shown to be strongly NP-hard. 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 worst-case performance ratio of 4/3. For theopen-shop, we show that the problem is NP-hard 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 pseudo-polynomial 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