An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 ^k n ³) time algorithm for this problem, significantly improving the previous algorithm of time for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n). A preliminary version of this paper was presented at The 10th Workshop on Algorithms and Data Structures (WADS 2007). This work was supported in part by the National Science Foundation under the Grants CCR-0311590 and CCF-0430683.     

Fragment-based responsive character motion for interactive games

Fragment-based character animation has become popular in recent years. By stringing appropriate motion capture fragments together, the system drives characters responding to the control signals of the user and generates realistic character motions. In this paper, we propose a novel, straightforward and fast method to build the control policy table, which selects the next motion fragment to play based on the current user’s input and the previous motion fragment. During the synthesis of the control policy table, we cluster similar fragments together to create several fragment classes. Dynamic programming is employed to generate the training samples based on the control signals of the user. Finally, we use a supervised learning routine to create the tabular control policy. We demonstrate the efficacy of our method by comparing the motions generated by our controller to the optimal controller and other previous controllers. The results indicate that although a reinforcement learning algorithm known as value iteration also creates the tabular control policy, it is more complex and requires more expensive space–time cost in synthesis of the control policy table. Our approach is simple but efficient, and is practical for interactive character games.     

Countering the loss of extended vigilance in supervisory control using a fuzzy logic model

When an operator first detects unusual and/or infrequent or irregular signals in a system, the operator does not need to take any action, but must increase his/her level of attention and be alert for any more serious signals that may confirm a problem with the system. This is referred to as extended vigilance. The purpose of this study was to construct a fuzzy vigilance-measuring model for countering the loss of extended vigilance. The model extends two-valued logic (“Yes” or “No”) to multi-valued logic through fuzzy sets. Then a fuzzy logic alarm was developed by the model for combating the extended vigilance decrement. The first experiment compared the effect of the fuzzy measuring model with signal detection theory (SDT) and discussed the relationship between preliminary and extended vigilance for a simulated feed-water monitoring system. The results indicated that the sensitivity of the fuzzy vigilance-measuring model is better than index d′ and β, and that the preliminary vigilance significantly influences the extended vigilance. The second experiment verified the effect of the fuzzy logic alarm. The results indicated that the effect of the fuzzy logic alarm for combating the extended vigilance decrement is significant. When the preliminary vigilance is poor, an appropriate alarm will improve the extended vigilance. However, if the preliminary vigilance is very poor, the improvement of the extended vigilance will be limited.Relevance to industry: The extended vigilance is a new and important issue in human performance problems in industry, particularly in such areas as air-traffic control, industrial inspection and power plant monitor. The measuring model of vigilance could be applied to develop an alarm for promoting supervisory performance of human and human–machine detectors.     

Whole-body vibration exposure experienced by motorcycle riders – An evaluation according to ISO 2631-1 and ISO 2631-5 standards

Riders of twelve motorcycles, comprising 6 full-scale motorbikes and 6 motor-scooters, and 5 sedan vehicles, performed test runs on a 20.6 km paved road composed of 5 km, 5 km, and 10.6 km of rural, provincial and urban routes, respectively. Each test run of motorcycle was separately performed under speed limits of 55 km/h and 40 km/h. Tri-axial accelerations of whole-body vibration (WBV) were obtained by using a seat pad and a portable data logger, and the driver's view was videotaped with a portable media recorder. Root mean square (RMS) acceleration, 8-h estimated vibration dose value (VDV₍₈₎) and 8-h estimated daily dose of static compression dose (S_ed) were determined from the collected data in accordance with ISO 2631-1 and ISO 2631-5 standards. Experimental results indicate that the WBV values of the sedan vehicle drivers have low RMS, VDV₍₈₎ and S_ed values (RMS 0.27–0.32 m/s²; VDV₍₈₎ 6.3–8.3 m/s^1.75; S_ed 0.21–0.26 MPa). However, over 90% of the motorcycle riders had VDV₍₈₎ (mean 23.5 m/s^1.75) exceeding the upper boundary of health guidance caution zone (17 m/s^1.75) recommended by ISO 2631-1, or had S_ed (mean 1.17 MPa) exceeding the value associated with a high probability of adverse health effects (0.8 MPa) recommended by ISO 2631-5. Over 50% of the motorcycle riders reached these boundary values for VDV and S_e in less than 2 h. The WBV exposure levels of the full-scale motorbikes riders and motor-scooter riders were not significantly different. However, the RMS and VDV₍₈₎ values of motorcycle riders indicate significant roadway effect (p < 0.001), while their S_ed values indicate significant speed limit effect (p < 0.05). This study concludes that the WBV exposure levels of common motorcycle riders are distinctively higher than those of sedans, even on a regular paved road. The impact on health of WBV exposure in motorcycle riders should be carefully addressed with reference to ISO 2631-1 and ISO 2631-5.

Relevance to industry

This study compares the predicted health risks of motorcycle riders according to ISO 2631-1 and ISO 2631-5 standards. Experimental data suggest that the vibration dose value of ISO 2631-1 and daily dose of equivalent static compression stress of ISO 2631-5 have roughly equivalent boundaries for probable health effects.     

Insights from Dividing 3D Goal-Directed Movements into Meaningful Phases

Existing measures for evaluating user performance on interaction tasks in virtual environments don't often provide sufficient information for improving these interactions. A new method for analyzing 3D goal-directed movements divides them into meaningful phases. The authors applied this method to experimental data collected for a 3D task resembling a standardized 2D multidirectional pointing task (ISO 9241-9). The results and analysis demonstrate that the method provides a more detailed insight into 3D goal-directed movements. This analysis can help researchers better identify input devices' and interaction techniques' strengths and weaknesses. This article is part of a special issue on 3D user interfaces.     

Godson-3: A Scalable Multicore RISC Processor with x86 Emulation

The Godson-3 microprocessor aims at high-throughput server applications, high-performance scientific computing, and high-end embedded applications. It offers a scalable network on chip, hardware support for x86 emulation, and a reconfigurable architecture. The four-core Godson-3 chip is fabricated with 65-nm CMOS technology. Eight- and 16-core Godson-3 chips are in development.     

A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems

This paper presents a novel discrete differential evolution (DDE) algorithm for solving the no-wait flow shop scheduling problems with makespan and maximum tardiness criteria. First, the individuals in the DDE algorithm are represented as discrete job permutations, and new mutation and crossover operators are developed based on this representation. Second, an elaborate one-to-one selection operator is designed by taking into account the domination status of a trial individual with its counterpart target individual as well as an archive set of the non-dominated solutions found so far. Third, a simple but effective local search algorithm is developed to incorporate into the DDE algorithm to stress the balance between global exploration and local exploitation. In addition, to improve the efficiency of the scheduling algorithm, several speed-up methods are devised to evaluate a job permutation and its whole insert neighborhood as well as to decide the domination status of a solution with the archive set. Computational simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is shown that the proposed DDE algorithm is superior to a recently published hybrid differential evolution (HDE) algorithm [Qian B, Wang L, Huang DX, Wang WL, Wang X. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers & Operations Research 2009;36(1):209–33] and the well-known multi-objective genetic local search algorithm (IMMOGLS2) [Ishibuchi H, Yoshida I, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation 2003;7(2):204–23] in terms of searching quality, diversity level, robustness and efficiency. Moreover, the effectiveness of incorporating the local search into the DDE algorithm is also investigated.     

Performance modeling,real-time dispatching and simulation of wafer fabrication systems using timed extended object-oriented Petri nets

Semiconductor wafer fabrication system (SWFS) is the most complex and capital-intensive phase in the entire semiconductor manufacturing cycle. With characteristics of re-entrant processing routes, equipment uncertainty, product diversity and improving technologies, great challenges are presented in SWFS’s modeling, scheduling and simulation. To implement efficient production control, this paper provides a timed extended object-oriented Petri nets (TEOPNs) approach to performance modeling, real-timed dispatching and simulation of SWFSs. The TEOPNs models are constructed in a hierarchy to accord with the real-world SWFS’s organization, and a new type of signal place is added into the TEOPNs to respond the dynamic states of all processing facilities. A novel autonomy and coordination-based real-time dispatching mechanism (A&C-RDM) is developed in this paper, which executes under the support of the TEOPNs-based hybrid real-time dispatching control system (HRDCS). Owning to the ability of gathering dynamic real-time information of all production facilities and WIP products, the HRDCS can make adaptive dispatching decisions according to the local and global real-time processing status. Two sets of key elements of real-time dispatching, i.e. the state thresholds and dispatching rules, are defined in the HRDCS so that the A&C-RDM can integrate different types of dispatching rules. A set of simulation experiments prove the efficiency of the proposed modeling and dispatching algorithm. In summary, the proposed TEOPNs, HRDCS and A&C-RDM form the cornerstones of a real-time dispatching simulation prototype of SWFS, and the work described in this paper carries out an advanced integrated “modeling–dispatching–simulation” methodology.