A polynomial algorithm for a two-job shop scheduling problem with routing flexibility

Author

Mati, Yazid ; Xie, Xiaolan

Author_Institution

INRIA, MACSI & LGIPM, ENIM, Metz, France

Volume

1

fYear

2003

fDate

14-19 Sept. 2003

Firstpage

157

Abstract

A classical two-job shop problem deals with the determination of an optimal schedule of operations fixed by the technological process. In this paper, we address a generalization of such a problem by introducing the routing flexibility on the realization of jobs. The sequence a job follows in order to be performed is not fixed but must be computed from several alternatives. A polynomial algorithm, based on the geometric approach for the two-job shop problem, is developed for solving a particular case with two jobs. The algorithm applies for the minimization of any regular objective function.

Keywords

flexible manufacturing systems; job shop scheduling; manufacturing processes; minimisation; polynomials; geometric approach; linear operations sequence; machines; objective function minimization; optimal schedule; polynomial algorithm; routing flexibility; technological process; two-job shop scheduling problem; Flexible manufacturing systems; Job shop scheduling; Minimization methods; Modems; Optimal scheduling; Polynomials; Processor scheduling; Routing; Scheduling algorithm; Transportation;

fLanguage

English

Publisher

ieee

Conference_Titel

Robotics and Automation, 2003. Proceedings. ICRA '03. IEEE International Conference on

ISSN

1050-4729

Print_ISBN

0-7803-7736-2

Type

conf

DOI

10.1109/ROBOT.2003.1241589

Filename

1241589