Scheduling Two No-wait Hybrid Flowshops

Many problems from industry,are always scheduling problems. In this paper, we studied the model and algorithms of a complicated no-wait hybrid flowshop problem, which originates from the cold rolling mill of Wuhan Iron & Steel Group Corp. The practical problem in mill was described as a model: There exist two no-wait two-stage hybrid flowshops(Flowshop 1 and Flowshop 2), thereinto, Flowshop 1 can be programmed as: , and Flowshop 2 can be programmed as: . The former flowshop has jobs which can only be processed on Flowshop 1, while the latter one has jobs which can be processed on the both Flowshops. The objective is to minimize the maximum finish time makespan(=max{makespan1,makespan2}).When makespan1 is greater than makespan2, we can decrease the makespan just by improving the algorithms for no-wait hybrid flowshop problems. However, when makespan1 is smaller than makespan2, intuitionly, we will adjust some jobs of Flowshop 2 to Flowshop 1, so as to decrease the makespan. Which jobs should be adjusted and how to schedule the new processing sequence? To solve these, we proposed the strategies for the workload reallocation between two no-wait two-stage hybrid flowshops.Most scheduling problems arising in the real manufacturing environment are inherently complex belonging to a class of NP-hard problems. To overcome this difficulty, artificial intelligence literature has recently treated such scheduling problems as CSPs. When the CSP approach is applied to scheduling problems, the problem-solving process requires two kinds of decisions for incremental schedule construction. First, a variable ordering heuristic is necessary to choose the next activity for scheduling from the unscheduled activities. After an activity is chosen, a specific time value for the selected activity is determined according to a ordering heuristic, In this paper, 4 variable ordering strategies and 3 value ordering strategies were proposed. 12 algorithms were formed for the workload reallocation problem. To evaluate the 12 algorithms, we made 11 groups of tests by orthogonal designs. By analysis of test results, we find: case , algorithm H5 behave most significantly; case , alogrithm H12 is the bestchoice, the tests under the practical machine environment ulteriorly confirm it。...