Study On A Two-stage Hybrid Flowshop Scheduling Problem

In this paper, a two-stage hybrid flowshop scheduling problem which consists of processing stage and assembly stage is considered. The hybrid flowshop scheduling problem is also named the flexible flow shop scheduling problem. The problem consists of the traditional flowshop scheduling problem and the parallel machines scheduling problem.Even if there are only two machines in the processing stage, the problem has been proved that it was NP-hard. The hybrid flowshop scheduling problem has a wide application in process industry, especially the car manufacturing, metallurgy and chemical industry. Therefore, in recent years, the problem has become the focus of attention of experts and scholars from different states.Actually, the production system can process different products which assembled by different parts. The scheduling problem in this paper consists of machining operation and assembly operation. The machining operation stage is a hybrid flowshop, which contains two stages. There are different numbers of parallel machines in each stage.Firstly, considering the features of this problem, this paper proposed a mixed integer programing model. For verified the correctness of the model, run an example on the software called ILOG OPL Studio3.5.1. Secondly, a heuristic has been produced which base on the Johnson’rule and Longest Processing Time rule. The heuristic find the sequence of products in the assembly stage first, then according to the product’ sequence, find the sequence of parts belong to each products in the processing stage. Lastly, this paper also presents a heuristic discrete particle swarm optimal algorithm (H-DPSO) and a heuristic variable neighborhood search algorithm (H-VNS). The heuristic discrete particle swarm optimal algorithm design a method called "job-to-position" for representing the discrete particle. The heuristic variable neighborhood search algorithm designs real coding to represent the job list. The two algorithm both used the list which given by the proposed heuristic as one of the initial solutions. In addition, two lower bounds which can evaluate and analysis the presented algorithm have been produced in this paper.The numerical experiments are used to evaluate the performance of the proposed algorithm. Computational results show that the presented heuristic can efficiently obtain near optimal solution with an average percentage deviation of1.6749in large scale of problems.