Наказать нужно парочку для наглядности. Выговоры объявить с пояснениями, что и уволить работодатель имеет право за такие дела. И премию не дать, всем кто опаздывает и рано уходит. Может поможет. Но только при этом нужно не забывать, что исключений из правил быть не должно. Нельзя - значит всем!
НО: На одной из прошлых моих работ премия была столь незначительна, что было абсолютно "не больно" ее потерять, поэтому приходили с опозданиями, писали объяснительные каждый раз.

Так может им просто делать нечего? :redface:
А чего тогда в офисе сидеть? На случай "случайных" клиентов можно дежурство организовать, а остальные пусть идут с Богом...