|
...large-scale instances. Therefore, various heuristic methods to solve the problem have been proposed in the literature.
The currently reported approximation algorithms can be categorized into one of two types: constructive methods or improvement methods. Constructive methods include slope-index-based heuristics (Palmer, 1965; Gupta, 1971), the CDS heuristic (Campbell et al., 1970), the RA heuristic (Dannenbring, 1977) and the NEH algorithm (Nawaz et al., 1983). Most of the improvement approaches are based on modern metaheuristics, such as simulated annealing (Osman and Potts, 1989; Ogbu and Smith, 1990), tabu search (Nowicki and Smutnicki, 1996; Grabowski and Pempera, 2001; Grabowski and Wodecki, 2004) and genetic algorithms (Reeves, 1995; Reeves and Yamada, 1998; Wang and Zheng, 2003).
Among the constructive methods, the NEH algorithm is regarded as the best one in practice (Framinan, 2004; Ruiz and Maroto, 2005). The NEH algorithm is usually applied to provide the initial solution for an improvement method such as a tabu search (Nowicki and Smutnicki, 1996; Grabowski and Pempera, 2001; Grabowski and Wodecki, 2004) or a genetic algorithm (Wang and Zheng, 2003). The main drawback of the NEH algorithm is that a total of [n(n + 1)/2] - 1 partial schedules need to be evaluated. Therefore, the running time of the NEH algorithm increases rapidly as the problem size increases. If the running time could be reduced, then the efficiency of those improvement methods that take initial solutions from NEH could also be improved.
To reduce the running time, Taillard (1990) developed a wonderful implementation technique which calculates all the partial schedules in a given iteration in a single step. It significantly reduces the running time of the NEH algorithm, but all the partial schedules still need to be evaluated. However, several recent works (Nowicki and Smutnicki, 1996; Reeves and Yamada, 1998; Grabowski and Pempera, 2001; Grabowski and Wodecki, 2004) show that it helps to reduce the running time if properties of the FSP are introduced into the algorithms. In these papers, the block properties of the FSP are developed and used to reduce the size of the neighborhood in a tabu search. Thus, the running time can be efficiently reduced.
In this paper, it is found that lower bounds of partial makespans could be obtained in time O(1) based on the FSP block properties mentioned above. A pruning procedure is introduced into the NEH algorithm in order to reduce the computational complexity.
This paper is organized as follows. In Section 2, definitions and notation are introduced and the classical NEH algorithm is reviewed. Section 3 presents our improvement of the NEH algorithm. Experimental results are illustrated in Section 4 and Section 5 gives our conclusions.
2. Problem formulation and preliminaries
2.1. The FSP
The FSP is commonly defined as follows. A set J of n jobs must be processed using m machines. The processing time [p.sub.ij] of job i on machine j is given. The following assumptions are normally made in this type of study.
1. All jobs are available for processing at time 0.
2. Each job can only be processed on...
NOTE: All illustrations and photos
have been removed from this article.
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
