Ordonarea lucrărilor monotone în problema Mxn Bellman-Johnson

Abstract

Bellman-Johnson’s Mxn scheduling problem with monotone (no decreasing, constant or no increasing) jobs is investigated. Rules for optimal ordering of monotone jobs in the schedule, which contain no monotone jobs too, are proposed. Partial ordering of jobs permits to reduce the volume of calculus and often to improve the quasi-optimal schedules. If all n jobs are monotone, particular cases are defined and rules for optimal schedules are proposed.

Problema Mxn Bellman-Johnson de ordonare a lucrărilor în sisteme secvenţiale, la care se reduce optimizarea diverselor procese tehnologice, nu este încă soluţionată. Sunt obţinute soluţii doar pentru unele cazuri particulare şi propuşi algoritmi de soluţionare cuazioptimă a problemei generale. Astfel, sunt soluţionate: problema 2xn, patru cazuri particulare pentru problema 3xn, un caz particular pentru problema 4xn şi câteva cazuri particulare pentru problema Mxn; algoritmi cuazioptimi sunt propuşi. În această lucrare se cercetează unele cazuri particulare ale problemei Mxn, ce ţin de ordonarea parţială sau totală a lucrărilor monotone (nedescrescătoare, constante sau necrescătoare).