Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.

A heuristic for the two-machine open-shop scheduling problem with transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimize the makespan, provided that preemption is not allowed and the interstage transportation times are involved. This problem is known to be unary NP-hard. We present an algorithm that requires O (n log n) time and provides a worst-case performance ratio of 3/2.

Policy packages as potential routes to urban road pricing in the UK

This paper focuses on urban road pricing as a demand management policy that is often regarded as radical and generally unacceptable. Road pricing often gets delayed or abandoned due to low acceptability. This may be due to the fact that complex interactions and drivers of change affect road transport management and require cooperation within implementation networks. The implementation network is a group of people (referred to as partners and actors) who co-ordinate the introduction of policy tools. The drivers of change include any internal or external influences that have an effect on the time, place, or ‘shape’ of the policy measures being introduced. Demand management measures that focus on 'sustainable transport' usually address a limited set of objectives and are often implemented alone i.e. are not necessarily combined with other policy measures. When combined with other measures, it is not always clear whether the multiple interactions between policy tools and implementation networks have been sufficiently considered. Examples of ongoing implementation of policy package in the UK are the support of road pricing initiatives combined with public transport improvements by the Transport Innovation Fund. The objectives of the paper are twofold. First, we present a review of the UK urban road pricing situation. Second, we contrast the emerging issues against six key implementation factors. The analysis of three existing UK road pricing examples - London, Edinburgh and Durham – shows the importance of combining policy tools. Furthermore, through the above examples and theoretical arguments, we emphasise the additional need of creating and maintaining strong networks when implementing policy packages.