Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan

https://doi.org/10.1016/j.knosys.2009.06.002Get rights and content

Abstract

This paper presents an efficient meta-heuristic algorithm based on electromagnetism-like mechanism (EM), in which has been successfully implemented in a few combinatorial problems. We propose the EM for scheduling the flow shop problem that minimizes the makespan and total weighted tardiness and considers transportation times between machines and stage skipping (i.e., some jobs may not need to be processed on all the machines). To show the efficiency of this proposed algorithm, we also apply simulated annealing (SA) and some other well-recognized constructive heuristics, such as SPT, NEH, (g/2, g/2) Johnson’ rule, EWDD, SLACK, and NEH_EWDD for the given problems. To evaluate the performance and robustness of our proposed EM, we experiment a number of test problems. Our computational results show that our proposed EM in almost all cases outperforms SA and other foregoing heuristics applied to this paper.

Introduction

Production scheduling, which is a decision-making process in the operational level, can be defined as the allocation of available production resources to carry out certain tasks in an efficient manner. A scheduling problem is difficult to solve due to its complex nature. One of the most thoroughly studied scheduling problems is the flowshop (FS) problem. In regular FS, we have a set of n jobs {J1,J2,  ,Jn} and a set of m machines {M1,M2,  ,Mm}. Each job has a set of m operation {Oi1,Oi2,  ,Oim} and each operation can be done by one machine. All jobs have the same processing route, starting from Machine 1 until finishing at machine m. Job i has a non-negative, known, and fixed processing time for operation j. pij denotes the processing time of job i on machine j. By removing the restriction that all jobs need to be processed on all machines, regular FS convert to flowshop with stage skipping, so-called flexible flow shop, which is more realistic than regular FS [12].

In addition, transportation times are considered in this problem. In the most papers in scheduling, it is assumed that the process of job i on machine j commences without delay after finishing its process on machine j  1. In practice, in most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as an automatic guided vehicle (AGV). The transportation time from machine j-1 to machine j is Tf and transportation time from machine j to machine j  1 is Tb. The time to load and unload the AGV is included in the transportation time. When AGV leaves the first machine, it always returns in time Tf + Tb to take the next job. This transportation time can be either job-dependent or job in-dependent. We assume that all transportations are job-independent; and transportations between two machines have to be done by one AGV. This AGV can only carry one job at a time; therefore, a job may have to wait for the AGV before its transportation.

The purpose of production scheduling is to find the job sequence in such a way that one or some objectives are optimized. All the objectives which are commonly considered by researchers are classified into three types: (1) efficient utilization of resources: maximum completion time or makespan; (2) rapid response to demands, or minimization of work in process: total weighted completion time, mean flow time, or mean waiting time; and (3) close conformance to prescribed deadlines: total weighted tardiness, maximum tardiness, and the number of tardy jobs. The tardiness of each job is equivalent to the amount of time the job is completed after its due date. The first and second types of decision-making goals are process oriented and the third one is considered as a costumer oriented objective [1].

The best sequence with respect to the makespan minimization may have a large number of jobs being completed after their due dates. In this case, we also consider the total weighted tardiness (TWT) minimization, in which the relative importance of each job is indicated by a weight. This weight is multiplied by the amount of tardiness. The TWT minimization is of vital prominence in a make-to-order or just-in-time environment [19]. Through exploring two essentially different objectives, we aim at evaluating the robustness of our proposed electromagnetism algorithm (EMA). In other words, we study whether the high performance of EMA is transferable to other objective functions.

Electromagnetic algorithm is known as a meta-heuristic method to tackle complex optimization problems. The motivation behind this algorithm has risen from the attraction–repulsion mechanism of electromagnetic theories and this basic idea that in meta-heuristics we desire to bring our search closer to a region with superior objective function values and at same time, go away from the region with inferior objective function values to move the algorithm gradually toward the optimality. EMA shows very high-performing rather than other meta-heuristics in NP-hard problems [25]. Therefore, we have been thinking of applying EMA to a case of the flowshop scheduling problem. In our case, transportation times and stage skipping are assumed. To assess the performance of the proposed EMA, we go through the corresponding problem under minimization of two separate objectives: (1) total weighted tardiness times from make-to-order environments; and (2) makespan (Cmax) from make-to-stock environments.

The purpose of this paper is to ponder a more realistic case of flowshop with stage skipping and transportation times. To solve such an NP-hard problem [19], we apply our proposed EMA and solve the given problem with two independent objectives to examine the EMA robustness in the different situations. Finally, we compare the consequence with some other related algorithms.

The rest of the paper is organized as follows: Section 2 gives the literature review of the problem. In Section 3, the proposed algorithm is presented. In Section 4, we evaluate our proposed algorithm and other algorithms by a benchmark. Finally, Section 5 concludes the paper.

Section snippets

Literature review

The flowshop with stage skipping (FS-SS) has been a very dynamic research domain on meta-heuristic and heuristic methods, principally because of the difficulty encountered by exact methods to solve large or medium instances. Salvador [20] was first defined the FS-SS. A detailed survey for the FS-SS has been given by Linn and Zhang [14] and Wang [26]. Moursli and Pochet [16] presented a branch-and-bound algorithm to minimize the makespan in the FS-SS. Due to high complexity of FS-SS, exact

Dispatching rules

In this paper, we consider six dispatching rules applied for each decision-making goals, process and customer oriented. We classify these rules into two main groups as follows:

  • (1)

    Those dispatching rules are used to solve scheduling problems focusing on makespan, such as SPT (shortest processing time), NEH (Nawaz, Enscore Jr., and Ham), and (g/2, g/2) Johnson’ rule.

  • (2)

    Those dispatching rules are used to solve scheduling problems focusing on due dates, such as EWDD (earliest weighted due date), SLACK,

Experimental evaluation

We are going to apply a benchmark to evaluate the performance of our proposed algorithms. These algorithms are implemented in MATLAB 7.0 and run on a Pentium IV PC with an Intel processor running at 3 GHz and 1 GB of RAM memory. We use the relative percentage deviation (RPD) for makespan as a common performance measure to compare these algorithms. The best solutions obtained for each instance (which is named Minsol) are calculated by any of five algorithms. RPD is obtained by Eq. (3).RPD=Algsol-

Conclusion and future work

In this paper, we have proposed a new robust electromagnetism-like algorithm (EMA) for the flowshop (FS) problem with stage skipping and transportation times between machines that minimizes bi-objectives: (1) total weighted tardiness times; and (2) makespan, independently. We have also applied simulated annealing (SA) and some well-known dispatching rules to the given problem. The related results were analyzed in terms of the objective functions and the effects of the problem size in all

Acknowledgement

The authors would like to acknowledge the Iran National Science Foundation (INSF) for the financial support of this work.

References (27)

Cited by (0)

View full text