A shuffled frog-leaping algorithm for hybrid flow shop scheduling with two agents

Highlights

• HFSP with two agents and its minimality mode are considered and a novel SFLA is proposed.

• Tournament selection is applied to divide population.

• Not all solutions of population are allocated into memeplexes.

• The best solution of each memeplex acts as the object of the search process.

• The search process consists of the global searches and multiple neighborhood search.

Abstract

Two-agent scheduling problem has attracted much attention; however, two-agent hybrid flow shop scheduling problem (TAHFSP) is seldom studied. In this study, TAHFSP and its minimality model are considered and a novel shuffled frog-leaping algorithm (SFLA) is proposed is to minimize the sum of the objectives of two agents. The following new principles are applied in SFLA: a tournament selection based method is used to divide population, not all solutions of population are allocated into memeplexes, the best solution of each memeplex acts as the object of the search process and the search process within memeplex consists of the global searches on two sub-problems sequentially and multiple neighborhood search. We test the performance of SFLA using a number of instances and the experimental results show the notable advantage of our SFLA when compared to other algorithms of TAHFSP.

Introduction

Generally, multi-agent scheduling problems are composed of several groups of jobs and some necessary processing resources such as machines. Each group of jobs belong to an agent, all agents compete on the use of common processing resources and each of them wishes to minimize an objective function that depends on the completion time of his/her own set of jobs. The goal of multi-agent problem is either to find a schedule that minimizes a combination of the agents’ objective functions or to find a schedule that satisfies each agent's requirement for his/her own objective function.

Since Baker and Smith (2003) and Agnetic, Mirchandani, Pacciarelli, and Pacifici (2004) first introduce the multi-agent scheduling problem, the problem has attracted much attention in the past decade and a large body of literature discusses the problem in single machine, parallel machines and flow shop environments. With respect to multi-agent single machine scheduling, Cheng, Ng, and Yuan (2008) discuss the feasibility model and the minimality model. Lee, Chung, and Hu (2012) propose three genetic algorithms (GA) for two-agent scheduling with release time. The objective is to minimize the total tardiness of jobs from the first agent given that the maximum tardiness of jobs from the second agent does not exceed an upper bound. Yin, Cheng, Cheng, Wu, and Wu (2012) consider several two-agent scheduling problems with assignable due dates and give polynomial-time algorithm. Liu, Yi, Zhou, and Gong (2013) discuss the optimal properties of two-agent scheduling with sum-of- processing-times-based deterioration and present some polynomial time algorithms. Wu et al. (2013) propose branch-and-bound (BB) algorithm and tabu search for two-agent problem with deterioration jobs.

Yin and his partners carry out some related works on two-agent problem in single machine (Wu et al. 2013; Yin et al. 2012; Wang et al., 2015). They provide complexity results for two-agent problems with due date determination, propose a BB algorithm and a marriage in honey bees optimization algorithm for the problem with ready times and present a GA for the problem with learning effects. Feng, Fan, Li, and Shang (2015) discuss NP-hard features of two-agent problem with rejection and present some pseudo-polynomial-time algorithms. Oron, Shabtay, & Steiner, 2015 also prove the NP-hard complexity and provide some pseudo-polynomial-time algorithms for the problem with equal processing times.

With respect to parallel machines multi-agent scheduling, Elvikis, Hamacher, and T'kindt (2011) discuss two-agent scheduling on uniform parallel machines with two conflicting objectives and provide polynomial time algorithms for solving the problem. Li and Yuan (2012) consider the constrained optimization problem with an unbounded parallel-batch machines and two agents and provide polynomial-time and pseudo-polynomial-time algorithm. Fan, Cheng, Li, and Feng (2013) study the NP-hard feature and polynomial solvability of bounded parallel-batching scheduling with two competing agents and different objectives. Zhao and Lu (2015) propose two approximation algorithms for two-agent parallel machines scheduling

Some studies have considered multi-agent scheduling in flow shop environments. Lee, Chen, and Wu (2010) consider two-agent two-machine flow shop scheduling problem and develop a BB algorithm and simulated annealing (SA) to minimize the total tardiness of the first agent with no tardy jobs for the second agent. Lee, Chen, Cheng, and Wu (2011) study a two-machine flow shop problem with two agents where the objective is to minimize the total completion time of first agent with no tardy jobs for the second agent. Luo, Chen, and Zhang (2012) investigate the weighted-sum optimization model and the constrained optimization model and study approximation schemes for two-machine flow shop scheduling with two agents. Mor and Mosheiov (2014) study polynomial time solution algorithms for the problem on a proportionate flow shop with two agents. Shiau, Tsai, Lee, and Cheng (2015) present some GAs two-agent two-machine flow shop with learning effects. Lei, 2015a, Lei, 2015b) propose a variable neighborhood search (VNS) and a two-phase neighbor-hood search for two-agent scheduling in flow shop and hybrid flow shop respectively to simultaneously minimize objectives of two agents under the given upper bound.

As stated above, the previous studies on multi-agent production scheduling have the following features: (1) Most of papers have been presented for multi-agent scheduling on single machine. Multi- agent flow shop scheduling also attract some attention; however, the existing researches mainly focus on two-agent two-machine flow shop scheduling and multi-agent scheduling is not fully considered in hybrid flow shop, which is common manufacturing environments. (2) The pseudo-polynomial-time algorithm and BB algorithms are often applied to solve the problem. Several meta-heuristics such as GA (Lee et al., 2012), VNS (Lei, 2015a) and SA (Lee et al., 2010) also have been used to deal with multi-agent scheduling; however, for multi-agent scheduling, the applications of meta-heuristics are not extensive and the advantages of meta-heuristics such as SFLA are not fully investigated.

SFLA is based on observing, imitating and modeling the behavior of a group of frogs when searching for the location that has the maximum amount of available food. SFLA is originally developed by Eusuff, Lansey, and Pasha (2006). SFLA has been applied to production scheduling problems (Rahimi-Vahed et al., 2009, Pan et al., 2011, Li et al., 2012, Fang and Wang, 2013); however, to the best of our knowledge, SFLA is not applied to multi-agent scheduling. The main benefits of SFLA are its fast convergence speed and effective algorithm structures containing local search and global information exchanges. The advantages of SFLA and the extensive applications of hybrid flow shop motivate us to consider two-agent hybrid flow shop scheduling problem (TAHFSP) and apply some new principles to design SFLA for the problem. The objective is to minimize the sum of the objectives of two agents.

The remainder of the paper is organized as follows. Problem under study is described in Section 2 and followed by the description on basic SFLA (BSFLA) in Section 3. The novel SFLA for the problem is described in Section 4. Numerical test experiments on SFLA are reported in Section 5 and the conclusions are summarized in the final section and some topics of the future research are provided.