В текстах официально-делового стиля принято сначала указывать родовое понятие (улица, проспект, переулок и т. п.), а затем видовое (собственно наименование): ул. Ставропольская. Однако грамматическим нормам русского языка соответствует иной порядок элементов: если наименование выражено прилагательным, то оно пишется после родового понятия (Садовая улица, Фельдмаршальский проспект, Горлов переулок и т. п.), а если существительным в родительном падеже — то после (улица Москвиной, плащадь Пролетарской Диктатуры). Нарушение этого естественного порядка, кстати, может приводить к непониманию этимологии наименования. Например, в Петербурге есть Зеленина улица (где Зеленина — от зелейная, так как улица шла к пороховому заводу), но улица Зайцева (так как названа в честь участника Великой Отечественной войны генерал-майора П. А. Зайцева).

В подобных составных обозначениях военных чинов и званий первая часть обычно не склоняется: генерал-майора, генерал-лейтенанта, капитан-лейтенанта и т. п.

Первая часть составных обозначений военных и государственных чинов и званий не склоняется: генерал-лейтенанта, генерал-майора.

Правильно: генерал-майора. Подробнее см. в "Письмовнике".