Обзор задач календарного планирования при параллельной пакетной обработке (p-пакетах)

При параллельной пакетной обработке на заданной пакетной машине одновременно обрабатывается несколько заданий. Образованный в результате пакет называется p-пакетом. Пакетирование может привести к снижению производственных затрат, однако способ группировки заданий в пакеты может улучшать или ухудшать сроки поставки продукции. Планирование заданий на пакетных машинах, помимо традиционных решений о назначении и последовательности, требует принятия решений о группировке. Параллельная пакетная обработка имеет важное значение в различных областях, включая производство полупроводников, самолетостроение, производство обуви и здравоохранение. В статье представлен обзор литературы по параллельной пакетной обработке, основное внимание уделено детерминированному планированию. Предлагается таксономия задач параллельной пакетной обработки, в которой различаются совместимый случай, когда для формирования пакета могут использоваться все задания, и случай несовместимых семейств, когда в пакет могут входить только задания из одного семейства. Рассматриваются критерии, связанные с длительностью выполнения всех заданий, временем пребывания и сроками выполнения. Обсуждаются подходы к планированию для одиночных машин, параллельных машин и других производственных сред, таких как поточные и цеховые производства. Помимо анализа опубликованных ранее и современных работ, рассматриваются также последние тенденции в планировании заданий на машинах с параллельной пакетной обработкой. Наконец, обсуждаются перспективные направления дальнейших исследований в области планирования p-пакетов.