It always puzzled me that a simpler algorithm has never been considered.

Passengers with heavier hand luggage or more than one piece (say hand-luggage and laptop) should be given back-seats. Anyone without hand luggage should be placed at the front seats.