University Class Scheduling Problem (UCSP) is an inevitable task every university must go through prior to the commencement of a semester. The problem studied in this paper is decomposed into two stages - lab scheduli...
详细信息
University Class Scheduling Problem (UCSP) is an inevitable task every university must go through prior to the commencement of a semester. The problem studied in this paper is decomposed into two stages - lab scheduling and theoretical class scheduling. This novel technique of decomposition of the problem not only allowed maximum number of free variables to stricter constraints found in lab scheduling, but also reduced the overall computational cost and combinatorial complexity. The mathematical model for the problem is formulated via binary integer linear programming (BILP) structure using data collected from the department considered in the study. Part of the contribution of this work also includes developing ways to recognize only the true variables while formulating the model. The model is then optimized using the simplex method with the objectives to optimize classroom utilization and faculty preferences while fulfilling additional constraints. Furthermore, the proposed method is compared to the traditional technique in which the model is optimized in a single stage with both true variables recognized and not recognized.
This paper studies a single-stage train formation problem in railway marshaling stations, aiming to efficiently assign railcars to classification tracks with one roll-in and one pull-out operation for ensuring the for...
详细信息
This paper studies a single-stage train formation problem in railway marshaling stations, aiming to efficiently assign railcars to classification tracks with one roll-in and one pull-out operation for ensuring the formation of outbound trains. Assigning railcars to classification tracks by blocks (block-to-track), by outbound trains (train-to-track), and by need (railcar-to-track) are three typical policies widely addressed in the literature. An extended railcar-to-track policy is investigated by combining the first and third policies, where railcars are preferentially assigned to their fixed-use classification tracks through a specified block-to-track scheme and then to other classification tracks if necessary, while re-humping and re-sorting operations are eliminated. We formulate the formation problem under this policy as a binarylinearprogramming model with the objective of minimizing the total weighted cost required for train formation, including both the weighted roll-in cost and the weighted pull-out cost. A two-phase decomposition algorithm, which divides our model into a roll-in and a pull-out subproblem, is developed to improve the solving efficiency. For the roll-in subproblem, a novel group-indexed model is constructed to determine a railcar-to-track scheme with minimal total weighted roll-in cost and simplified pull-out cost. For the following pull-out subproblem, the objective is to determine a pull-out scheme that minimizes the total weighted pull-out cost. This subproblem is decomposed further into multiple simplified problems, each of which is formulated into a quadratic assignment model for each outbound train, enabling rapid solving times of this subproblem. Computational results on a set of realistic instances reveal that our algorithm outperforms two benchmark approaches, in which the roll-in subproblem is formulated respectively as a big-M and an arc-indexed model inspired by existing models, and an imitated empirical approach used in practic
In a busy railway marshalling station, train and engine traffic management in the receiving/departure yard plays a crucial role in efficient and stable operations. Traditionally, a track assignment problem (TAP) is so...
详细信息
In a busy railway marshalling station, train and engine traffic management in the receiving/departure yard plays a crucial role in efficient and stable operations. Traditionally, a track assignment problem (TAP) is solved to assign tracks to trains for berthing at a receiving/departure yard. However, the TAP does not encompass shunting operations in the yard (e.g., engine replacement and train disassembly), which can result in additional scheduling challenges for dispatchers and route conflicts between operations. This paper investigates a train and engine routing and scheduling problem (TERSP) in a receiving/departure yard of railway marshalling stations, which involves simultaneously assigning routes and scheduling route-setting start times for both train and shunting operations to be conducted in the yard. By introducing the concepts of task, activity, and pattern, we transform the original problem into assigning pre-generated patterns incorporating both route and route-setting start time alternatives to activities. The transformed problem is formulated into a compact binary integer linear programming model with a linear number of constraints and the objective of minimizing the total time deviation of all involved tasks. An improved technique that relies on listing all maximal (bi)cliques in a constructed graph is designed to effectively model the time coherence and track section occupation constraints. A heuristic that gradually expands the patterns for the identified key activities by adding more start time alternatives is applied to remedy an infeasible model caused by potential route conflicts. In addition, a rolling horizon algorithm that decomposes the original problem into consecutive smaller stages using either a time-rolling or a train-rolling rule is developed to efficiently solve instances. Finally, numerical experiments based on the physical layouts and real timetables of a receiving yard and a departure yard of a large marshalling station in China ar
With the advent of the Internet of Things (IoT), novel critical applications have emerged that leverage the edge/hub/cloud paradigm, which diverges from the conventional edge computing perspective. A growing number of...
详细信息
With the advent of the Internet of Things (IoT), novel critical applications have emerged that leverage the edge/hub/cloud paradigm, which diverges from the conventional edge computing perspective. A growing number of such applications require a streamlined architecture for their effective execution, often comprising a single edge device with sensing capabilities, a single hub device (e.g., a laptop or smartphone) for managing and assisting the edge device, and a more computationally capable cloud server. Typical examples include the utilization of an unmanned aerial vehicle (UAV) for critical infrastructure inspection or a wearable biomedical device (e.g., a smartwatch) for remote patient monitoring. Task allocation in this streamlined architecture is particularly challenging, due to the computational, communication, and energy limitations of the devices at the network edge. Consequently, there is a need for a comprehensive framework that can address the specific task allocation problem optimally and efficiently. To this end, we propose a complete, binary integer linear programming (BILP) based formulation for an application -driven design -time approach, capable of providing an optimal task allocation in the targeted edge/hub/cloud environment. The proposed method minimizes the desired objective, either the overall latency or overall energy consumption, while considering several crucial parameters and constraints often overlooked in related literature. We evaluate our framework using a realworld use -case scenario, as well as appropriate synthetic benchmarks. Our extensive experimentation reveals that the proposed approach yields optimal and scalable results, enabling efficient design space exploration for different applications and computational devices.
Phasor measurement units(PMUs)are preferred for installation at weak buses in a power ***,the weak buses need to be located and the strategic locations of PMUs identified to ensure network ***,the primary aim of this ...
详细信息
Phasor measurement units(PMUs)are preferred for installation at weak buses in a power ***,the weak buses need to be located and the strategic locations of PMUs identified to ensure network ***,the primary aim of this work is to identify the placements of the maximum number of PMUs installed at the weak buses in the electrical *** voltage collapse proximity indicator,line stability index,fast voltage stability index,and a new voltage stability indicator utilizing load flow measurement are used to determine the weak buses.A novel deterministic methodology based on a binary-integerlinearprogramming model is then proposed to determine the optimal locations of *** effect of a single PMU outage considering the weak buses is also *** effectiveness of the developed approach is tested and validated on the standard IEEE 14-,118-,300-,and New England 39-bus *** obtained results are also compared to those using different weak bus methodologies.
The availability of satellite communication systems is extremely limited by atmospheric impairments, such as rain (for radio frequencies) and cloud coverage (for optical frequencies). A solution to this problem is the...
详细信息
The availability of satellite communication systems is extremely limited by atmospheric impairments, such as rain (for radio frequencies) and cloud coverage (for optical frequencies). A solution to this problem is the site diversity technique, where a network of geographically distributed ground stations (GSs) can ensure, with high probability, that at least one GS is available for connection to the satellite at each time period. However, the installation of redundant GSs induces unnecessary additional costs for the network operator. In this context, we study an optimization problem that minimizes the number of required GSs, subject to availability constraints. First, the problem is transformed into a binary-integer-linear-programming (BILP) problem, which is proven to be NP-hard. Subsequently, we design a branch-and-bound (B&B) algorithm, with global-optimization guarantee, based on the linear-programming (LP) relaxation and a greedy method as well. Finally, numerical results show that the proposed algorithm significantly outperforms state-of-the-art methods, and has low complexity in the average case.
This paper proposes a mixed integer nonlinearprogramming (MINLP) formulation with binary-valued variables for the optimal installation of the phasor measurement units (PMUs) in a power network. The MINLP framework ha...
详细信息
This paper proposes a mixed integer nonlinearprogramming (MINLP) formulation with binary-valued variables for the optimal installation of the phasor measurement units (PMUs) in a power network. The MINLP framework has been solved by a two-phase branch-and-bound algorithm (BBA) for the optimal PMU placement (OPP) problem. The present work deals with the solution of the OPP problem without considering the radial buses including in the optimal solution. PMU is pre-assigned to each bus connected to a radial bus such that the radial buses are excluded from the list of potential PMU locations. The programming technique is used to determine the optimum number of PMUs and their locations to make the interconnected power network completely observable. The proposed BBA may provide multiple solutions at the lowest objective value, each time the optimizer routine restarts. Therefore, the obtained optimal solutions are being ranked regarding the measurement redundancy index. The two-phase branch-and-bound algorithm is applied to IEEE standard test systems as well as to New England 39-bus and a northern regional power grid 246-bus system. The proposed algorithm has been compared with the existing programming techniques in the recent literature. The simulation results obtained by the proposed BBA indicate the effectiveness and the efficiency to detect the desired target. (C) 2018 Elsevier Ltd. All rights reserved.
The separating redundancy is an important property in the analysis of the error-and-erasure decoding of a linear block code. In this work, we investigate the separating redundancy of the duals of first-order generaliz...
详细信息
The separating redundancy is an important property in the analysis of the error-and-erasure decoding of a linear block code. In this work, we investigate the separating redundancy of the duals of first-order generalized Reed-Muller (GRM) codes, a class of nonbinarylinear block codes that have nice algebraic properties. The dual of a first-order GRM code can be specified by two positive integers m and q and denoted by R (m, q), where q is the power of a prime number and q not equal 2. We determine the first separating redundancy value of R (m, q) for any m and q. We also determine the second separating redundancy values of R (m, q) for any q and m = 1 and 2. For m >= 3, we set up a binary integer linear programming problem, the optimum of which gives a lower bound on the second separating redundancy of R (m, q).
This paper discusses an experimental study of the home appliances scheduling problem that incorporates realistic aspects. The residential load scheduling problem is solved while considering consumer's preferences....
详细信息
This paper discusses an experimental study of the home appliances scheduling problem that incorporates realistic aspects. The residential load scheduling problem is solved while considering consumer's preferences. The objective function minimizes the weighted sum of electricity cost by earning relevant incentives, and the scheduling inconvenience. The objective of this study is five-fold. First, it sought to develop and solve a binary integer linear programming optimization model for the problem. Second, it examined the factors that might affect the obtained schedule of residential loads. Third, it aimed to test the performance of a developed optimization model under different experimental scenarios. Fourth, it proposes a conceptual definition of a new parameter in the problem, the so-called "flexibility ratio". Finally, it adds a data set for use in the literature on the home appliance scheduling problem, which can be used to test the performance of newly-developed approaches to the solution of this problem. This paper presents the results of experimental analysis using four factors: problem size, flexibility ratio, time slot length and the objective function weighting factor. The experimental results show the main and interaction effects, where these exist, on three performance measures: the electricity cost, inconvenience and the optimization model computation time. (C) 2018 Elsevier Ltd. All rights reserved.
Cell densification is being perceived as the panacea for the imminent capacity crunch. However, high aggregated energy consumption and increased inter-cell interference (ICI) caused by densification, remain the two lo...
详细信息
Cell densification is being perceived as the panacea for the imminent capacity crunch. However, high aggregated energy consumption and increased inter-cell interference (ICI) caused by densification, remain the two long-standing problems. We propose a novel network orchestration solution for simultaneously minimizing energy consumption and ICI in ultra-dense 5G networks. The proposed solution builds on a big data analysis of over 10 million CDRs from a real network that shows there exists strong spatio-temporal predictability in real network traffic patterns. Leveraging this, we develop a novel scheme to pro-actively schedule radio resources and small cell sleep cycles yielding substantial energy savings and reduced ICI, without compromising the users QoS. This scheme is derived by formulating a joint Energy Consumption and ICI minimization problem and solving it through a combination of linearbinaryintegerprogramming, and progressive analysis based heuristic algorithm. Evaluations using: 1) a HetNet deployment designed for Milan city where big data analytics are used on real CDRs data from the Telecom Italia network to model traffic patterns, 2) NS-3 based Monte-Carlo simulations with synthetic Poisson traffic show that, compared to full frequency reuse and always on approach, in best case, the proposed scheme can reduce energy consumption in HetNets to 1/8th while providing same or better QoS.
暂无评论