Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - a polymatroid optimization approach

We consider a variety of preemptive scheduling problems with controllable processing times on a single machine and on identical/uniform parallel machines, where the objective is to minimize the total compression cost. In this paper, we propose fast divide-and-conquer algorithms for these scheduling problems. Our approach is based on the observation that each scheduling problem we discuss can be formulated as a polymatroid optimization problem. We develop a novel divide-and-conquer technique for the polymatroid optimization problem and then apply it to each scheduling problem. We show that each scheduling problem can be solved in $ \O({\rm T}_{\rm feas}(n) \times\log n)$ time by using our divide-and-conquer technique, where n is the number of jobs and Tfeas(n) denotes the time complexity of the corresponding feasible scheduling problem with n jobs. This approach yields faster algorithms for most of the scheduling problems discussed in this paper.

Exploration of the student experience of e-learning: beginning to bridge the learning divide

Introduction This proposal aims, through debate within symposium to explore the student experience of e-learning. The team facilitating the discussion will draw upon their experience of an HEA funded pathfinder project, the main aim of which was to collect learner stories about their experience of using technology in their everyday learning activities at the University of Greenwich across a range of programmes, levels, locations and student groups. Method The project design responded to the growing body of student voice literature and then utilised and built upon the JISC-funded studies that focussed on understanding the learner perspectives on the role of technology in learning, namely: • the LEX study which investigated a broad spectrum of technology use by eliciting rich data about learners’ feelings, beliefs and intentions towards e-learning (Creanor et al, 2006); • the LXP studies which explored disciplinary differences in uses of technology by university students through a variety of methodologies (Conole et al, 2006). Results The symposium will be organised as a round table discussion that will be structured into three sections: • Designing an online survey tool, and the results of our survey. • Exploring student stories. • What can learned from the project and taking the findings back to enhance learning. To stimulate discussion each section will start by asking the participants to discuss and debate a particular question, this will be followed by an interactive presentation by the respective member of the project team who will share the findings of the project and invite contributions to the resulting discussion from personal perspectives. The questions are: • What is effective learning within a context of digital technology? • What are the myths and truths about the identity of today's learners? • What practical changes need to happen in order to see real change? Conclusion The final section of the symposium will invite contributions from the participants in order to collate the views and perspectives of all the participants in order to focus the discussion on the following: • The issues that have arisen as a result of the round table debates. • New speculative approaches to enhancing the student experience. • A controversial stand to the future of Higher Education teaching and learning and the role and integration of technology within that education. The symposium will provide an opportunity to explore the predictive value of Student Experience of E-Learning Laboratory (SEEL) project.

Rethinking the digital divide

The ALT-C 2008 conference theme of 'Re-thinking the Digital Divide' was highlighted in relation to the Greenwich conference theme of ‘Learning from the Learners' Experience of eLearning’ in a plenary session in which the Co-Chair of ALT-C 2008 introduced the forthcoming ALT-C conference at Leeds.

A combined evolutionary search and multilevel optimisation approach to graph-partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

Numerical and experimental studies of a substructural identification strategy

For structural health monitoring it is impractical to identify a large structure with complete measurement due to limited number of sensors and difficulty in field instrumentation. Furthermore, it is not desirable to identify a large number of unknown parameters in a full system because of numerical difficulty in convergence. A novel substructural strategy was presented for identification of stiffness matrices and damage assessment with incomplete measurement. The substructural approach was employed to identify large systems in a divide-and-conquer manner. In addition, the concept of model condensation was invoked to avoid the need for complete measurement, and the recovery process to obtain the full set of parameters was formulated. The efficiency of the proposed method is demonstrated numerically through multi-storey shear buildings subjected to random force. A fairly large structural system with 50 DOFs was identified with good results, taking into consideration the effects of noisy signals and the limited number of sensors. Two variations of the method were applied, depending on whether the sensor could be repositioned. The proposed strategy was further substantiated experimentally using an eight-storey steel plane frame model subjected to shaker and impulse hammer excitations. Both numerical and experimental results have shown that the proposed substructural strategy gave reasonably accurate identification in terms of locating and quantifying structural damage.

Drawing the net: internet identification, internet use, and the image of internet users

Theory and research suggest that Internet identification may account for some of the gender divide in Internet use. Internet identification is a type of domain identification, and is inherently bound with images of those who use the Internet, a domain traditionally conceived as masculine. Combining the “draw an Internet user” test with an Internet identification scale, this study tests two hypotheses: participants drawing gender-concordant images will (i) identify with and (ii) use the Internet more than those drawing gender-discordant images. Participants were 371 students (121 males, 250 females) from three universities in the United Kingdom and Australia. The need to challenge masculinized images of the Internet is discussed.

Student Experience of E-Learning (SEEL)

The Student Experience of E-Learning project (SEEL) was an institutional response to the university’s HEA/JISC Benchmarking exercise (Ryan and Kandler, 2007). The study had a social constructivist approach which recognised the importance of listening to the student voice (JISC 2007) within the University of Greenwich context, to interpret the student experience of e-learning. Nearly 1000 students responded to an online survey on their approaches to, and their use of, learning technology. The quantitative and qualitative questions used included identifying study patterns, using specific online tools, within the context of learning and beyond, and student’s attitudes towards using e-learning in their studies. Initially, individual responses to questions were analysed in depth, giving a general indication of the student experience. Further depth was applied through a filtering mechanism, beginning with a cross-slicing of individual student responses to produce cameos. Audio logs and individual interviews were drawn from these cameos. Analysis of the cameos is in progress but has already revealed some unexpected results. There was a mismatch between students’ expectations of the university’s use of technology and their experiences and awareness of its possible use in other contexts. Students recognised the importance of social interaction as a vehicle for learning (Vygotsky 1978, Bruner 2006) but expressed polarised views on the use of social networking sites such as Facebook for e-learning. Their experiences in commercial contexts led them to see the university VLE as unimaginative and the tutors’ use of it as lacking in vision. Whereas analysis of the individual questions provided a limited picture, the cameos gave a truer reflection of the students lived experiences and identified a gulf between the university’s provision and the students’ expectation of e-learning and their customary use of technology. However it is recognised that the very nature of an online survey necessarily excludes students who chose not to engage, either through lack of skills or through disillusionment and this would constitute a separate area for study.