99-33
An Enumerative Algorithm for Two-Machine Flow Shop Problems with Earliness and Tardiness Penalties
by Gupta, J.N.D.; Lauff, V.; Werner, F.
Preprint series: 99-33, Preprints
The paper is published: Journal of Mathematical Modelling and Algorithms, Vol. 3, No. 2, 2004, 123 - 151 (under the title: Two-Machine Flow Shop Scheduling with Nonregular Criteria)
Abstract: We consider a two-machine flow shop problem with a common due date where the objective is to minimize an arbitrary function of a weighted sum of penalties assigned to early and tardy completion of jobs. Since the problem is NP-hard in the strong sense, we investigate some general properties of optimal schedules for the problem, we develop lower and upper bounds, derive dominance criteria, and propose an enumerative algorithm for finding an optimal schedule. Finally, the performance of the proposed algorithm is empirically evaluated.
Keywords: scheduling, flow shop non-regular criterion, enumerative algorithm, branch and bound
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.