Abstract
Most research in production scheduling is concerned with the optimization of a single criterion. However, the analysis of the performance of a schedule often involves more than one aspect and therefore requires a multi-objective treatment. Therefore, in this research, the author makes use of one of the multiple objective decision-making methods, the min-max technique, to develop a new hybrid metaheuristic for solving sequence-dependent setup time hybrid flowshop scheduling problems with consideration of two performance measures, namely the makespan and the sum of the earliness and tardiness, simultaneously. In formulation of min-max type, the decision maker can have the flexibility of mixed use of weights and distance parameter in expressing desired improvement on produced Pareto optimal solutions. The proposed hybrid approach comprises two components: an electromagnetism-like algorithm and a tabu search to improve it. An extensive computational experience is carried out in order to analyze the different parameters of the combined algorithm. The comparison in the chapter shows the proposal to be very efficient for different structure instances.
Top1. Introduction
Scheduling theory has been developed to solve problems occurring in production facilities but also in the service industry. The basic scheduling problem can be described as finding for each of the tasks, which are also called jobs, an execution interval on one of the machines that are able to execute it, such that all side-constraints are met; obviously, this should be done in such a way that the resulting solution, which is called a schedule, is best possible, that is, it optimizes a given objective function.
Scheduling problems are encountered in all types of systems, since it is necessary to organize and/or distribute the work between many entities. We find in every book in the literature a definition of a scheduling problem as well as its principal components. Among these definitions we quote the following one (Carlier and Chrétienne 1988):
Scheduling is to forecast the processing of a work by assigning resources to tasks and fixing their start times. [...] The different components of a scheduling problem are the tasks, the potential constraints, the resources and the objective function. [...] The tasks must be programmed to optimize a specific objective [...] of course, often it will be more realistic in practice to consider several criteria.
Another definition has been put forward by Pinedo (2008):
Scheduling concerns the allocation of limited resources to tasks over time. It is a decision-making process that has as a goal the optimization of one or more objectives.
Since the first scheduling paper appeared in 1954, many variants of the basic scheduling problem have been formulated by differentiating between machine environments, side-constraints, and objective functions.
A hybrid flowshop scheduling (HFS) problem, as described by Linn and Zhang (1999), consists of a series of production stages, each of which has several machines operating in parallel. Some stages may have only one machine, but at least one stage must have multiple machines. The HFS is an adequate model for several industrial settings such as semiconductors, electronics manufacturing, airplane engine production, and petrochemical production (Low et al., 2008). The flow of products in the plant is unidirectional. Each product is processed at only one facility in each stage and at one or more stages before it exits the plant. Each stage may have multiple parallel machines. These machines can be identical, uniform, or unrelated. Each job is processed by at most one machine at each stage. A machine can process only one job at a time. Furthermore, a job can be processed by any of the machines and will be processed by a single machine in each stage. The setup times are assumed to be sequence-dependent. Interest in multi-objective scheduling has also been increasing recently but has been limited when compared to research in single criterion problems. In a real manufacturing environment, several objectives frequently need to be considered at the same time. In this study, the following criteria are to be minimized:
Let dj be the due date for the job j, the earliness and tardiness of job j are defined as Ej=max(0,dj−Cj) and Tj= max(0,Cj−dj), respectively, where Cj is the completion time of job j. In particular, the objective function for ET measurement for n jobs can be written as
(1)When we write the objective function in this form, it is clear that earliness and tardiness are penalized at the same rate for all jobs (Su, 2008). Interestingly, the objective of the ET problem fits perfectly to JIT production control policy where an early or a late delivery of an order results in an increase in the production costs.
Key Terms in this Chapter
Multi-Objective Optimization: Multi-objective optimization is an area of multiple criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously.
Electromagnetism-Like Algorithm: Electromagnetism-like algorithm as a population-based metaheuristic is based on an attraction-repulsion mechanism of different particle types to move the particles towards the optimum solution.
Sequence-Dependent Setup Time: In sequence-dependent setup time, the magnitude of time required to do the setup depends on both the immediately preceding and current jobs to be performed on the same machine.
Makespan: The makespan is the total length of the schedule (that is, when all the jobs have finished processing).
Scheduling: Scheduling concerns the allocation of limited resources to tasks over time. It is a decision-making process that has as a goal the optimization of one or more objectives.
Tabu Search: Tabu search (TS) is a local search procedure to explore the solution space beyond local optimality. Memory-based strategy is the property of TS approaches.
Total Earliness and Tardiness: As an objective function, fits perfectly to JIT production control policy where an early or a late delivery of an order results in an increase in the production costs.
Hybrid Flowshop: A hybrid flowshop scheduling problem consists of a series of production stages, each of which has several machines operating in parallel. Some stages may have only one machine, but at least one stage must have multiple machines.