A heuristic for parallel machine scheduling depending on job characteristics

In the real world, situations that some jobs need be processed only on certain limited machines frequently occur due to the capacity restrictions of machines such as tools, fixtures, or material handling equipment. In this paper, we consider n-job, non-preemptive and m parallel machines scheduling problem having two machines group. The objective function is to minimize the sum of earliness and tardiness with different release times and due dates. The problem is formulated as a mixed integer programming problem. The problem is proved to be NP-complete. Thus, a heuristic is developed to solve this problem. To illustrate its suitability and efficiency, a proposed heuristic is compared with a genetic algorithm and tabu search for a large number of randomly generated test problems in ship engine assembly shop. Through the experimental results, it is shown that the proposed algorithm yields good solutions efficiency.