Performance analysis of active schedules in identical parallel machine

Active schedule is one of the most basic and popular concepts in production scheduling research. For identical parallel machine scheduling with jobs’ dynamic arrivals, the tight performance bounds of active schedules under the measurement of four popular objectives are respectively given in this paper. Similar analysis method and conclusions can be generalized to static identical parallel machine and single machine scheduling problem.     

Performance analysis of active schedules in identical parallel machine

Active schedule is one of the most basic and popular concepts in production scheduling research. For identical parallel machine scheduling with jobs’ dynamic arrivals, the tight performance bounds of active schedules under the measurement of four popular objectives are respectively given in this paper. Similar analysis method and conclusions can be generalized to static identical parallel machine and single machine scheduling problem.     

Task-resource scheduling problem

Cloud computing is a new and rapidly emerging computing paradigm where applications,data and IT services are provided over the Internet.The task-resource management is the key role in cloud computing systems.Task-resource scheduling problems are premier which relate to the efficiency of the whole cloud computing facilities.Task-resource scheduling problem is NPcomplete.In this paper,we consider an approach to solve this problem optimally.This approach is based on constructing a logical model for the problem.Using this model,we can apply algorithms for the satisfiability problem(SAT) to solve the task-resource scheduling problem.Also,this model allows us to create a testbed for particle swarm optimization algorithms for scheduling workflows.     

Worst-Case Nash Equilibria in Restricted Routing

We study the network routing problem with restricted and related links.There are parallel links with possibly different speeds,between a source and a sink.Also there are users,and each user has a traffic of some weight to assign to one of the links from a subset of all the links,named his/her allowable set.The users choosing the same link suffer the same delay,which is equal to the total weight assigned to that link over its speed.A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link.To measure the performance degradation of the system due to the selfish behavior of all the users,Koutsoupias and Papadimitriou proposed the notion Price of Anarchy (denoted by PoA),which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution.The PoA for this restricted related model has been studied,and a linear lower bound was obtained.However in their bad instance,some users can only use extremely slow links.This is a little artificial and unlikely to appear in a real world.So in order to better understand this model,we introduce a parameter for the system,and prove a better Price of Anarchy in terms of the parameter.We also show an important application of our result in coordination mechanism design for task scheduling game.We propose a new coordination mechanism,Group-Makespan,for unrelated selfish task scheduling game with improved price of anarchy.     

Modeling and control for wireless networked control system

In this paper, the stabilization problem is considered for the class of wireless networked control systems (WNCS). An indicator is introduced in the WNCS model. The packet drop sequences in the indicator are represented as states of a Markov chain. A new discrete Markov switching system model integrating 802.11 protocol and new scheduling approach for wireless networks with control systems are constructed. The variable controller can be obtained easily by solving the linear matrix inequality (LMI) with the use of the Matlab toolbox. Both the known and unknown dropout probabilities are considered. Finally, a simulation is given to show the feasibility of the proposed method.     

Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system

Consider a resource allocation problem on the following system. A system consists of m identical parallel machines and is alive only when all the machines are alive. To keep a machine alive, it requires resources (material, fuel, etc.). Resources with various sizes arrive one by one and the goal is to keep the system alive as long as possible. The problem has applications in many areas such as sequencing of maintenance actions for modular gas turbine aircraft engines[1]. Using scheduling term…     

Selective ensemble extreme learning machine modeling of effluent quality in wastewater treatment plants

Real-time and reliable measurements of the effluent quality are essential to improve operating efficiency and reduce energy consumption for the wastewater treatment process.Due to the low accuracy and unstable performance of the traditional effluent quality measurements,we propose a selective ensemble extreme learning machine modeling method to enhance the effluent quality predictions.Extreme learning machine algorithm is inserted into a selective ensemble frame as the component model since it runs much faster and provides better generalization performance than other popular learning algorithms.Ensemble extreme learning machine models overcome variations in different trials of simulations for single model.Selective ensemble based on genetic algorithm is used to further exclude some bad components from all the available ensembles in order to reduce the computation complexity and improve the generalization performance.The proposed method is verified with the data from an industrial wastewater treatment plant,located in Shenyang,China.Experimental results show that the proposed method has relatively stronger generalization and higher accuracy than partial least square,neural network partial least square,single extreme learning machine and ensemble extreme learning machine model.     

Energy-efficient power allocation for selfish cooperative communication networks using bargaining game

In commercial networks,user nodes operating on batteries are assumed to be selfish to consume their energy solely to maximize their own benefits,e.g.,data rates.In this paper,we propose a bargaining game to perform the power allocation for the selfish cooperative communication networks.In our system,two partner nodes can act as a source as well as a relay for each other,and each node is with an energy constraint to transmit one frame.Consider a selfish node is willing to seek cooperative transmission only if the data rate achieved through cooperation will not lower than that achieved through noncooperation by using the same amount of energy.The energy-efficient power allocation problem can be modeled as a cooperative game.We proved that there exists a unique Nash bargaining solution (NBS) for the game by verifying that the game is indeed a bargaining problem.Thus,the two objectives,i.e.,system efficiency and user fairness specified in the selfish networks can be achieved.Simulation results show that the NBS scheme is efficient in that the performance loss of the NBS scheme to that of the maximal overall rate scheme is small while the maximal-rate scheme is unfair.The simulation results also show that the NBS result is fair in that both nodes could experience better performance than they work independently and the degree of cooperation of a node only depends on how much contribution its partner can make to improve its own performance.     

Game Theoretic subcarrier and power allocation for wireless OFDMA networks

This paper proposes a bargaining game theoretic resource(including the subcarrier and the power) allocation scheme for wireless orthogonal frequency division multiple access(OFDMA) networks.We define a wireless user s payoff as a function of the achieved data-rate.The fairness resource allocation problem can then be modeled as a cooperative bargaining game.The objective of the game is to maximize the aggregate payoffs for the users.To search for the Nash bargaining solution(NBS) of the game,a suboptimal subcarrier allocation is performed by assuming an equal power allocation.Thereafter,an optimal power allocation is performed to maximize the sum payoff for the users.By comparing with the max-rate and the max-min algorithms,simulation results show that the proposed game could achieve a good tradeoff between the user fairness and the overall system performance.     

Fuzzy differential games for nonlinear stochastic systems:suboptimal approach

A fuzzy differential game theory is proposed to solve the n-person (or n-player) nonlinear differential noncooperative game and cooperative game (team) problems, which are not easily tackled by the conventional methods. In the paper, both noncooperative and cooperative quadratic differential games are considered. First, the nonlinear stochastic system is approximated by a fuzzy model. Based on the fuzzy model, a fuzzy controller is proposed to deal with the noncooperative differential game in the sense of Nash equilibrium strategies or with the cooperative game in the sense of Pareto-optimal strategies. Using a suboptimal approach, the outcomes of the fuzzy differential games for both the noncooperative and the cooperative cases are parameterized in terms of an eigenvalue problem. Since the state variables are usually unavailable, a suboptimal fuzzy observer is also proposed in this study to estimate the states for these differential game problems. Finally, simulation examples are given to illustrate the design procedures and to indicate the performance of the proposed methods     

利用退火回归神经网络极值搜索算法求纳什均衡解

针对如何解算n人非合作的动态博弈对策中的纳什均衡解问题,提出一种利用退火回归神经网络极值搜索算法解算纳什均衡解的方法．在动态博弈对策问题中,将每个竞争者视为一个代价函数,利用此算法可以使每个代价函数均收敛于其最小值,从而获得此对策的纳什均衡解．此算法不限制代价函数的具体形式,同时由于摒弃了正弦激励信号,解决了一般极值搜索算法中存在的输出量“颤动”现象和控制量来回切换问题,改善了系统的动态性能．     

Noncooperative load balancing in distributed systems

In this paper, we present a game theoretic framework for obtaining a user-optimal load balancing scheme in heterogeneous distributed systems. We formulate the static load balancing problem in heterogeneous distributed systems as a noncooperative game among users. For the proposed noncooperative load balancing game, we present the structure of the Nash equilibrium. Based on this structure we derive a new distributed load balancing algorithm. Finally, the performance of our noncooperative load balancing scheme is compared with that of other existing schemes. The main advantages of our load balancing scheme are the distributed structure, low complexity and optimality of allocation for each user.     

泛集群环境中计算密集型任务流调度策略

针对计算节点较多的泛集群环境下难以快速、合理地制定计算密集型任务流调度方案的问题,提出一种基于多目标连续竞买博弈的任务调度策略.建立多目标优化调度模型,降低多目标优化函数维度,并采用线性加权和法将其转化为总和目标函数,以保证最优解的合理性.为提高最优解搜索速度,引入ETC矩阵作为最优解表达形式,设计连续竞买博弈算法.模拟真实场景并通过与同类算法的对比,表明了调度策略在泛集群环境下的响应速度、资源性价比和总成本支出等方面具有明显优势.     

Capacity allocation under noncooperative routing

The capacity allocation problem in a network that is to be shared by noncooperative users is considered. Each user decides independently upon its routing strategy so as to optimize its individual performance objective. The operating points of the network are the Nash equilibria of the underlying routing game,. The network designer aims to allocate link capacities, so that the resulting Nash equilibria are efficient, according to some systemwide performance criterion. In general, the solution of such design problems is complex and at times counterintuitive, since adding link capacity might lead to degradation of user performance. For systems of parallel links, we show that such paradoxes do not occur and that the capacity allocation problem has a simple and intuitive optimal solution that coincides with the solution in the single-user case     

单台批处理机生产运输协调合作博弈调度问题

研究单台批处理机生产与生产前运输的协调调度问题,目标函数为最小化与完成时间相关的生产总成本.以工件为博弈方,以联盟的最大成本节省为特征函数,将调度问题转换为合作博弈模型.针对相同运输时间与加工时间的情形,证明该合作博弈具有非空核,beta规则可得一个核分配.针对一般问题,设计Q-learning算法求解联盟最优调度,并利用beta规则对节省的成本进行分配.数值算例验证了合作博弈模型的可行性以及Q-learning算法与beta规则对节省成本分配的有效性.     

Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability

This article considers the unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times and machine-dependent processing times. Furthermore, the machine has a production availability constraint to each job. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the total completion time. To solve the problem, a mathematical model for the optimal solution is derived, and hybrid genetic algorithms with three dispatching rules are proposed for large-sized problems. To assess the performance of the algorithms, computational experiments are conducted and evaluated using several randomly generated examples.     

求解考虑机器调整时间的并行机分批优化调度问题

基于目前车间调度问题是以单个或整批进行生产加工的并行机调度模型已不再符合实际工况下的车间生产。提出以最小化最大完工时间为优化目标,对遗传差分进化混合算法,灰狼差分进化混合算法进行了比较。为提高加工工件进行分批及分批之后子批的分配与排序效率,该问题是对不同规模的经典并行机调度问题进行求解并展示两种算法的求解,证明了灰狼差分进化混合算法在寻优性能上优于遗传差分进化混合算法,不仅具有更好的解的稳定性,而且具有更高的寻优精度。     

Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm

The problem of parallel machine scheduling for minimizing the makespan is an open scheduling problem with extensive practical relevance. It has been proved to be non-deterministic polynomial hard. Considering a job’s batch size greater than one in the real manufacturing environment, this paper investigates into the parallel machine scheduling with splitting jobs. Differential evolution is employed as a solution approach due to its distinctive feature, and a new crossover method and a new mutation method are brought forward in the global search procedure, according to the job splitting constraint. A specific local search method is further designed to gain a better performance, based on the analytical result from the single product problem. Numerical experiments on the performance of the proposed hybrid DE on parallel machine scheduling problems with splitting jobs covering identical and unrelated machine kinds and a realistic problem are performed, and the results indicate that the algorithm is feasible and efficient.     

带尺寸约束的二机流水车间生产运输协调博弈调度问题

研究二机流水车间生产运输协调调度问题,当工件在第1台机器加工完成后,由1台带有容量限制的运输车分批次运输到第2台机器加工,运输过程考虑工件尺寸约束,目标函数为最小化最大完工时间.考虑到源于不同客户的工件对机器及运输设备的竞争,以工件为博弈方,工件在生产运输过程中等待时间为策略,各工件完工时间为收益,建立非合作博弈模型.通过将问题转化为马尔可夫决策过程,设计线性逼近值函数的Q-learning算法求解纳什均衡调度.实验结果表明Q-learning算法求得的纳什均衡调度具有较好的全局最优性,从而能够在满足客户的利益下,提高企业的生产效率,实现客户与企业的双赢.