Tham khảo tài liệu 'multiprocessor scheduling part 7', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 170 Multiprocessor Scheduling Theory and Applications . Construction heuristics Often solutions for problems are needed very fast as the problem is an element of a dynamic real world setting. This requirement can generally not be met by exact algorithms like branch and bound algorithm and Lagrangian relaxation method especially when the problem is NP hard. Besides not everyone is interested in the optimal solution. In many cases it is preferable to find a sub-optimal but good solution in a short time which can be obtained by constructive algorithms. Most of the researchers have reported that the above enumerative and Lagranginan algorithms are computationally expensive for larger problem size and tend for other techniques viz. construction heuristics and heuristic search algorithms. Constructive algorithms generate solutions from scratch by adding solution components to an initially empty solution until it is complete. A common approach is to generate a solution in a greedy manner where a dispatching rule decides heuristically which job should be added next to the sequence of jobs that makes up the partial solution. Dispatching rules have been applied consistently to scheduling problems. They are procedures designed to provide good solutions to complex problems in real-time. The term dispatching rule scheduling rule sequencing rule or heuristic are often used synonymously. Panwalker and Iskander 1977 named construction heuristics as scheduling rules and made a survey about different scheduling rules. Blackstone et al. 1982 called as dispatching rules and discussed the state of art of various dispatching rules in the manufacturing operations. Haupt 1989 termed the construction heuristics as priority rules and provides a survey of this type of priority rule based scheduling. Montazer and Van Wassenhove 1990 extensively studied and analysed these scheduling rule using simulation techniques for a flexible manufacturing system. A distinction in dispatching rules can
