An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

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.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

Transporting jobs through a two-machine open shop

We consider the two-machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a 7/5-approximation algorithm. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009

Single machine scheduling and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.

Ghost/Machine: cinema in a digital age

Cinema, with its passive cinematic apparatus and linear narrative is often characterised as a contrast to new media narrative strategies, yet from Vertov’s Man with a Movie Camera to Mike Figgis’ TimeCode and Wong Kar Wei’s 2046 cinema provides narrative strategies and spatial conceptualisations which prefigure or are contiguous with new media environments. Both our perception of what cyberspace constitutes and the technology that actualises those perceptions arise out of and are driven by fantasy and desire. This paper will explore the metaphors used to represent and understand new media aesthetics through cinematic representations of new media environments. Two key themes relevant to new media aesthetics emerge. Irigaray, Haraway, and Grosz are used to explore the de-essentialising haptic and penetrative potential of new technologies and their ability to collapse the boundary between the body and the machine. The second fantasy, of new media as a liminal space that expresses the memorialising function of technology and its relation to mourning, is analysed using Benjamin, Burgin and Rutsky. These altered spaces and perceptions of the body and memory of the post-cinematic subject are illustrated through an analysis of Gondry’s Eternal Sunshine of the Spotless Mind and Jonze’s Being John Malkovich. [From the Author]

Lost in Translation, book review of Urban Landscape Perspectives

In Sofia Coppola's 2003 film Lost in Translation, Bill Murray and Scarlett Johansson's characters find themselves culturally stranded and oddly mismatched as an improvised tourist couple in contemporary Tokyo. This is an urban landscape that they cannot comprehend but only temporarily experience, in a fragmented and surreptitious way that allows no possible understanding and categorizations, but offers physical inclusion, emotional participation and momentary embeddedness.

Relational dimensions of corporate governance in translation: networked governance in China and India

The effectiveness of corporate governance mechanisms has been a subject of academic research for many decades. Although the large majority of corporate governance studies prior to mid 1990s were based on data from developed market economies such as the U.S., U.K. and Japan, in recent years researchers have begun examining corporate governance in transition economies. A comparison of China and India offers a unique environment for analyzing the effectiveness of corporate governance. First, both countries state-owned enterprise (SOE) reform strategies hinges on the Modern Enterprise System characterized by the separation of ownership and control. Ownership of an SOE’s assets is distributed among the government, institutional investors, managers, employees, and private investors. Effective control rights are assigned to management, which generally has a very small, or even nonexistent ownership stake. This distinctive shareholding structure creates conflict of interest not only between management (insiders) and outside investors but also between large shareholders and minority investors. Moreover, because both governments desire to retain some control—in part through partial retained ownership of commercialized SOEs, further conflicts arise between politicians and firms. Second, directors in publicly listed firms in both countries are predominantly drawn from institutions with significant non-market objectives: the government and other state enterprises, particularly in China, and extended families, particularly in India. As a result, the effectiveness of internal governance mechanisms, such as the number of independent directors on the board and the number of independent supervisors on the supervisory committee, are likely to be quiet limited, although this has yet to be fully evaluated. Third, because of the political nature of the privatization process itself, typical external governance mechanisms, such as debt (in conjunction with appropriate bankruptcy procedures), takeover threats, legal protection of investors, product market competition, etc., have not been effective. Bank loans have traditionally been viewed as grants from the state designed to bail out failing firms. State-owned banks retain monopoly or quasi-monopoly positions in the banking sector and profit is not their overriding objective. If political favor is deemed appropriate, subsidized loans, rescheduling of overdue debt or even outright transfer of funds can be arranged with SOEs (soft budget constraints). In addition, a market for private, non-bank debt is limited in India and has yet to be established China. There is no active merger or takeover activity in Chinese stock markets to discipline management. Information available in the capital markets is insufficient to keep at arm’s length of the corporate decisions. In light of the above peculiarities, China and India share many of the typical institutional characteristics as a transition economy, including poor legal protection of creditors and investors, the absence of an effective takeover market, an underdeveloped capital market, a relative inefficient banking system and significant interference of politicians in firm management. Su (2005) finds that the extent of political interference, managerial entrenchment and institutional control can help explain corporate dividend policies and post-IPO financing choices in this situation. Allen et al. (2005) demonstrate that standard corporate governance mechanisms are weak and ineffective for publicly listed firms while alternative governance mechanisms based on reputation and relationship have been remarkably effective in the private sector. Because the peculiarities are significant in this context, the differences in the political-economies of the two countries are likely to be evident in such relational terms. In this paper we explore the peculiarities of corporate governance in this transitional environment through a systematic examination of certain aspects of these reputational and relationship dimensions. Utilising the methods of social network analysis we identify the inter-organisational relationships at board level formed by equity holdings and by shared directors. Using data drawn from the Orbis database we map these relations among the 3700 largest firms in India and China respectively and identify the roles played in these relational networks by the particularly characteristic institutions in each case. We find greatly different social network structures in each case with some support in these relational dimensions for their distinctive features of governance. Further, the social network metrics allow us to considerably refine proxies for political interference, managerial entrenchment and institutional control used in earlier econometric analysis.

Effect of machine dependence on wall failure property measurements, Jenike versus an annular shear tester

Annular, ring or torsional shear testers are commonly used in bulk solids handling research for the purpose of powder characterisation or equipment design. This paper reports from a DEFRA sponsored project which aims to develop an industrial powder flow-ability tester, (based on the annular shear tester) that is economic to buy and quick and easy to use in trained but unskilled hands. This paper compares the wall failure loci measured with an annular shear cell with measurements obtained using the accepted standard wall friction tester, the Jenike shear cell. These wall failure loci have been measured for several bulk solids which range from fine cohesive powders to free-flowing granular materials, on a stainless steel 304 2B wall surface.

Slicing issues in CAD translation to STL in rapid prototyping

The rapid prototyping (RP) process is being used widely with great potential for rapid manufacturing of functional parts. The RP process involves translation of the CAD file to STL format followed by slicing of the model into multiple horizontal layers, each of which is reproduced physically in making the prototype. The thickness of the resulting slices has a profound effect on the surface finish and build time of the prototype. The purpose of this paper is to show the effects of slice thickness on the surface finish, layering error, and build time of a prototype, as well as to show how an efficient STL file can be developed. Three objects were modeled and STL files were generated. One STL file for each object was sliced using different slice thicknesses, and the build times were obtained. Screenshots were used to show the slicing effect on layering error and surface finish and to demonstrate the means to a more efficient STL file. From the results, it is clear that the surface finish and build time are important factors that are affected by slice thickness