Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

https://doi.org/10.1016/j.cor.2009.02.012Get rights and content

Abstract

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.

Introduction

A classical parallel machine problem can be stated as follows: a set of the independent jobs to be processed on a number of available identical parallel machines. Each machine can process only one job at a specific time, and each job can be processed on one machine. Each job is ready at the beginning of the scheduling horizon and has a distinct processing time and due date [1].

Majority of scheduling research studies assume that setup times are negligible or part of the processing time. While this assumption simplifies the analysis and/or represents certain industrial applications, it adversely affects the solution quality for many applications which require explicit treatment of setup times and makes the model inapplicable in real environments.

In a manufacturing environment, setup times consist of all activities that are performed on material, in order to prepare them for the main process phase. Production problems that are related to setup times are divided into two important categories: (1) sequence-dependent setup times and (2) sequence-independent setup times. For example, at a production facility where paint is needed, a setup time is incurred for cleaning the machine whenever a color change is required. The thoroughness required in cleaning the machine depends on both the color being removed and the color for which it is being prepared. Likewise, in the plastic industry, items of different colors are typically assigned to different extrusion machines. When a color change is required, a certain amount of time is taken until the extruded plastic reaches the desired color. Such problems are also common in the glass manufacturing industry, where molten glass is held in huge vats before the actual glass blowing process. The vats have to be changed for different colors and properties of the glass. This changeover process incurs major setup times. Likewise, in the soft drink beverage industry, the manufacturing lines have to go through major setups while changing over from filling glass bottles to soda cans. Many such examples can be found in chemical and paper manufacturing industries [2].

In the past years, many researchers have investigated multi-criteria parallel machines scheduling problems with two or more criteria that apply simultaneously or hierarchically in the objective function. Minimizing the number of tardy jobs is one objective that has received less attention researchers. However, in many situations, we face conditions where missed due dates lead to cancellation of orders by the clients. Therefore, in these situations we have to consider a scheduling problem that minimizes the number of tardy jobs.

On the other hand, minimization of the total completion time of all the jobs is commonly applied in scheduling problems by researchers. Decreasing the completion times is an effective method in reducing job lateness and tardiness. Decreasing the completion times also leads to the reduction in the total work-in-process (WIP) inventories, and minimization of irregularities and inordinate shop flow crowding due to uncompleted jobs. Therefore, minimizing the completion times is one of the most important criteria for manufacturing and service organizations.

The presented parallel machine can be formulated as a generalized parallel machine problem, and it thus belongs to the class of NP-hard problems. This paper, a genetic algorithm (GA) is proposed to solve the presented model, for the real-sized instances.

The rest of this paper is organized as follows: a brief overview of the extended model and related literature is presented in Section 2. The extended model is formulated in Section 3. The proposed GA is developed in Section 4. Computational results are reported in Section 5, and finally Section 6 covers the conclusion.

Section snippets

Literature review

Most of the research work preformed on machine scheduling does not consider sequence-dependent setup times for different jobs. We can find a survey on this problem in [3] and [4]. Different methods for solving this problem exist. Some researchers reach the optimal or near-optimal solution by using the mathematical programming models [5], [6], meta-heuristics such as genetic algorithm, and heuristic method based on list scheduling [7], [8], [9].

Monma and Potts [10] considered the complex

Proposed mathematical model

In this paper, we define the parallel machine scheduling in which some machines operate with different speed and all of them are available at the beginning of the scheduling. Jobs are not independent and there are some precedence relations between them. All jobs are not available at the beginning of the scheduling and each of them has its own due date. We know that setup times depend on job sequences and machine types.

As mentioned before, in many cases customers want to receive their orders on

GA implementation

GA is a well-known meta-heuristic approach inspired by the natural evolution of the living organisms. It works on a population of solutions simultaneously. It combines the concept of the survival of the fittest with structured, yet randomized, information exchange to form robust exploration and exploitation of the solution space. The exploration process is performed by a genetic operator, namely Crossover, and the exploitation process is performed by another genetic operator, namely mutation.

Computational results

To solve the presented model, a number of test problems are randomly generated in small and large sizes. To generate model's data, such as processing times, setup times, job's ready times and due dates, the methods presented in [2], [11] are used. To generate processing times and setup times, we use uniform distribution [1], [20] and [1], [7], respectively. Then the amount of setup times is corrected based on inequality Sijm + SjkmSikm. The random number generation for due dates obtained by

Conclusion

In this paper, a novel multi-objective parallel machine scheduling is solved by a zero-one linear programming based on a goal programming approach. This model is proposed to minimize the number of tardy jobs (as the primary criterion) and the total completion times (as the secondary criterion), considering a set of jobs that have non-identical due dates and ready times with some precedence relations on a set of unrelated parallel machines. We have assumed that there were sequence-dependent

Acknowledgement

The authors would like to thank the anonymous reviewers for their helpful comments and suggestions, which greatly improved the presentation of this paper. In addition, this study was partially supported by the University of Tehran under the research Grant No. 8106043/1/09. The first author is grateful for this financial support.

References (25)

  • R. Tavakkoli-Moghaddam et al.

    A memetic algorithm for the flexible flow line scheduling problem with processor blocking

    Computers and Operations Research

    (2009)
  • U. Blidgue et al.

    A tabu search algorithm for parallel machine total tardiness problem

    Computers & Operation Research

    (2004)
  • Cited by (85)

    • Introducing preferences in scheduling applications

      2022, Computers and Industrial Engineering
    • Scheduling parallel extrusion lines

      2024, Journal of Project Management (Canada)
    View all citing articles on Scopus
    View full text