《2016 A note on flow-shop and job-shopbatch scheduling with identical processing-time jobs》.pdfVIP

European Journal of Operational Research 161 (2005) 285–291 /locate/dsw Short Communication A note on flow-shop and job-shop batch scheduling with identical processing-time jobs Gur Mosheiov a,*, Daniel Oron b a School of Business Administration, The Hebrew University, Mount Scopus, Jerusalem 91905, Israel b Department of Statistics, The Hebrew University, Mount Scopus, Jerusalem 91905, Israel Received 19 February 2003; accepted 4 September 2003 Available online 19 December 2003 Abstract We address a batch scheduling problem of n identical processing time jobs on an m-machine flow-shop and a 2- machine job-shop. The objective is makespan minimization. Both problems are shown to be solved in O ðnÞ. 2003 Elsevier B.V. All rights reserved. Keywords: Batch scheduling; Flow-shop; Job-shop; Makespan 1. Introduction Formally, assume that a set of n jobs is avail- able for processing at time zero on an m-machine In a recent paper, Cheng et al. [1] studied a flow-shop. p ij denotes the processing time of job j minimum makespan scheduling problem on a two- on machine i, i ¼ 1; . . . ; m, j ¼ 1; . . . ; n. Job pro- machine flow-shop with batching and sequence- cessing times are assumed to be identical, i.e., independent setup times. The problem is proved to p ij ¼ p for all jobs. Jobs have to be batched as wel