Search

This paper presents a tabu search algorithm that solves the flexible job shop scheduling problem to minimize the makespan time. As a context for solving sequencing and scheduling problems, the flexible job shop model is highly complicated. Alternative operation sequences and sequence-dependent setups are two important factors that frequently appear in various manufacturing environments and in project scheduling. In this paper, we present a model for a flexible job shop scheduling problem while considering those factors simultaneously. The purpose of this paper is to minimize the makespan time and to find the best sequence of operations and the best choice of machine alternatives, simultaneously. The proposed tabu search algorithm is composed of two parts: a procedure that searches for the best sequence of job operations, and a procedure that finds the best choice of machine alternatives. Randomly generated test problems are used to evaluate the performance of the proposed algorithm. Results of the algorithm are compared with the optimal solution using a mathematical model solved by the traditional optimization technique (the branch and bound method). After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented. Computational results indicate that the proposed algorithm can produce optimal solutions in a short computational time for small and medium sized problems. Moreover, it can be applied easily in real factory conditions and for large size problems. The proposed algorithm should thus be useful to both practitioners and researchers. [ABSTRACT FROM AUTHOR]

Multiple-route job shop scheduling problem (MRJSP) is a generalization of job shop scheduling problem in which each job may have more than one route for its production and the numbers of operations associated to the alternative routes of the job are not necessarily equal. MRJSP is recognized to be extremely difficult because of its combinatorial nature of integer optimization and the large size of the real problem, necessitating the use of heuristic approaches or dispatching rules for its solution. In this paper, mathematical formulation of MRJSP is first presented. Then, a two-phase algorithm is proposed to deal with the two major sub-problems in MRJSP, namely, the route selection and the sequencing sub-problems. In order to evaluate the effectiveness of the proposed algorithm, several problems (in small, medium, and large sizes) are designed and solved using the proposed algorithm. The problems are also solved using some other dispatching rules, and comparisons are provided. The computational results show that the proposed algorithm generates high-quality schedules in a timely fashion. [ABSTRACT FROM AUTHOR]