Ўзбекистон алоқа ва ахборотлаштириш агентлиги тошкент ахборот технологиялари университети самарқанд филиали

Дастлабки кадам. Элементлари операцияларни бажариш вактларидан иборат , , матрицани тузамиз ва биринчи кадамга утамиз.
Биринчи кадам. матрицада минимал элементни аниклаймиз. Агар у биринчи сатрда жойлашган булса (биринчи сатр биринчи машинага мос келгани учун) шу ишни биринчи булиб, иккинчи сатрда жойлашган булса, уни охирида бажарамиз. Иккинчи кадамга утамиз.
Иккинчи кадам. Бажариладиган ишга таълукли тартибланган операцияларни карашдан чикарамиз. Агар шундан кейин хосил булган матрицанинг элементлар туплами буш булса, масала ечилди. Акс холда биринчи кадамга кайтамиз.
Шундай килиб, оптимал жадвал тузилиши учун биринчи ва иккинчи кадамлар марта кайтарилиши керак. Агар булса ишни буйича хам буйича хам тартиблаш мумкин.
Мисол. Бешта иш берилган булиб, улар олдин биринчи кейин эса иккинчи машинада бажарилиши керак булган операциялардан иборат. Операцияларни бажариш вактлари куйидаги жадвалда берилган.

Р M	P1	P2	P3	P4	P5
M1 M2	5 2	3 1	4 3	1 2	2 3

Джонсон алгоритми буйича операцияларни бажариш тартибини аниклаймиз.

сонларнинг энг кичиги булиб, у биринчи сатрда жойлашган. Шунинг учун дастлаб иш бажарилади. Шунга мос устунни учириб, кичрайтирилган матрицада энг кичик элемент ни топамиз. Бу элемент иккинчи сатрда жойлашганлиги учун га мос иш охирида бажарилади. Энди устунни хам чикариб, хосил булган матрицада энг кичик элемент ни топамиз. Демак, дан кейин иш бажарилади. Уни хам матрицадан чикариб факат ва устунлар катнашган матрицага эга буламиз. Улардаги энг кичик элемент иккинчи сатрда жойлашгани учун иш дан кейин бажарилади. Шундай килиб, бажариладиган ишлар тартиби (оптимал жадвал) куйидагича булади: .
Юкорида каралган жадвал тузиш масаласи факат иккита машина булган хол учун осон ечилади. Умумий холда (баъзи хусусий холлар мустасно) бу масалани ечиш учун махсус математик усуллардан фойдаланишга туђри келади ва жуда куп хисоблаш кийинчиликларини хал килиш оркали максадга эришиш мумкин.