Genetic algorithms for match-up rescheduling of the flexible manufacturing systems

Scheduling plays a vital role in ensuring the effectiveness of the production control of a flexible manufacturing system (FMS). The scheduling problem in FMS is considered to be dynamic in its nature as new orders may arrive every day. The new orders need to be integrated with the existing production schedule immediately without disturbing the performance and the stability of existing schedule. Most FMS scheduling methods reported in the literature address the static FMS scheduling problems. In this paper, rescheduling methods based on genetic algorithms are described to address arrivals of new orders. This study proposes genetic algorithms for match-up rescheduling with non-reshuffle and reshuffle strategies which accommodate new orders by manipulating the available idle times on machines and by resequencing operations, respectively. The basic idea of the match-up approach is to modify only a part of the initial schedule and to develop genetic algorithms (GAs) to generate a solution within the rescheduling horizon in such a way that both the stability and performance of the shop floor are kept. The proposed non-reshuffle and reshuffle strategies have been evaluated and the results have been compared with the total-rescheduling method.     

Dynamic rescheduling that simultaneously considers efficiency and stability

Dynamic job shop scheduling is a frequently occurring and highly relevant problem in practice. Previous research suggests that periodic rescheduling improves classical measures of efficiency; however, this strategy has the undesirable effect of compromising stability and this lack of stability can render even the most efficient rescheduling strategy useless on the shop floor. In this research, a rescheduling methodology is proposed that uses a multiobjective performance measures that contain both efficiency and stability measures. Schedules are generated at each rescheduling point using a genetic local search algorithm that allows efficiency and stability to be balanced in a way that is appropriate for each situation. The methodology is tested on a simulated job shop to determine the impact of the key parameters on the performance measures.     

E-commerce success criteria: determining which criteria count most

We explore in this paper how performance of e-commerce websites in terms of various criteria influences customers’ intention to shop again in the same website. Our approach is based on an interesting use of statistical regression in the hotel literature that attempted to classify different cues in hotels as critical, satisfier, dissatisfier, etc. We use online ratings for 484 e-commerce websites for this study. Our study shows that “satisfaction with claims” is the single most important criterion valued as critical by online customers. “Comparative prices” and “Refunds/returns” are desirable criteria. “Management accessibility”, “Payment process” and “Privacy experience” are satisfiers while “on-time delivery” is a dissatisfier.     

A genetic algorithm for dynamic advanced planning and scheduling (DAPS) with a frozen interval

This paper investigates a dynamic advanced planning and scheduling (DAPS) problem where new orders arrive on a continuous basis. A periodic policy with a frozen interval is adopted to increase stability on the shop floor. A genetic algorithm is developed to find a schedule such that both production idle time and penalties on tardiness and earliness of both original orders and new orders are minimized at each rescheduling point. The proposed methodology is tested on a series of examples. A representative example is illustrated to indicate that the suggested approach can improve the schedule stability while retaining efficiency.     

An anticipative scheduling approach with controllable processing times

In practice, machine schedules are usually subject to disruptions which have to be repaired by reactive scheduling decisions. The most popular predictive approach in project management and machine scheduling literature is to leave idle times (time buffers) in schedules in coping with disruptions, i.e. the resources will be under-utilized. Therefore, preparing initial schedules by considering possible disruption times along with rescheduling objectives is critical for the performance of rescheduling decisions. In this paper, we show that if the processing times are controllable then an anticipative approach can be used to form an initial schedule so that the limited capacity of the production resources are utilized more effectively. To illustrate the anticipative scheduling idea, we consider a non-identical parallel machining environment, where processing times can be controlled at a certain compression cost. When there is a disruption during the execution of the initial schedule, a match-up time strategy is utilized such that a repaired schedule has to catch-up initial schedule at some point in future. This requires changing machine–job assignments and processing times for the rest of the schedule which implies increased manufacturing costs. We show that making anticipative job sequencing decisions, based on failure and repair time distributions and flexibility of jobs, one can repair schedules by incurring less manufacturing cost. Our computational results show that the match-up time strategy is very sensitive to initial schedule and the proposed anticipative scheduling algorithm can be very helpful to reduce rescheduling costs.     

Analysis of optimal strategies for a competing stock market portfolio model with a polyvariant profit function

A competitive market model with a polyvariant profit function is investigated as applied to the competing banking portfolio medium under conditions of “zeitnot” stock behavior of clients with a view to devising optimal strategies. The method of associated Markov processes is developed with a view to finding an optimal strategy for choosing the most valuable share package for monovariant and bivariant profit functions. Under certain constraints on the so-called bank “promotional” parameter with respect to the “fee” for a missed share package transaction in the case of an asymptotically large portfolio size, universal transcendental equations are obtained that determine the optimal share package choice among competing strategies with monovariant and bivariant profit functions.     

Multi-objective scheduling of dynamic job shop using variable neighborhood search

Dynamic job shop scheduling that considers random job arrivals and machine breakdowns is studied in this paper. Considering an event driven policy rescheduling, is triggered in response to dynamic events by variable neighborhood search (VNS). A trained artificial neural network (ANN) updates parameters of VNS at any rescheduling point. Also, a multi-objective performance measure is applied as objective function that consists of makespan and tardiness. The proposed method is compared with some common dispatching rules that have widely used in the literature for dynamic job shop scheduling problem. Results illustrate the high effectiveness and efficiency of the proposed method in a variety of shop floor conditions.     

Filtered-beam-search-based algorithm for dynamic rescheduling in FMS

In the practical production process of a flexible manufacturing system (FMS), unexpected disturbances such as rush orders arrival and machine breakdown may inevitably render the existing schedule infeasible. This makes dynamic rescheduling necessary to respond to the disturbances and to improve the efficiency of the disturbed FMS. Compared with the static scheduling, the dynamic rescheduling relies on more effective and robust search approaches for its critical requirement of real-time optimal response. In this paper, a filtered-beam-search (FBS) -based heuristic algorithm is proposed to solve the dynamic rescheduling problem in a large and complicated job shop FMS environment with realistic disturbances. To enhance its performance, the proposed algorithm makes improvement in the local/global evaluation functions and the generation procedure of branches. With respect to a due date-based objective (weighted quadratic tardiness), computational experiments are studied to evaluate the performance of the proposed algorithm in comparison with those of other popular methods. The results show that the proposed FBS-based algorithm performs very well for dynamic rescheduling in terms of computational efficiency and solution quality.     

Lemma and cut strategies for propositional model elimination

This paper describes new “lemma” and “cut” strategies that are efficient to apply in the setting of propositional Model Elimination. Previous strategies for managing lemmas and C-literals in Model Elimination were oriented toward first-order theorem proving. The original “cumulative” strategy remembers lemmas forever, and was found to be too inefficient. The previously reported C-literal and unit-lemma strategies, such as “strong regularity”, forget them unnecessarily soon in the propositional domain. An intermediate strategy, called “quasi-persistent” lemmas, is introduced. Supplementing this strategy, methods for “eager” lemmas and two forms of controlled “cut” provide further efficiencies. The techniques have been incorporated into “Modoc”, which is an implementation of Model Elimination, extended with a new pruning method that is designed to eliminate certain refutation attempts that cannot succeed. Experimental data show that on random 3CNF formulas at the “hard” ratio of 4.27 clauses per variable, Modoc is not as effective as recently reported model-searching methods. However, on more structured formulas from applications, such as circuit-fault detection, it is superior. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于窗口的印刷车间作业动态调度研究

为了解决实际印刷车间突发设备故障和紧急插单问题,采用滚动窗口技术结合遗传算法的方法,建立适合实际印刷车间生产的动态再调度模型;设定若干印品订单、机器设备的加工工序以及各工序加工时间、工序约束条件等,以订单的最大最小加工时间和再调度的偏离度为多目标优化,采用周期与事件混合驱动策略,将滚动窗口再调度机制和遗传算法相结合进行流程设计和编码,构建印刷车间再调度模型;采用标准问题FT06和FT01验证了文章设计的模型算法的有效性和可行性;运行程序,模拟正常加工时紧急插单和机器故障突发时,系统生产新的调度计划即调度甘特图,仿真结果表明该动态调度模型可以用于印刷作业的正常排产调度,在遇突发状况时可生成稳定、符合交货日期的再调度方案。     

“Those found responsible have been sacked”: some observations on the usefulness of error

Erik Hollnagel’s body of work in the past three decades has molded much of the current research approach to system safety, particularly notions of “error”. Hollnagel regards “error” as a dead-end and avoids using the term. This position is consistent with Rasmussen’s claim that there is no scientifically stable category of human performance that can be described as “error”. While this systems view is undoubtedly correct, “error” persists. Organizations, especially formal business, political, and regulatory structures, use “error” as if it were a stable category of human performance. They apply the term to performances associated with undesired outcomes, tabulate occurrences of “error”, and justify control and sanctions through “error”. Although a compelling argument can be made for Hollnagel’s view, it is clear that notions of “error” are socially and organizationally productive. The persistence of “error” in management and regulatory circles reflects its value as a means for social control.     

Effects of etiquette strategy on human–robot interaction in a simulated medicine delivery task

The objective of this study was to examine the extent to which a model of linguistic etiquette in human–human interaction could be applied to human–robot interaction (HRI) domain, and how different etiquette strategies proposed through the model might influence performance of humans and robots as mediated by manipulations of robot physical features, in a simulated medicine delivery task. A “wizard of Oz” experiment was conducted in which either a humanoid robot or a mechanical-looking robot was used to present medicine reminding utterances (following different etiquette strategies) to participants, who were engaged in a primary cognitive task (a Sudoku puzzle). Results revealed the etiquette model to partially extend to the HRI domain. Participants were not sensitive to positive language from robots (e.g., appreciation of human values/wants) and such a strategy did not succeed in supporting or enhancing the “positive face” of human users. Both “bald” (no linguistic courtesy) and mixed strategies (positive and “negative face” (minimizing user imposition) saving) resulted in moderate user perceived etiquette scores (PE). However, individual differences suggested such robot linguistic strategies should be applied with caution. Opposite to this, a negative face saving strategy (supporting user freedom of choice) promoted user task and robot performance (in terms of user response time to robot requests), and resulted in the highest PE score. There was also evidence that humanoid robot features provide additional social cues that may be used by patients and support human and robot performance, but not PE. These results provide a basis for determining appropriate etiquette strategies and robot appearance to promote better collaborative task performances for future health care delivery applications of service robots.     

Analysis of autonomous cooperative assembly using coordination schemes by heterogeneous robots using a control basis approach

Robotic technology is quickly evolving allowing robots to perform more complex tasks in less structured environments with more flexibility and autonomy. Heterogeneous multi-robot teams are more common as the specialized abilities of individual robots are used in concert to achieve tasks more effectively and efficiently. An important area of research is the use of robot teams to perform modular assemblies. To this end, this paper analyzed the relative performance of two robots with different morphologies and attributes in performing an assembly task autonomously under different coordination schemes using force sensing through a control basis approach. A rigid, point-to-point manipulator and a dual-armed pneumatically actuated humanoid robot performed the assembly of parts under a traditional “push-hold” coordination scheme and a human-mimicked “push-push” scheme. The study revealed that the scheme with higher level of cooperation—the “push-push” scheme—performed assemblies faster and more reliably, lowering the likelihood of stiction phenomena, jamming, and wedging. The study also revealed that in “push-hold” schemes industrial robots are better pushers and compliant robots are better holders. The results of our study affirm the use of heterogeneous robots to perform hard-to-do assemblies and also encourage humans to function as holder’s when working in concert with a robot assistant for insertion tasks.     

Improving the anytime behavior of two-phase local search

Algorithms based on the two-phase local search (TPLS) framework are a powerful method to efficiently tackle multi-objective combinatorial optimization problems. TPLS algorithms solve a sequence of scalarizations, that is, weighted sum aggregations, of the multi-objective problem. Each successive scalarization uses a different weight from a predefined sequence of weights. TPLS requires defining the stopping criterion (the number of weights) a priori, and it does not produce satisfactory results if stopped before completion. Therefore, TPLS has poor “anytime” behavior. This article examines variants of TPLS that improve its “anytime” behavior by adaptively generating the sequence of weights while solving the problem. The aim is to fill the “largest gap” in the current approximation to the Pareto front. The results presented here show that the best adaptive TPLS variants are superior to the “classical” TPLS strategies in terms of anytime behavior, matching, and often surpassing, them in terms of final quality, even if the latter run until completion.     

Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion

This study investigates the flexible job shop scheduling problem (FJSP) with new job insertion. FJSP with new job insertion includes two phases: initializing schedules and rescheduling after each new job insertion. Initializing schedules is the standard FJSP problem while rescheduling is an FJSP with different job start time and different machine start time. The time to do rescheduling is the same as the time of new job insertion. Four ensembles of heuristics are proposed for scheduling FJSP with new job insertion. The objectives are to minimize maximum completion time (makespan), to minimize the average of earliness and tardiness (E/T), to minimize maximum machine workload (Mworkload) and total machine workload (Tworkload). Extensive computational experiments are carried out on eight real instances from remanufacturing enterprise. The results and comparisons show the effectiveness of the proposed heuristics for solving FJSP with new job insertion.     

Properties of a relational framework synthesized over a set of semantically atomic predicates

Properties of a relational framework synthesized over a set of semantically atomic predicates are analyzed. A relational framework is shown to be stable with respect to a modification in the basic predicate set. The stability, uniqueness, and completeness allow one to consider a relational framework as a universal “carrier” for object domains with arbitrary semantics.     

Parallel machine match-up scheduling with manufacturing cost considerations

Many scheduling problems in practice involve rescheduling of disrupted schedules. In this study, we show that in contrast to fixed processing times, if we have the flexibility to control the processing times of the jobs, we can generate alternative reactive schedules considering the manufacturing cost implications in response to disruptions. We consider a non-identical parallel machining environment where processing times of the jobs are compressible at a certain manufacturing cost, which is a convex function of the compression on the processing time. In rescheduling it is highly desirable to catch up the original schedule as soon as possible by reassigning the jobs to the machines and compressing their processing times. On the other hand, one must also keep the manufacturing cost due to compression of the jobs low. Thus, one is faced with a tradeoff between match-up time and manufacturing cost criteria. We introduce alternative match-up scheduling problems for finding schedules on the efficient frontier of this time/cost tradeoff. We employ the recent advances in conic mixed-integer programming to model these problems effectively. We further provide a fast heuristic algorithm driven by dual prices of convex subproblems for generating approximate efficient schedules.     

Size-depth tradeoff in non-monotone Boolean formulae

Summary Formula size and depth are two important complexity measures of Boolean functions. We study the tradeoff between those two measures: We give an infinite set of Boolean functions and show for nearly each of them: There is no formula over “and”, “or”, “negation” computing it optimal with respect to both measures. That implies a logarithmic lower bound on circuit depth.     

A new parallel scheduling system for multiple radio wireless mesh network

To enhance the capacity of wireless mesh networks, a key technique is widely investigated which is the usage of multi-radio and multi-channel diversity. In this paper, a new parallel scheduling system is proposed which exploits MAC diversities by transmitting packets on the radios opportunistically. Compared with conventional packet transmission which follows “one flow one radio”, the new system uses radio diversity to transmit the packets on different radios simultaneously. Two kernel components of this system are selection module and schedule module. A localized selecting algorithm is implemented in the selection model to choose the right radios based on the quality of wireless links; two distributed packet-scheduling algorithms are optional with the schedule component. Finally, a routing metric adapting this system is presented. We have carried out a comprehensive performance evaluation of this system using ns-2. Simulation results show that it can successfully harness diversity of multi-radio and multi-channel to provide considerable improvements over a baseline multi-channel system in several situations.