On-line algorithms for single machine scheduling with family setup times

The paper considers an on-line single machine scheduling problem where the goal is to minimize the makespan. The jobs are partitioned into families and a setup is performed every time the machine starts processing a batch of jobs of the same family. The scheduler is aware of the number of families and knows the setup time of each family, although information about a job only becomes available when that job is released. We give a lower bound on the competitive ratio of any on-line algorithm. Moreover, for the case of two families, we provide an algorithm with a competitive ratio that achieves this lower bound. As the number of families increases, the lower bound approaches 2, and we give a simple algorithm with a competitive ratio of 2.

Public sector pay in the UK: has the historic pattern of public/private sector pay movements been broken?

The historic pattern of public sector pay movements in the UK has been counter-cyclical with private sector pay growth. Periods of relative decline in public sector pay against private sector movements have been followed by periods of ‘catch-up’ as Government controls are eased to remedy skill shortages or deal with industrial unrest among public servants. Public sector ‘catch up’ increases have therefore come at awkward times for Government, often coinciding with economic downturn in the private sector (Trinder 1994, White 1996, Bach 2002). Several such epochs of public sector pay policy can be identified since the 1970s. The question is whether the current limits on public sector pay being imposed by the UK Government fit this historic pattern or whether the pattern has been broken and, if so, how and why? This paper takes a historical approach in considering the context to public sector pay determination in the UK. In particular the paper seeks to review the period since Labour came into office (White and Hatchett 2003) and the various pay ‘modernisation’ exercises that have been in process over the last decade (White 2004). The paper draws on national statistics on public sector employment and pay levels to chart changes in public sector pay policy and draws on secondary literature to consider both Government policy intentions and the impact of these policies for public servants.