Here is a non-optimal algorithm that we tried to schedule jobs online on two machines in order to minimize the makespan. When a job is pending, if there is free space on only one machine, the algorithm will decide to wait for a fraction of time depending on the size of the job. This way, if a bigger job is to come before our algorithm has taken the decision to schedule the previous one, the bigger job will be scheduled on the machine with free space. This algorithm performs quite well in practice, but on a well chosen counter example can behave really badly... :-(.