Variable neighborhood search for two-agent flow shop scheduling problem

• Two-agent scheduling in flow shop with more than two machines is first considered.
• The feasibility model is considered unlike most of literature on multi-agent scheduling.
• A VNS with learning neighborhood structure and a new replacement principle is proposed.
• Computational results show the promising advantage of VNS.

Multi-agent scheduling in flow shop environment is seldom considered. In this paper flow shop scheduling problem with two agents is studied and its feasibility model is considered, in which the goal is to minimize the makespan of the first agent and the total tardiness of the second agent simultaneously under the given upper bounds. A simple variable neighborhood search (VNS) algorithm is proposed, in which a learning neighborhood structure is constructed to produce new solutions and a new principle is applied to decide if the current solution can be replaced with the new one. VNS is tested on a number of instances and the computational results show the promising advantage of VNS when compared to other algorithms of the problem.

Figure optionsDownload as PowerPoint slide