Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Унифицированное планирование машин (также называемое равномерным планированием машин или связанным планированием машин) — это задача оптимизации в компьютерных науках и исследованиях операций. Это вариант оптимального планирования заданий. Дано n заданий J1, J2, ..., Jn с различным временем обработки, которые необходимо запланировать на m различных машинах. Цель состоит в минимизации времени завершения (makespan) — общего времени, необходимого для выполнения расписания. Время, необходимое машине i для обработки задания j, обозначается как pi,j. В общем случае времена pi,j не связаны, и возможна любая матрица положительных времен обработки. В специфическом варианте, называемом унифицированным планированием машин, некоторые машины равномерно быстрее других. Это означает, что для каждой машины i существует коэффициент скорости si, и время выполнения задания j на машине i равно pi,j = pj / si. В стандартной трехпольной нотации для задач оптимального планирования заданий унифицированный вариант машины обозначается Q в первом поле. Например, задача, обозначенная как "Q||", — это задача унифицированного планирования машин без ограничений, где целью является минимизация максимального времени завершения. Особым случаем унифицированного планирования машин является планирование идентичных машин, в которых все машины имеют одинаковую скорость. Этот вариант обозначается P в первом поле. В некоторых вариантах задачи вместо минимизации максимального времени завершения желательно минимизировать среднее время завершения (в среднем по всем n заданиям); оно обозначается как Q||. В более общем смысле, когда некоторые задания важнее других, может быть желательно минимизировать взвешенное среднее время завершения, где каждое задание имеет разный вес. Это обозначается как Q||.
Uniform machine scheduling (also called uniformly related machine scheduling or related machine scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given n jobs J1, J2, , Jn of varying processing times, which need to be scheduled on m different machines. The goal is to minimize the makespan the total time required to execute the schedule. The time that machine i needs in order to process job j is denoted by pi,j. In the general case, the times pi,j are unrelated, and any matrix of positive processing times is possible. In the specific variant called uniform machine scheduling, some machines are uniformly faster than others. This means that, for each machine i, there is a speed factor si, and the run time of job j on machine i is pi,j = pj / si. In the standard three field notation for optimal job scheduling problems, the uniform machine variant is denoted by Q in the first field. For example, the problem denoted by " Q||" is a uniform machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. A special case of uniform machine scheduling is identical machines scheduling, in which all machines have the same speed. This variant is denoted by P in the first field. In some variants of the problem, instead of minimizing the maximum completion time, it is desired to minimize the average completion time (averaged over all n jobs); it is denoted by Q||. More generally, when some jobs are more important than others, it may be desired to minimize a weighted average of the completion time, where each job has a different weight. This is denoted by Q||.