دانلود رایگان ترجمه مقاله استفاده از الگوریتم Branch و Bound برای حل مساله زمانبندی جریان کارکردی (سال 2014)

کاربرد الگوریتم شاخه ایی و محدود به منظور حل مشکل زمانبندی Flow Shop و مقایسه آن با الگوریتم جست جوی Tabu

Application of Branch and Bound algorithm for solving flow shop scheduling problem comparing it with tabu search algorithm

Abstract

The leading position in contributing to the economics of many countries is hold occupied by the garments factory and it has great opportunity to enhance its area .In Bangladesh, the garment factory is the top of the organization, which takes the vital role in the economic sector. As the number of jobs and machines increase, the flow shop scheduling problems in the industry approaches to difficulty. Consider a regular flow shop cell with several bottleneck stages. If such were the case, the industry owners would provide more resources to these bottleneck stages. In this case it is so much important to eliminate the bottleneck in production section and improve the total productivity of the industry. This paper deals with the Branch and Bound technique for solving M machines and N jobs in flow-shop scheduling problem. Here the optimal sequence of jobs is obtained through minimizing the total elapsed time by a lower Bounding (LB) method based on the Branch and Bound algorithm. The working of the algorithm has been illustrated by numerical example and also a C++ code was used to generate an algorithm for finding the optimal solution. The input parameters are process time and operation sequence for each job in the machines provided. This research ensures the makespan optimal values of the schedules comparing with the Tabu search method.

1 Introduction

Consider n different jobs that need to be processed on m machines in the same order. Each job has one operation on each machine and the operation of job i on machine j has processing time Pij. This problem is called a flow shop problem [1,5].In a flow shop problem all jobs have the same ordering sequence on all machines. An optimal permutation schedule does not produce an appreciably worse performance than the optimal general flow shop schedule [4]. Also schedules are attractive from a practical point of view since they are easier to implement. The flow shop problem is NP-hard for m >=3 [3,7]. Optimal solutions can only be obtained via enumeration techniques such as Branch and Bound[6] . However, these methods may take a prohibitive amount of computation even for medium-size problems and become intractable for large problems. This leads to the development of many heuristic procedures. Heuristics for solving the flow shop scheduling problem can be divided into two categories: sequence generating heuristics and improvement heuristics. The former methods generate a schedule from scratch. Most of these methods are either extensions or based on the ideas behind Johnsons’ s well known algorithm for solving twoand three-machine problems[2,4,8,9]. Starting with a solution produced by some sequence generating heuristic, improvement heuristics provide a scheme for obtaining a new sequence with improved performance measure. Methods of this type include neighborhood search techniques[5] such as simulated annealing and tabu search. Tabu search is a local search based optimization method which has been successfully used to solve many difficult combinatorial optimization problems, particularly in the scheduling area. It also exhibited considerable robustness.