A Pareto-Optimal Solution for a Multi-Objective Scheduling Problem with Periodic Maintenance Requirement

A Pareto-Optimal Solution for a Multi-Objective Scheduling Problem with Periodic Maintenance Requirement

Deniz Mungan (Cyprus Mobile Telecommunication Ltd, Cyprus), Junfang Yu (Southern Methodist University, USA), Bhaba R. Sarker (Louisiana State University, USA) and Mohammad Anwar Rahman (University of Southern Mississippi, USA)
DOI: 10.4018/joris.2012040102
OnDemand PDF Download:
List Price: $37.50


A Pareto-optimal solution is developed in this paper for a scheduling problem on a single machine with periodic maintenance and non-preemptive jobs. Most of the scheduling problems address only one objective function, while in the real world, such problems are always associated with more than one objective. In this paper, both multi-objective functions and multi-maintenance periods are considered for a machine scheduling problem. To avoid complexities, multiple objective functions are consolidated and transformed into a single objective function after they are weighted and assigned proper weighting factors. In addition, periodic maintenance schedules are also considered in the model. The objective of the model addressed is to minimize the weighted function of the total job flow time, the maximum tardiness, and the machine idle time in a single machine problem with periodic maintenance and non-preemptive jobs. An algorithm is developed to solve this multiple criterion problem and to construct the Pareto-set. The parametric analysis of the trade-offs of all solutions with all possible weighted combination of the criteria is performed. A neighborhood search heuristic is also developed. Results are provided to explore the best schedule among all the Pareto-optimality sets and to compare the result of the modified Pareto-optimality algorithm with the result of the neighborhood search heuristic.
Article Preview


Most real-world scheduling problems are naturally multi-criterion. However, due to the lack of suitable solution techniques such problems are usually transformed into a single-objective problem. A solution is called Pareto-optimal if it is not possible to decrease the value of one objective without increasing the value of the other (Pinedo, 2002). The difficulty that arises with this approach is the rise of a set of Pareto-optimal solutions, instead of a single optimum solution.

There are several approaches that deal with the multi-objective problems. Traditionally, the most common way is to combine the multiple criteria into a single scalar value by using weighted aggregating functions according to the preferences set by the scheduler (or decision-makers) and then to find a compromise solution that reflects these preferences (Deb, 2001). However, in many real scenarios involving multi-criterion scheduling problems, it is preferable to present a set of promising solutions to the decision-makers so that the most adequate schedule can be chosen. This has increased the interest in investigating the application of Pareto-optimization techniques to multi-criterion scheduling problems. The aim in Pareto-optimization is to find a set of compromised solutions that represent a good approximation to the Pareto-optimality (Pinedo, 2002). In recent years, several algorithms proposed for Pareto-optimization have been published because multi-objective optimization problems exist in almost any domain (Kasprzak & Lewis, 2001, Gupta & Sivakumar, 2002, Kulturel-Konak, Coit, & Baheranwala, 2008).

In addition to multiple objectives, periodic maintenance is also considered for this scheduling problem. An unexpected breakdown will make the shop behavior hard to predict, and thereby will reduce the efficiency of the production system. Maintenance can reduce the breakdown rate with minor sacrifices in production (Liao & Chen, 2003).

In literature, there are several approaches for handling multi-criterion problems. Branch and bound technique is one of those approaches that could obtain a better solution for such problems. Branch and bound technique explores all the possible enumerations to find the best sequence with minimum value in O(2*) time complexity (Baker, 1998, p. 3.13). Liao and Chen (2003) address minimizing the maximum tardiness of jobs in a periodically maintained single machine problem. A branch and bound algorithm is developed to find the optimal solution, and a heuristic solution is also devised for handling the large problem. The larger is the neighborhood, the better is the quality of the locally optimal solutions, and the greater is the accuracy of the final solution. At the same time, searching larger neighborhoods requires more time at each stage. Because of many runs of a neighborhood search algorithm, longer execution times per run lead to fewer runs within a specified time. For this reason, a larger neighborhood can produce a more effective heuristic algorithm only if the larger neighborhood can be searched in a very efficient manner. A survey of large-scale neighborhood search algorithms can be found in Ahuja et al. (2002). For the single-machine problem, Adiri et al. (1991) assumes two cases of a breakdown, that is, the resumable and non-resumable cases assuming that machine idle time is unknown and follows a probabilistic distribution pattern. Mosheiov (1994) solves the minimization of total completion time for two-parallel-machine-scheduling problem by assuming each machine is available in a specified interval. Lee (1991) also studies in this area for other machine configurations including single and parallel machines.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing