Flexible job shop scheduling with overlapping in operations

In this paper, flexible job shop scheduling problem with a new approach, overlapping in operations, is discussed. In many flexible job shops, a customer demand can be released more than one for each job, where demand determines the quantity of each finished job ordered by a customer. In these models each job has a demand more than one. This assumption is an important and practical issue for many flexible job shops such as petrochemical industries. To consider this assumption, we use a new approach, named overlapping in operations. In this approach, embedded operations of each job can be performed due to overlap considerations in which each operation may be overlapped with the others because of its nature. The overlapping is limited by structural constraints, such as the dimensions of the box to be packed or the capacity of the container used to move the pieces from one machine to the next. Since this problem is well known as NP-Hard class, a hierarchical approach used simulated annealing algorithm is developed to solve large problem instances. Moreover, a mixed integer linear programming (MILP) method is presented. To evaluate the validity of the proposed SA algorithm, the results are compared with the optimal solution obtained with the traditional optimization technique (The Branch and Bound method). The computational results validate the efficiency and effectiveness of the proposed algorithm. Also the computational results show that the overlapping considering can improve the makespan and machines utilization measures. So the proposed algorithm can be applied easily in real factory conditions and for the large size problems and it should thus be useful to both practitioners and researchers. (C) 2008 Elsevier Inc. All rights reserved.