A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity

Highlights

• Features of deteriorating maintenance activities, parallel-batching processing, and deteriorating jobs are considered simultaneously in an unrelated parallel machine scheduling problem. Considering the joint decision on jobs assignments, maintenance arrangements, jobs batching, and batches sequencing, a mixed integer programming model is formulated.

• Given that all jobs have been assigned to machines, we provide the detail analysis of the problem. Based on the derived structural properties, we developed optimal algorithms to solve the problem.

• Since the studied problem is proved to be NP-hard, a hybrid ABC-TS algorithm based on ABC and TS is proposed to search for a good solution in a reasonable time.

Abstract

This paper studies an unrelated parallel machine scheduling problem with deteriorating maintenance activities, parallel-batching processing, and deteriorating jobs. Practically, deteriorating maintenance activities mean that durations of maintenance activities will increase with their starting time. The objective is to make the joint decisions on jobs assignments, the maintenance arrangements, jobs batching, and batches sequencing on each machine to minimize the makespan. Firstly, we formulate a mixed integer programming model for the problem. Then, we analyze a special case where all jobs have been assigned to machines and provide polynomial time optimal algorithms. Furthermore, since the studied problem is NP-hard, we develop a hybrid ABC-TS algorithm combining artificial bee colony (ABC) and Tabu Search (TS) to solve the problem in a reasonable time. Extensive computational experiments are conducted and the results validate the effectiveness and robustness of our proposed algorithms.

Introduction

In traditional scheduling problems, the processing time of a job is usually assumed to be fixed and known in advance. However, in practical production, e.g., steel production, national defense, medical treatment, and environmental governance, any delay in tackling a task may result in supplementary time for accomplishing the task [[1], [2], [3], [4], [5], [6]]. Gupta and Gupta [7] first investigated scheduling problems under this kind of situations and called it deteriorating effect. Following this topic, extensive surveys on various scheduling problems with deteriorating effect were summarized by Cheng et al. [8] and Gawiejnowicz [9]. More recent papers integrated deteriorating effect into the newest scheduling models including Cheng et al. [10] and Zhu et al. [11].

Furthermore, the scheduling problems taking both deteriorating effect and maintenance activity into consideration have received considerable attention. Yang and Yang [12] studied a single-machine scheduling problem with deteriorating job processing time and maintenance duration to minimize total completion time, and then they Yang and Yang [13] extended their study by considering the objective to minimizing makespan. Under similar assumptions, Cheng et al. [14] investigated various due window assignment problems. More researchers investigated scheduling problems considering different deteriorating functions and maintenance schemes such as Zhao and Tang [[15], [16]], Yang [[17], [18]], Luo and Ji [19], Yu [20], Do Chung and Kim [21], Kacem and Levner [22], and Zhang et al. [23], which are presented in Table 1.

Another important class of scheduling problems is characterized by the parallel-batching processing, where jobs are processed in batches and the processing time of a batch is determined by the largest processing time of all jobs contained in the batch [24]. A review of previous research work on this topic was given by Mathirajan and Sivakumar [25]. Sung et al. [26] studied the multiple machines parallel-batching scheduling problem in dynamic situations and put forward several efficient heuristics. Some scholars dedicated their efforts to the problem with non-identical job sizes, e.g., Chen et al. [58] and Zhou et al. [59]. Considering deteriorating jobs, Li et al. [27] and Miao [28] provided complexity analysis and approximation algorithms.

A real manufacturing system usually consists of several parallel machines which can process jobs simultaneously. Owing to the complexity of the parallel machine scheduling problems [29], exact methods may fail to find the optimum solution within a reasonable time. Hence, the application of metaheuristics is justified to obtain an optimal or approximately optimal schedule for such problems [[30], [31]]. An improved genetic algorithm (GA) was proposed to solve parallel machine scheduling problems in Joo and Kim [32]. Based on another effective metaheuristic known as particle swarm algorithm (PSO), Ding [33] and Behnamian [34] studied parallel machine scheduling problems in general and fuzzy situations respectively. Mir and Rezaeian [35] extended the research on this topic and developed hybrid algorithms based on GA and PSO.

In this paper, we investigate an unrelated parallel machine scheduling problem in consideration of deteriorating maintenance activities, parallel-batching processing, and deteriorating jobs. To the best of our knowledge, the proposed problem has not been considered yet while it is very common in real production systems. Based on the characteristics of the problem, we derive some structural properties and develop several heuristic algorithms. Furthermore, a hybrid metaheuristic is proposed to solve the problem of minimizing makespan.

The contribution of this paper can be summarized as follows.

• An unrelated parallel machine scheduling problem with deteriorating maintenance activities, parallel-batching processing, and deteriorating jobs is proposed and a mixed integer programming model is formulated by considering the joint decision on jobs assignments, maintenance arrangements, jobs batching, and batches sequencing.

• We analyze a special case where all jobs have been assigned to machines. Based on the derived structural properties for the case, optimal algorithms are developed to minimize makespan.

• Due to the complexity of the studied problem, a hybrid ABC-TS algorithm combining ABC and TS is proposed to obtain a good solution in a reasonable time.

The remainder of this paper is organized as follows. Section 2 gives the description of the problem formulation. In Section 3, some structural properties and solution procedures are presented. A hybrid algorithm combining ABC with TS is designed in Section 4 to solve the studied problem. The results of computational experiments are presented in Section 5. Finally, Section 6 concludes the paper.