A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-streaming flow shop scheduling problems

Abstract

A blocking lot-streaming flow shop (BLSFS) scheduling problem is to schedule a number of jobs on more than one machine, where each job is split into a number of sublots while no intermediate buffers exist between adjacent machines. The BLSFS scheduling problem roots from traditional job shop scheduling problems but with additional constraints. It is more difficult to be solved than traditional job shop scheduling problems, yet very popular in real-world applications, and research on the problem has been in its infancy to date. This paper presents a hybrid multi-objective discrete artificial bee colony (HDABC) algorithm for the BLSFS scheduling problem with two conflicting criteria: the makespan and the earliness time. The main contributions of this paper include: (1) developing an initialization approach using a prior knowledge which can produce a number of promising solutions, (2) proposing two crossover operators by taking advantage of valuable information extracted from all the non-dominated solutions in the current population, and (3) presenting an efficient Pareto local search operator based on the Pareto dominance relation. The proposed algorithm is empirically compared with four state-of-the-art multi-objective evolutionary algorithms on 18 test subsets of the BLSFS scheduling problem. The experimental results show that the proposed algorithm significantly outperforms the compared ones in terms of several widely-used performance metrics.

Introduction

Scheduling is to optimally arrange limited resources (such as machines in a shop and processing units in a computing environment) to complete tasks with respect to one or more objectives [22]. In literature, flow shop or job shop scheduling problems have been widely studied. For interested readers, please refer to [10], [11], [20], [28], [58], [60] for a survey and recent advances. In addition, Table 1 lists the abbreviation of terminology in the whole paper conveniently for reading.

It has always been a common practice to split a job into a number of sublots, which can bring various advantages, such as shortening the production period of a job and enhancing the production efficiency. Specifically, the term “lot-streaming” means to split a job into more than one sublot with each sublot being processed on the downstream machine when it is completed in the current one. LSFS scheduling problem is thus to determine either the best allocation of sublots or the size of a sublot so as to optimize given criteria. It has become a widely researched topic for its various applications in manufacturing systems, information service facilities, and semiconductor industries, and others [39].

LSFS scheduling problems can be roughly classified into two categories with respect to the number of buffers (either infinite or finite). The former does not result in job blocking since it has enough intermediate buffers to store completed jobs. Here, the term “blocking” means to maintain a limited capacity of in-process inventories due to finite intermediate buffers, which makes the search for optimal sublot assignments among jobs difficult.

In this study, we focus on a BLSFS scheduling problem that schedules a number of jobs on more than one machine, where each job is split into a number of sublots, and there are no intermediate buffers between adjacent machines. Up to present, there have already been a bunch of papers for solving LSFS scheduling problems, in which a variety of optimization algorithms have provided excellent results in the acceptable computation time. The BLSFS scheduling problem roots from traditional LSFS scheduling problems but with additional blocking constraints, which makes it difficult to seek solutions with high quality [54].

For a BLSFS scheduling problem, a decision-maker generally expects to minimize the maximal makespan that is equal to the difference between the time when the last job is finished on the final machine and the setup time of the first job on the beginning machine. Besides, inspired by the philosophy of just-in-time production [37], the decision-maker also concerns with the due date for their customers’ satisfaction. The earliness or tardiness time, which is defined as the difference between the completion time and the due date, reflects strict requirements on the due date. If the due date is set in advance, the shorter the makespan of a scheduling strategy, the longer the earliness time of the process. However, it is not always preferable that the completion time is earlier than the due date, since a job completed earlier than its due date is possible to increase the inventory levels and floor space requirements, resulting in losses. Therefore, we need to optimize both objectives, i.e. the makespan and the earliness time. On this circumstance, the BLSFS scheduling problem can be formulated as a bi-objective optimization problem.

In literature, various methods have been successfully minimized the makespan, the total flow time and the earliness time of a flow shop scheduling problem without blocking, respectively. For example, Meng et al. [32] considered an integrated LSFS scheduling problem with the makespan criterion, in which lot-splitting and job scheduling are simultaneously optimized. Zhang et al. [62] employed a migrating birds algorithm to optimize the total flow time of a hybrid flow shop scheduling problem with lot streaming. Pan and Ruiz [38] applied EDA to minimize the makespan of a LSFS scheduling problem with the sequence-dependent setup time. Following that, Tiwari et al. [55] designed a Pareto block-based EDA for multi-objective permutation flow shop scheduling problems.  Han et al. [12] proposed an improved NSGA-II for multi-objective LSFS scheduling problems, in which EDA and a mutation operator based on insertion and swap are utilized to replace traditional crossover and mutation operators. Ventura and Yoon[56] employed a new genetic algorithm for LSFS scheduling problems with a limited capacity of buffers. Their objective is to minimize the total weighted earliness and tardiness time.

In the aforementioned work on a LSFS scheduling problem, various objectives, such as the makespan, the total flow time, the earliness and tardiness time, have been considered. These methods often transform all the objectives into one by weighting them [51]. However, methods based on the weighted objective cannot provide a diverse set of solutions for a decision-maker. On the other hand, it is rather difficult to select suitable weights that can accurately reflect a decision-maker’ preferences [12]. Therefore, it is appealing to take all the objectives into consideration and search for a set of solutions for a decision-making’s preferences.

In this paper, we aim to develop a multi-objective evolutionary algorithm for BLSFS scheduling problems based on ABC. The ABC algorithm has been successfully applied to various real-world single- and multi-objective optimization problems described in Section 2. It has many advantages, such as simple structures, easy to implement and fast convergence, which motivates our development of ABC for the considered problem.

The rest of this paper is organized as follows. Section 2 briefly introduces the basic ABC algorithm, its variants, and applications in solving scheduling problems. Section 3 formulates the considered BLSFS scheduling problem. The proposed algorithm is illustrated in Section 4. Section 5 provides the experimental results and analysis. Finally, Section 6 concludes the whole paper and points out several topics to be further researched.