Automatic design for shop scheduling strategies based on hyper-heuristics: A systematic review

Against the background of smart manufacturing and Industry 4.0, how to achieve real-time scheduling has become a problem to be solved. In this regard, automatic design for shop scheduling based on hyper-heuristics has been widely studied, and a number of reviews and scheduling algorithms have been presented. Few studies, however, have specifically discussed the technical points involved in algorithm development. This study, therefore, constructs a general framework for automatic design for shop scheduling strategies based on hyper-heuristics, and various state-of-the-art technical points in the development process are summarized. First, we summarize the existing types of shop scheduling strategies and classify them using a new classification method. Second, we summarize an automatic design algorithm for shop scheduling. Then, we investigate surrogate-assisted methods that are popular in the current algorithm field. Finally, current problems and challenges are discussed, and potential directions for future research are proposed.     

Generation expansion planning in electricity markets: A novel framework based on dynamic stochastic MPEC

This paper presents a novel framework for generation expansion planning (GEP) of restructured power systems under uncertainty in a multi-period horizon, which includes generation investment from a price maker perspective. The investment problem is modeled as a bi-level optimization problem. The first level problem includes decisions related to investment in order to maximize total profit in the planning horizon. The second level problem consists of maximizing social welfare where the power market is cleared. Rival uncertainties on offering and investment are modeled using sets of scenarios. The bi-level optimization problem is then converted to a dynamic stochastic MPEC and represented as a mixed integer linear program (MILP) after linearization. The proposed framework is examined on a typical six-bus power network, MAZANDARAN regional electric company (MREC) transmission network as an area of IRAN interconnected power system and IEEE RTS 24-bus network. Simulation results confirm that the proposed framework can be a useful tool for analyzing the behavior of investments in electricity markets.     

A practical assessment of risk-averse approaches in production lot-sizing problems

ABSTRACT

This paper presents an empirical assessment of four state-of-the-art risk-averse approaches to deal with the capacitated lot-sizing problem under stochastic demand. We analyse two mean-risk models based on the semideviation and on the conditional value-at-risk risk measures, and alternate first and second-order stochastic dominance approaches. The extensive computational experiments based on different instances characteristics and on a case-study suggest that CVaR exhibits a good trade-off between risk and performance, followed by the semideviation and first-order stochastic dominance approach. For all approaches, enforcing risk-aversion helps to reduce the cost-standard deviation substantially, which is usually accomplished via increasing production rates. Overall, we can say that very risk-averse decision-makers would be willing to pay an increased price to have a much less risky solution given by CVaR. In less risk-averse settings, though, semideviation and first-order stochastic dominance can be appealing alternatives to provide significantly more stable production planning costs with a marginal increase of the expected costs.     

Lagrangian relaxation hybrid with evolutionary algorithm for short-term generation scheduling

Short-term generation scheduling is an important function in daily operational planning of power systems. It is defined as optimal scheduling of power generators over a scheduling period while respecting various generator constraints and system constraints. Objective of the problem includes costs associated with energy production, start-up cost and shut-down cost along with profits. The resulting problem is a large scale nonlinear mixed-integer optimization problem for which there is no exact solution technique available. The solution to the problem can be obtained only by complete enumeration, often at the cost of a prohibitively computation time requirement for realistic power systems. This paper presents a hybrid algorithm which combines Lagrangian Relaxation (LR) together with Evolutionary Algorithm (EA) to solve the problem in cooperative and competitive energy environments. Simulation studies were carried out on different systems containing various numbers of units. The outcomes from different algorithms are compared with that from the proposed hybrid algorithm and the advantages of the proposed algorithm are briefly discussed.     

基于组合双向拍卖的云资源调度方法

针对跨数据中心的资源调度问题，提出了一种基于组合双向拍卖（PCDA）的资源调度方案。首先，将云资源拍卖分为三个部分：云用户代理报价、云资源提供商要价、拍卖代理组织拍卖；其次，在定义用户的优先级及任务紧迫度的基础上，在拍卖过程中估算每一个工作发生的服务等级协议（SLA）违规并以此计算云提供商的收益，同时每轮竞拍允许成交多项交易；最终达到根据用户等级合理分配云资源调度的效果。仿真实验结果表明该算法保证了竞拍成功率，与传统一次拍卖成交一项的组合双向拍卖方案相比，PCDA在竞拍时间段产生的能耗降低了35.00%，拍卖云提供商的利润提高了约38.84%。     

Supply chain planning and scheduling integration using Lagrangian decomposition in a knowledge management environment

The integration of planning and scheduling decisions in rigorous mathematical models usually results in large scale problems. In order to tackle the problem complexity, decomposition techniques based on duality and information flows between a master and a set of subproblems are widely applied. In this sense, ontologies improve information sharing and communication in enterprises and can even represent holistic mathematical models facilitating the use of analytic tools and providing higher flexibility for model building. In this work, we exploit this ontologies’ capability to address the optimal integration of planning and scheduling using a Lagrangian decomposition approach. Scheduling/planning sub-problems are created for each facility/supply chain entity and their dual solution information is shared by means of the ontological framework. Two case studies based on a STN representation of supply chain planning and scheduling models are presented to emphasize the advantages and limitations of the proposed approach.     

Improved Input and State Estimation for Linear Stochastic Systems with Direct Feedthrough

This paper is concerned with the problem of joint input and state estimation for linear stochastic systems with direct feedthrough. Based on the fact that each unknown input between any two time steps is always bounded, a novel improved algorithm is proposed. Compared with existing results, this algorithm can effectively enhance estimation accuracy. Moreover, the stability of the algorithm is also discussed. Finally, an illustrative example is given to demonstrate the effectiveness of the proposed approach.     

Multi-resource scheduling for FPGA systems

In modern cloud data centers, reconfigurable devices (FPGAs) are used as an alternative to Graphics Processing Units to accelerate data-intensive computations (e.g., machine learning, image and signal processing). Currently, FPGAs are configured to execute fixed workloads, repeatedly over long periods of time. This conflicts with the needs, proper to cloud computing, to flexibly allocate different workloads and to offer the use of physical devices to multiple users. This raises the need for novel, efficient FPGA scheduling algorithms that can decide execution orders close to the optimum in a short time. In this context, we propose a novel scheduling heuristic where groups of tasks that execute together are interposed by hardware reconfigurations. Our contribution is based on gathering tasks around a high-latency task that hides the latency of tasks, within the same group, that run in parallel and have shorter latencies. We evaluated our solution on a benchmark of 37500 random workloads, synthesized from realistic designs (i.e., topology, resource occupancy). For this testbench, on average, our heuristic produces optimum makespan solutions in 47.4% of the cases. It produces acceptable solutions for moderately constrained systems (i.e., the deadline falls within 10% of the optimum makespan) in 90.1% of the cases.     

Demand response for home energy management system

The optimization of energy consumption, with consequent cost reduction, is one of the main challenges for the present and future smart grid. Demand response (DR) program is expected to be vital in home energy management system (HEMS) which aims to schedule the operation of appliances to save energy costs by considering customer convenience as well as characteristics of electric appliances. The DR program is a challenging optimization problem especially when the formulations are non-convex or NP-hard problems. In order to solve this challenging optimization problem efficiently, an effective heuristic approach is proposed to achieve a near optimal solution with low computational costs. Different from previously proposed methods in literatures which are not suitable to be run in embedded devices such as a smart meter. The proposed algorithm can be implemented in an embedded device which has severe limitations on memory size and computational power, and can get an optimal value in real-time. Numerical studies were carried out with the data simulating practical scenarios are provided to demonstrate the effectiveness of the proposed method.     

Systematic convergence of nonlinear stochastic estimators on the Special Orthogonal Group SO(3)

This paper introduces two novel nonlinear stochastic attitude estimators developed on the Special Orthogonal Group with the tracking error of the normalized Euclidean distance meeting predefined transient and steady‐state characteristics. The tracking error is confined to initially start within a predetermined large set such that the transient performance is guaranteed to obey dynamically reducing boundaries and decrease smoothly and asymptotically to the origin in probability from almost any initial condition. The proposed estimators produce accurate attitude estimates with remarkable convergence properties using measurements obtained from low‐cost inertial measurement units. The estimators proposed in continuous form are complemented by their discrete versions for the implementation purposes. The simulation results illustrate the effectiveness and robustness of the proposed estimators against uncertain measurements and large initialization error, whether in continuous or discrete form.