Evaluating the effectiveness of FDM in identifying important factors in a dynamic flowshop

Dynamic events such as machine breakdown and hot jobs may induce problems on the production system such as order delay, increasing machine load, and changing inventory level. Past studies of dynamic events often use traditional design of experiments (DOE) to analyze the effects of dynamic events on system's performance. The shortcoming of this approach is that the number of experimental runs conducted would become exponentially increased as the number of factors increased. This study tries to use frequency domain methodology (FDM) instead so as to detect the higher order effects and rank important factors in a few experimental runs. Spectrum analysis is used to comprehend the effects of different location of machine breakdown and different size of hot jobs on the system's performance of flowshops with different traffic (utilization) and stability (oscillation). This study finds that the important factors identified by the FDM analysis are the same as that of DOE. However, only in some cases can the rankings of important factors be the same for both approaches. The dissimilarity between rankings of important factors found by these two methods is further measured using Kendall tau distance.     

A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs

The Arc-Preserving Subsequence (APS) problem appears in the comparison of RNA structures in computational biology. Given two arc-annotated sequences of length n and m<n, APS asks if the shorter sequence can be obtained from the longer one by deleting certain elements along with their incident arcs. It is known that APS with pairwise nested arcs can be solved in O(mn) time. We give an algorithm running in O(m²+n) time in the worst case, actually it is even faster in particular if the shorter sequence has many arcs. The result may serve as a building block for improved APS algorithms in the general case.     

Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines

We consider the scheduling of orders in an environment with m uniform machines in parallel. Each order requests certain amounts of k different product types. Each product type can be produced by any one of the m machines. No setup is required if a machine switches over from one product type to another. Different product types intended for the same order can be produced at the same time (concurrently) on different machines. Each order is released at time zero and has a positive weight. Preemptions are allowed. The completion time of an order is the finish time of the product type that is completed last for that order. The objective is to minimize the total weighted completion time. We propose heuristics for the non-preemptive as well as the preemptive case and obtain worst case bounds that are a function of the number of machines as well as the differences in the speeds of the machines. Even though the worst-case bounds we showed for the two heuristics are not very tight, our experimental results show that they yield solutions that are very close to optimal.