A hybrid shifting bottleneck procedure algorithm for the parallel-machine job-shop scheduling problem

In practice, parallel-machine job-shop scheduling (PMJSS) is very useful in the development of standard modelling approaches and generic solution techniques for many real-world scheduling problems. In this paper, based on the analysis of structural properties in an extended disjunctive graph model, a hybrid shifting bottleneck procedure (HSBP) algorithm combined with Tabu Search metaheuristic algorithm is developed to deal with the PMJSS problem. The original-version SBP algorithm for the job-shop scheduling (JSS) has been significantly improved to solve the PMJSS problem with four novelties: i) a topological-sequence algorithm is proposed to decompose the PMJSS problem into a set of single-machine scheduling (SMS) and/or parallel-machine scheduling (PMS) subproblems; ii) a modified Carlier algorithm based on the proposed lemmas and the proofs is developed to solve the SMS subproblem; iii) the Jackson rule is extended to solve the PMS subproblem; iv) a Tabu Search metaheuristic algorithm is embedded under the framework of SBP to optimise the JSS and PMJSS cases. The computational experiments show that the proposed HSBP is very efficient in solving the JSS and PMJSS problems.

Young adults’ accounts of scientific knowledge when responding to a television news report of contested science

This paper reports one aspect of a study of 28 young adults (18–26 years) engaging with the uncertain (contested) science of a television news report about recent research into mobile phone health risks. The aim of the study was to examine these young people’s ‘accounts of scientific knowledge’ in this context. Seven groups of friends responded to the news report, initially in focus group discussions. Later in semi-structured interviews they elaborated their understanding of the nature of science through their explanations of the scientists’ disagreement and described their mobile phone safety risk assessments. This paper presents their accounts in terms of their views of the nature of science and their concept understanding. Discussions were audio-recorded then analysed by coding the talk in terms of issues raised, which were grouped into themes and interpreted in terms of a moderate social constructionist theoretical framing. In this context, most participants expressed a ‘common sense’ view of the nature of science, describing it as an atheoretical, technical procedure of scientists testing their personal opinions on the issue, subject to the influence of funding sponsors. The roles of theory and data interpretation were largely ignored. It is argued that the nature of science understanding is crucial to engagement with contemporary socioscientific issues, particularly the roles of argumentation, theory, data interpretation, and the distinction of science from common sense. Implications for school science relate primarily to nature of science teaching and the inclusion of socioscientific issues in school science curricula. Future research directions are considered.

Scheduling a flow-shop with combined buffer conditions

In this paper, No-Wait, No-Buffer, Limited-Buffer, and Infinite-Buffer conditions for the flow-shop problem (FSP) have been investigated. These four different buffer conditions have been combined to generate a new class of scheduling problem, which is significant for modelling many real-world scheduling problems. A new heuristic algorithm is developed to solve this strongly NP-hard problem. Detailed numerical implementations have been analysed and promising results have been achieved.

Metaheuristics for minimizing the makespan of the dynamic shop scheduling problem

For the shop scheduling problems such as flow-shop, job-shop, open-shop, mixed-shop, and group-shop, most research focuses on optimizing the makespan under static conditions and does not take into consideration dynamic disturbances such as machine breakdown and new job arrivals. We regard the shop scheduling problem under static conditions as the static shop scheduling problem, while the shop scheduling problem with dynamic disturbances as the dynamic shop scheduling problem. In this paper, we analyze the characteristics of the dynamic shop scheduling problem when machine breakdown and new job arrivals occur, and present a framework to model the dynamic shop scheduling problem as a static group-shop-type scheduling problem. Using the proposed framework, we apply a metaheuristic proposed for solving the static shop scheduling problem to a number of dynamic shop scheduling benchmark problems. The results show that the metaheuristic methodology which has been successfully applied to the static shop scheduling problems can also be applied to solve the dynamic shop scheduling problem efficiently.

A fast tabu search algorithm for the group shop scheduling problem

Three types of shop scheduling problems, the flow shop, the job shop and the open shop scheduling problems, have been widely studied in the literature. However, very few articles address the group shop scheduling problem introduced in 1997, which is a general formulation that covers the three above mentioned shop scheduling problems and the mixed shop scheduling problem. In this paper, we apply tabu search to the group shop scheduling problem and evaluate the performance of the algorithm on a set of benchmark problems. The computational results show that our tabu search algorithm is typically more efficient and faster than the other methods proposed in the literature. Furthermore, the proposed tabu search method has found some new best solutions of the benchmark instances.

Metaheuristics for the mixed shop scheduling problem

In this paper, three metaheuristics are proposed for solving a class of job shop, open shop, and mixed shop scheduling problems. We evaluate the performance of the proposed algorithms by means of a set of Lawrence’s benchmark instances for the job shop problem, a set of randomly generated instances for the open shop problem, and a combined job shop and open shop test data for the mixed shop problem. The computational results show that the proposed algorithms perform extremely well on all these three types of shop scheduling problems. The results also reveal that the mixed shop problem is relatively easier to solve than the job shop problem due to the fact that the scheduling procedure becomes more flexible by the inclusion of more open shop jobs in the mixed shop.

A comparative study of algorithms for the flowshop scheduling problem

In this paper, we propose three meta-heuristic algorithms for the permutation flowshop (PFS) and the general flowshop (GFS) problems. Two different neighborhood structures are used for these two types of flowshop problem. For the PFS problem, an insertion neighborhood structure is used, while for the GFS problem, a critical-path neighborhood structure is adopted. To evaluate the performance of the proposed algorithms, two sets of problem instances are tested against the algorithms for both types of flowshop problems. The computational results show that the proposed meta-heuristic algorithms with insertion neighborhood for the PFS problem perform slightly better than the corresponding algorithms with critical-path neighborhood for the GFS problem. But in terms of computation time, the GFS algorithms are faster than the corresponding PFS algorithms.

Using operations research methodologies to improve operating theatre scheduling

A hospital consists of a number of wards, units and departments that provide a variety of medical services and interact on a day-to-day basis. Nearly every department within a hospital schedules patients for the operating theatre (OT) and most wards receive patients from the OT following post-operative recovery. Because of the interrelationships between units, disruptions and cancellations within the OT can have a flow-on effect to the rest of the hospital. This often results in dissatisfied patients, nurses and doctors, escalating waiting lists, inefficient resource usage and undesirable waiting times. The objective of this study is to use Operational Research methodologies to enhance the performance of the operating theatre by improving elective patient planning using robust scheduling and improving the overall responsiveness to emergency patients by solving the disruption management and rescheduling problem. OT scheduling considers two types of patients: elective and emergency. Elective patients are selected from a waiting list and scheduled in advance based on resource availability and a set of objectives. This type of scheduling is referred to as ‘offline scheduling’. Disruptions to this schedule can occur for various reasons including variations in length of treatment, equipment restrictions or breakdown, unforeseen delays and the arrival of emergency patients, which may compete for resources. Emergency patients consist of acute patients requiring surgical intervention or in-patients whose conditions have deteriorated. These may or may not be urgent and are triaged accordingly. Most hospitals reserve theatres for emergency cases, but when these or other resources are unavailable, disruptions to the elective schedule result, such as delays in surgery start time, elective surgery cancellations or transfers to another institution. Scheduling of emergency patients and the handling of schedule disruptions is an ‘online’ process typically handled by OT staff. This means that decisions are made ‘on the spot’ in a ‘real-time’ environment. There are three key stages to this study: (1) Analyse the performance of the operating theatre department using simulation. Simulation is used as a decision support tool and involves changing system parameters and elective scheduling policies and observing the effect on the system’s performance measures; (2) Improve viability of elective schedules making offline schedules more robust to differences between expected treatment times and actual treatment times, using robust scheduling techniques. This will improve the access to care and the responsiveness to emergency patients; (3) Address the disruption management and rescheduling problem (which incorporates emergency arrivals) using innovative robust reactive scheduling techniques. The robust schedule will form the baseline schedule for the online robust reactive scheduling model.

Alternative primary sources for studying Australian television history : an annotated list of online private collections

It is possible to write many different histories of Australian television, and these different histories draw on different primary sources. The ABC of Drama, for example, draws on the ABC Document Archives (Jacka 1991). Most of the information for Images and Industry: television drama production in Australia is taken from original interviews with television production staff (Moran 1985). Ending the Affair, as well as archival work, draws on ‘over ten years of watching … Australian television current affairs’ (Turner 2005, xiii). Moran’s Guide to Australian TV Series draws exhaustively on extant archives: the ABC Document Archives, material sourced through the ABC Drama department, the Australian Film Commission, the library of the Australian Film, Television and Radio School, and the Australian Film Institute (Moran 1993, xi)...

More than a backchannel : Twitter and television

Twitter is a social media service that has managed very successfully to embed itself deeply in the everyday lives of its users. Its short message length (140 characters), and one-way connections (‘following’ rather than ‘friending’) lend themselves effectively to random and regular updates on almost any form of personal or professional activity – and it has found uses from the interpersonal (e.g. boyd et al., 2010) through crisis communication (e.g. Bruns et al., 2012) to political debate (e.g. Burgess & Bruns, 2012). In such uses, Twitter does not necessarily replace existing media channels, such as the broadcast or online offerings of the mainstream media, but often complements them, providing its users with alternative opportunities to contribute more actively to the wider mediasphere. This is true especially where Twitter is used alongside television, as a simple backchannel to live programming or for more sophisticated uses. In this article, we outline four aspects – dimensions – of the way that the ‘old’ medium of television intersects and, in some cases, interacts, with the ‘new’ medium of Twitter.

Australian television, popular memory and suburbia

Different archives of television material construct different versions of Australian national identity. There exists a Pro-Am archive of Australian television history materials consisting of many individual collections. This archive is not centrally located nor clearly bounded. The collections are not all linked to each other, nor are they aware of each other, and they do not claim to have a single common project. Pro-Am collections tend not to address Australian television as a whole, rather addressing particular genres, programs or production companies. Their vision of Australia is 'ordinary' and everyday. The boundaries of 'Australia' in the Pro-Am archive are porous, allowing non-Australians to contribute material, and also including non-Australian material and this causes little sense of anxiety.

Scheduling techniques to optimise rail operations

In Australia, railway systems play a vital role in transporting the sugarcane crop from farms to mills. The sugarcane transport system is very complex and uses daily schedules, consisting of a set of locomotives runs, to satisfy the requirements of the mill and harvesters. The total cost of sugarcane transport operations is very high; over 35% of the total cost of sugarcane production in Australia is incurred in cane transport. Efficient schedules for sugarcane transport can reduce the cost and limit the negative effects that this system can have on the raw sugar production system. There are several benefits to formulating the train scheduling problem as a blocking parallel-machine job shop scheduling (BPMJSS) problem, namely to prevent two trains passing in one section at the same time; to keep the train activities (operations) in sequence during each run (trip) by applying precedence constraints; to pass the trains on one section in the correct order (priorities of passing trains) by applying disjunctive constraints; and, to ease passing trains by solving rail conflicts by applying blocking constraints and Parallel Machine Scheduling. Therefore, the sugarcane rail operations are formulated as BPMJSS problem. A mixed integer programming and constraint programming approaches are used to describe the BPMJSS problem. The model is solved by the integration of constraint programming, mixed integer programming and search techniques. The optimality performance is tested by Optimization Programming Language (OPL) and CPLEX software on small and large size instances based on specific criteria. A real life problem is used to verify and validate the approach. Constructive heuristics and new metaheuristics including simulated annealing and tabu search are proposed to solve this complex and NP-hard scheduling problem and produce a more efficient scheduling system. Innovative hybrid and hyper metaheuristic techniques are developed and coded using C# language to improve the solutions quality and CPU time. Hybrid techniques depend on integrating heuristic and metaheuristic techniques consecutively, while hyper techniques are the complete integration between different metaheuristic techniques, heuristic techniques, or both.

Provincialising Perth? : Satellite television and the Chinese in Perth

Relocated people habitually seek the familiar within their new social milieus as a means of easing their transition into ways strange and alien. However, from networks and food to everyday customs, efforts to hold on to such home comforts are often viewed with a measure of hostile disdain and regarded as preludes to the formation of ethnic enclaves. Through a pilot study on the access of satellite television by mainland Chinese migrants in Perth, Western Australia, this chapter seeks to shed some light on how migrants understand and employ these comforting strategies and how Chinese-Australians are using technology to achieve a sense of sanctuary from the views and habits of Australians while (re)constructing and articulating multiple belongings in their new homes.