Article Preview
TopIntroduction
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.