?
Лексикографический алгоритм для решения конвейерной задачи
The optimal schedule, on the one hand, is a practical necessity to conserve resources, for example, problem in the multiprocessor computing systems. On the other hand, many of the scheduling problems are NP-hard and can not be solved exactly in polynomial time. Flow shop scheduling problem is the one of the most famous optimization problem. The scheduling problem is to find sequences of jobs on given machines with the objective of minimizing some function of the job completion times. All jobs pass through all machines in the same order. There is exact polynomial Johnson's algorithm for two machines. But it is NP-hard problem in case of an arbitrary number of machines. In practice, either trivial exhaustive search algorithms with exponential complexity are used when the number of jobs is not large, either some fast approximation algorithms, for example, the frontal algorithm. In this paper a new approach for the approximate solution of the flow shop scheduling problem is proposed. It uses double sorting. For each job, the stage durations are previously sorted in descending order. Stage numbers are written as a character string (classification). These job classifications lexicographically are sorted in descending order. Therefore, jobs with the longest last stage will be executed firstly. Then work with the longest penultimate stage will be executed and so on. It means that the last machine, and then the penultimate machine etc. at the beginning are loaded with the largest jobs. It allows them to avoid idle waiting for the next jobs. The practical implications of this paper is higher accuracy of the lexicographical algorithm compared with the frontal algorithm to works, where the number of jobs more than the number of stages, however the frontal algorithm is faster. The paper provides data about accuracy and execution time of these algorithms depending on the number of jobs and stages.