Scheduling a three-machine no-wait flowshop with separated setup time

摘要

In many practical flowshop production environments, there is no intermediate storage space available to keep partially completed jobs between any two machines. The workflow has to be continuous, implying that the no-wait conditions must be abided, which is typical in steel and plastic production. We discuss the three-machine no-wait flowshop scheduling problem where the setup times are considered as separated from processing times and sequence independent. The scheduling goal is to minimize the total flowtime. An optimal property and two heuristic algorithms for this problem are proposed. Evaluated over a large number of problems, the proposed heuristics are found that they can yield good solutions effectively with low computational complexity, and have more obvious advantage for the large size problem compared with the existing one.