Search

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We investigate the problem to schedule a set of precedence constrained jobs of unit size on an open-shop or on a flow-shop to minimize the makespan. The precedence constraints among the jobs are presented as a directed acyclic graph called the precedence graph. When the number of machines in the shop is part of the input, both problems are strongly NP-hard on general precedence graphs, but were proven polynomial-time solvable for some special precedence graphs such as intrees. In this paper, we characterize improved lower bounds on the minimum makespan in terms of the number of agreeable pairings among certain jobs and propose approximation algorithms based on a maximum matching among these jobs, so that every agreeable pair of jobs can be processed on different machines simultaneously. For open-shop with an arbitrary precedence graph and for flow-shop with a spine precedence graph, both achieved approximation ratios are 2 -- m, where m is the number of machines in the shop. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Aiming at the sensor network lifetime problem (SNLP), a sensor network coverage model and its data structure are proposed, and the problem is equivalent to its dual problem, namely minimum weight sensor coverage problem. Firstly, SNLP is constructed as a package linear programming. After finding different sensor coverage satisfying sensor network constraints, the sensor network life is maximized by allocating time for each sensor coverage. Secondly, for solving SNLP, three centralized solving methods are proposed, which are based on Garg- Konemann algorithm, greedy algorithm considering partial sensor coverage and constant approximation algorithm considering communication cost. At the same time, a distributed solving method based on global reshuffle is proposed. The reshuffle is triggered when the initial energy supply of a sensor drops to a certain predefined threshold value H among active, idle and intermediate vulnerable states, thus the sensor network lifetime is improved by using smart self- organizing monitoring schedules. Simulation results show that the proposed SNLP, which is based on sensor network coverage model and data structure, and its solving method can achieve preferable running time, network life and network overhead. [ABSTRACT FROM AUTHOR]

In order to solve the problem of large deviation between hidden Markov model and actual equipment health diagnosis,this paper developed an improved degenerated hidden Markov model(DGHMM) with a core of the quasi power relation.Firstly,the model adopted the degradation factors,modeling the process of recession for the equipment’s continuous decrease in performance.Compared with the conventional exponential accelerated degradation,the quasi power relation accelerated degradation could better describe the process that the performance of the equipment decreases gradually with the increase of service age.Then,the improved genetic algorithm could replace the conventional EM algorithm for parameters’ estimation,which overcame the limitation that the EM algorithm was easy to fall into local optimization.At the same time,in terms of the limitation of life prediction problem as a result of the hidden Markov model must obeyed exponential distribution,an algorithm named greed& approximation based on approximation algorithm and Viterbi algorithm came out,and to seek maximum probability remaining observation,for the purpose of seeking maximum probability dynamically surplus state path,to predict the residual life of equipment.Finally,it validated and evaluated the proposed method with the data set of caterpillar hydraulic pumps.The results show that the method of equipment health diagnosis and life prediction based on the improved degraded hidden Markov model is more effective in describing equipment’s degeneration and the accuracy of equipment state diagnosis,and is also feasible in the prediction of residual life. [ABSTRACT FROM AUTHOR]

In today' s big data era, big data processing frameworks such as MapReduce often appear slow and inefficient when processing data, specially related to graphs. Therefore, it is necessary to explore an efficient algorithm to handle this type of clique counting problem. Since the predecessor literatures have thoroughly explored the 3-clique counting, the extended version of the problem( the 4-clique counting problem) improves its position gradually. Under the guidance of a heuristic idea, this paper proposed a probability sampling algorithm based on neighboring edge sampling to solve the extended problem. With the usage of Chernoff inequality, the algorithm only needed a certain number of samplers as the performance guarantee of relative error under the approximate condition. Later, the experimental evaluation and comparison shows that the probability sampling algorithm loses a small amount of precision compared with the traditional precision algorithm, but it has great advantages in algorithm running time and space occupation. Finally, it comes to the conclusion that it has great practical value in practical applications. [ABSTRACT FROM AUTHOR]

To improve the efficiency of frequent itemset mining upon uncertain dataset, addressing the issue of heavy computation cost of existing algorithms on judging whether to build sub header table for a certain item in the header table, this paper proposed an approximation algorithm called AAT-Mine, at the cost of losing a small portion of frequent itemsets, improved the overall mining performance. It evaluated the AAT-Mine algorithm using three datasets against classical and state of art algorithms. Experimental results show that AAT-Mine not only outperforms AT-Mine, MBP, IMBP, UF-Growth and CUFP-Mine in terms of running time, but also remains efficient memory usage. [ABSTRACT FROM AUTHOR]