Shop scheduling problems under precedence constraints

The paper considers a scheduling model that generalizes the well-known open shop, flow shop, and job shop models. For that model, called the super shop, we study the complexity of finding a time-optimal schedule in both preemptive and non-preemptive cases assuming that precedence constraints are imposed over the set of jobs. Two types of precedence rela-tions are considered. Most of the arising problems are proved to be NP-hard, while for some of them polynomial-time algorithms are presented.

Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment

The paper considers the single machine due date assignment and scheduling problems with n jobs in which the due dates are to be obtained from the processing times by adding a positive slack q. A schedule is feasible if there are no tardy jobs and the job sequence respects given precedence constraints. The value of q is chosen so as to minimize a function ϕ(F,q) which is non-decreasing in each of its arguments, where F is a certain non-decreasing earliness penalty function. Once q is chosen or fixed, the corresponding scheduling problem is to find a feasible schedule with the minimum value of function F. In the case of arbitrary precedence constraints the problems under consideration are shown to be NP-hard in the strong sense even for F being total earliness. If the precedence constraints are defined by a series-parallel graph, both scheduling and due date assignment problems are proved solvable in time, provided that F is either the sum of linear functions or the sum of exponential functions. The running time of the algorithms can be reduced to if the jobs are independent. Scope and purpose We consider the single machine due date assignment and scheduling problems and design fast algorithms for their solution under a wide range of assumptions. The problems under consideration arise in production planning when the management is faced with a problem of setting the realistic due dates for a number of orders. The due dates of the orders are determined by increasing the time needed for their fulfillment by a common positive slack. If the slack is set to be large enough, the due dates can be easily maintained, thereby producing a good image of the firm. This, however, may result in the substantial holding cost of the finished products before they are brought to the customer. The objective is to explore the trade-off between the size of the slack and the arising holding costs for the early orders.

Building temporal constraints into knowledge bases for process control: an examination [Reply to author's reply]

Reply to author's reply

Non-preemptive two-machine open shop scheduling with non-availability constraints

We study a two-machine open shop scheduling problem, in which the machines are not continuously available for processing. No preemption is allowed in the processing of any operation. The objective is to minimize the makespan. We consider approximability issues of the problem with more than one non-availability intervals and present an approximation algorithm with a worst-case ratio of 4/3 for the problem with a single non-availability interval.

Scheduling problems for parallel dedicated machines under multiple resource constraints

The paper considers scheduling problems for parallel dedicated machines subject to resource constraints. A fairly complete computational complexity classification is obtained, a number of polynomial-time algorithms are designed. For the problem with a fixed number of machines in which a job uses at most one resource of unit size a polynomial-time approximation scheme is offered.

Flow shop scheduling problems under machine–dependent precedence constraints

The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems with two and three machines is obtained.

Single machine scheduling and due date assignment under series-parallel precedence constraints

We consider a single machine due date assignment and scheduling problem of minimizing holding costs with no tardy jobs tinder series parallel and somewhat wider class of precedence constraints as well as the properties of series-parallel graphs.

On Hamilton cycles in locally connected graphs with vertex degree constraints

It is shown that every connected, locally connected graph with the maximum vertex degree Δ(G)=5 and the minimum vertex degree δ(G)3 is fully cycle extendable. For Δ(G)4, all connected, locally connected graphs, including infinite ones, are explicitly described. The Hamilton Cycle problem for locally connected graphs with Δ(G)7 is shown to be NP-complete

Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation

We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

Approximation results for flow shop scheduling problems with machine availability constraints

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

Hazard and risk assessment from Hurricane Ivan (2004) in Grenada using Geographical Information Systems and remote sensing

Hurricanes are destructive storms with strong winds, intense storm surges, and heavy rainfall. The resulting impact from a hurricane can include structural damage to buildings and infrastructure, flooding, and ultimately loss of human life. This paper seeks to identify the impact of Hurricane Ivan on the aected population of Grenada, one of the Caribbean islands. Hurricane Ivan made landfall on 7th September 2004 and resulted in 80% of the population being adversely aected. The methods that were used to model these impacts involved performing hazard and risk assessments using GIS and remote sensing techniques. Spatial analyses were used to create a hazard and a risk map. Hazards were identied initially as those caused by storm surges, severe winds speeds, and flooding events related to Hurricane Ivan. These estimated hazards were then used to create a risk map. An innovative approach was adopted, including the use of hillshading to assess the damage caused by high wind speeds. This paper explains in detail the methodology used and the results produced.

Reaching across organisational, sectoral and geographical boundaries: exploring the learning potential of an EU cross-border project

Research This paper outlines some of the key findings from an evaluation of the project and demonstrates that EC funded projects such as this, which seek to promote cross border collaboration and understanding (i.e. across organisational, sectoral and geographical boundaries) offer considerable learning potential – not least about variances in health politics across different communities. However, for this learning to be realised a comprehensive system of knowledge management needs to be an integral part of project planning alongside a system for sustaining embryonic professional networks. The concept of managing relationships was also a key part of the projects success. Executing a project funded by the EU demands the development of complex organisational skills to negotiate all the administrative challenges en route to successful completion and this project in particular relied for its success on the development of social relationships of trust and mutual respect across national, professional and social boundaries. Context A three–year European Commission funded project designed to exchange a wide range of staff (professional semiprofessional and voluntary staff in health and social care) project led by the University of Greenwich (UK) and the Université Catholique de Lille, France was completed this year (February 2008). The project was complex because it involved working in different national contexts, was multi-disciplinary, and demanded the negotiation of multiple boundaries. Theories A mixed method evaluation including written reports gathered immediately after each exchange visit and a post hoc series of individual interviews and focus groups was conducted in order to gain qualitative information (from the participants perspective) on their experiences and to identify any learning gained. Results Analysis of the data provided evidence of learning on a number of levels; personally, inter and intra professionally and organisationally as well as across sectors and also from a project management perspective. The learning crystallised around the extent of the differences noted by the participants between the UK and the French health and social care systems despite geographical proximity, common membership of the EU and many shared challenges in health and social care. The extent of these differences, noted at every level from policy to practice proved a rich source for reflection on organisational philosophies, ways of working, distribution of resources, professional roles and autonomy and professional registration and mobility - in short on health politics at ‘macro’ and ‘micro’ levels.

Bridging the gap with teamwork: collaborative leadership for communities of practice in the learning and skills sector

Collaborative approaches in leadership and management are increasingly acknowledged to play a key role in successful institutions in the learning and skills sector (LSS) (Ofsted, 2004). Such approaches may be important in bridging the potential 'distance' (psychological, cultural, interactional and geographical) (Collinson, 2005) that may exist between 'leaders' and 'followers', fostering more democratic communal solidarity. This paper reports on a 2006-07 research project funded by the Centre for Excellence in Leadership (CEL) that aimed to collect and analyse data on 'collaborative leadership' (CL) in the learning and skills sector. The project investigated collaborative leadership and its potential for benefiting staff through trust and knowledge-sharing in communities of practice (CoPs). The project forms part of longer-term educational research investigating leadership in a collaborative inquiry process (Jameson et al., 2006). The research examined the potential for CL to benefit institutions, analysing respondents' understanding of and resistance to collaborative practices. Quantitative and qualitative data from senior managers and lecturers was analysed using electronic data in SPSS and Tropes Zoom. The project aimed to recommend systems and practices for more inclusive, diverse leadership (Lumby et al., 2005). Collaborative leadership has increasingly gained international prominence as emphasis shifted towards team leadership beyond zero-sum 'leadership'/ 'followership' polarities into more mature conceptions of shared leadership spaces, within which synergistic leadership spaces can be mediated. The relevance of collaboration within the LSS has been highlighted following a spate of recent government-driven policy developments in FE. The promotion of CL addresses concerns about the apparent 'remoteness' of some senior managers, and the 'neo-management' control of professionals which can increase 'distance' between leaders and 'followers' and may de-professionalise staff in an already disempowered sector. Positive benefit from 'collaborative advantage' tends to be assumed in idealistic interpretations of CL, but potential 'collaborative inertia' may be problematic in a sector characterised by rapid top-down policy changes and continuous external audit and surveillance. Constant pressure for achievement against goals leaves little time for democratic group negotiations, despite the desires of leaders to create a more collaborative ethos. Yet prior models of intentional communities of practice potentially offer promise for CL practice to improve group performance despite multiple constraints. The CAMEL CoP model (JISC infoNet, 2006) was linked to the project, providing one practical way of implementing CL within situated professional networks.The project found that a good understanding of CL was demonstrated by most respondents, who thought it could enable staff to share power and work in partnership to build trust and conjoin skills, abilities and experience to achieve common goals for the good of the sector. However, although most respondents expressed agreement with the concept and ideals of CL, many thought this was currently an idealistically democratic, unachievable pipe dream in the LSS. Many respondents expressed concerns with the 'audit culture' and authoritarian management structures in FE. While there was a strong desire to see greater levels of implementation of CL, and 'collaborative advantage' from the 'knowledge sharing benefit potential' of team leadership, respondents also strongly advised against the pitfalls of 'collaborative inertia'. A 'distance' between senior leadership views and those of staff lower down the hierarchy regarding aspects of leadership performance in the sector was reported. Finally, the project found that more research is needed to investigate CL and develop innovative methods of practical implementation within autonomous communities of professional practice.