Search

In response to the challenges posed by economic globalisation and increasing customer demands, enterprises are compelled to adapt and refine their production models and operational objectives, which motivates this paper to address the integrated production scheduling and vehicle routing problem in the distributed manufacturing environment (IPSVRP-DME). The objective is to simultaneously minimise both total energy consumption and total earliness/tardiness. Initially, a mixed integer programming model is proposed to address small-scale problems using Gurobi. Considering the NP-hardness of the problem, a novel Self-adapted Gaussian Mutation-based Arithmetic Optimiser Algorithm (SGMAOA) is developed to handle medium-scale and large-scale instances. To address the complexity of decision-making, an innovative two-level encoding method that encompasses four decision dimensions is introduced. Additionally, an incremental repair strategy is devised to rectify infeasible solutions caused by unreasonable delivery batching, while a time relaxation strategy is proposed to further enhance service levels without compromising energy consumption. Comparative experiments are conducted to demonstrate the effectiveness of SGMAOA, which is benchmarked against five prominent metaheuristics. In addition, a specific example is applied for the discussion of managerial applications and to illustrate the practicality of the proposed model and solution method. [ABSTRACT FROM AUTHOR]

With the service level playing an increasingly essential role in the service-oriented manufacturing (SOM) supply chain, the distribution network design can be heavily affected by the customer behaviour based on their satisfaction of services. In this paper, we consider the service level for service time and delivery quantity separately. A novel mixed integer non-linear programming model is proposed to design the multi-period distribution network from a fourth-party logistics (4PL) perspective. The customer satisfaction based on prospect theory is maximised while considering the investment budget and the service level. A scenario-based linear reformulation is proposed to find the optimal solution when the problem scale is small. For a large-scale problem, we propose an individual-driven Q-learning based memetic particle swarm optimisation algorithm. Numerical experiments are conducted to demonstrate the effectiveness and efficiency of the proposed algorithm. Furthermore, the impact of service modes, different customer behaviour, and customer satisfaction evaluation periods on distribution network is investigated. We find that the length of evaluation periods leads to differences in customer satisfaction due to different perceptions of 'small loss' and 'big gain' by boundedly rational customers. [ABSTRACT FROM AUTHOR]

A bi-objective distributed flow-shop scheduling problem with multistep electricity pricing and carbon emissions is studied. One objective is to minimise the completion time of production, and the other is to minimise the total cost of multistep electricity pricing and carbon emissions. A mixed integer programming model and a two-stage knowledge based cooperative algorithm with a local reinforcement strategy are proposed for the problem. The extensive numerical experiments show that the two-stage algorithm was effective statistical significantly in generating non-dominated solution sets and Pareto frontiers. Simulations on Electricity Prices are applied to examine different multistep electricity pricing schemes, and management implications were drawn for both government and companies. [ABSTRACT FROM AUTHOR]

This paper studies the constrained two-dimensional non-guillotine cutting problem with defects, in which a set of items of a specific size is cut from a large rectangular sheet with defective areas, with the number of each type of cut item cannot exceed a specified quantity. The objective is to maximise the total value of the cut items. We propose a decomposition approach to address the problem. The process involves decomposing the original problem into a master problem and a subproblem. The master problem is formulated as a one-dimensional contiguous bin packing problem, while the subproblem is an x-Check problem to identify a two-dimensional packing that does not lead to any overlap. The x-Check problem is effectively addressed by using an integer linear programming model. When the x-Check problem proves infeasible, cuts are added to the master problem, and the iteration is repeated until the x-Check finds a feasible solution. Furthermore, we introduce several novel techniques, including valid inequalities, preprocessing techniques, and lifting the cut methods to improve the performance of the algorithm. Extensive computational results show that our method can quickly find the optimal solution for the 5450 instances in the literature. [ABSTRACT FROM AUTHOR]

The solution to the assembly line balancing with the hierarchical worker assignment problem (ALBHWP) provides the optimal allocation of workers and tasks to the stations that minimise the total worker cost. In the ALBHWP, tasks differ in terms of the qualification requirements of workers, and the qualification levels of workers are hierarchical. In the hierarchical workforce structure, a lower qualified worker can be replaced by higher qualified ones with higher costs, while the vice versa is not applicable. This problem has only been studied for straight assembly lines so far. In this paper, we introduce the ALBHWP for U-shaped assembly lines. We developed integer and constraint programming models for solving the ALBHWP and compared their effectiveness using an extensive set of benchmark instances. We solved the ALBHWP for straight and U-shaped assembly lines comparatively. Constraint programming models have been statistically proven to provide better quality solutions faster than integer programming models. Besides, the CP model outperforms the only available metaheuristic in the literature for the S-ALBHWP in almost all problem sizes. Another observation is that a U-shaped line design is more cost-effective than a straight line design, but solving the ALBHWP for U-shaped lines is more difficult regarding computational complexity. [ABSTRACT FROM AUTHOR]

Modular integrated construction (MiC) is an innovative construction method that is widely used in practice, but high transportation cost is an obstacle to its wider implementation. This paper is motivated by the real-world need for a scientific approach for MiC transport scheduling, and addresses the practical problem of how to achieve on-time door-to-door MiC delivery in an economical manner. An innovative integer programming model is formulated with the objective of minimising the total transportation costs, including trailer rental, fuel costs, and worker salaries. A case study based on Hong Kong data validates that the developed model can be efficiently solved for problems of practical size. The results also demonstrate that the derived MiC schedule plan can reduce transportation costs by 58.7% compared with a just-in-time (JIT) strategy, thus bringing great economic benefits to off-site construction practitioners. Useful managerial implications related to on-site MiC storage areas are derived through sensitivity analysis. Overall, this paper sets the ground for the application of mathematical programming methodology to the off-site construction field. Future research may be devoted to MiC transport scheduling under uncertainty. [ABSTRACT FROM AUTHOR]

Human-robot collaborative disassembly lines are widely used by remanufacturing companies to disassemble end-of-life (EOL) products. When disassembling large-sized EOL products, each workstation on a disassembly line is generally divided into multiple operating positions, so that different operators can disassemble the same product at their respective positions at the same time, thereby greatly improving efficiency. This paper focuses on a position-constrained human-robot collaborative disassembly planning (PC-HRCDP) problem for the above-mentioned lines, including three subproblems of disassembly sequence planning, disassembly line balancing and robot path planning. A multi-objective mixed integer programming model for PC-HRCDP is developed to solve smallscale instances. Furthermore, a multi-objective multi-fidelity optimisation (MO-MFO) algorithm is proposed to solve large-scale instances. Comprehensive experiments are conducted based on 10 problem instances generated in this study. Experimental results show that the proposed MO-MFO is better than a high-fidelity optimisation algorithm in terms of running time. In addition, benefiting from the strategy of MO-MFO to allocate the limited high-fidelity computational budget to solutions in the two stages of multi-objective optimisation and optimal sampling, MO-MFO is significantly better than the existing representative multi-fidelity optimisation algorithms in terms of the hyper-volume and the inverted generational distance. [ABSTRACT FROM AUTHOR]

The train stowage planning problem (TSPP) of the steel industry aims to select steel coils and allocate them to trains cost-effectively. It is a key component in the transportation of steel products. This study focuses on a multiobjective train stowage planning problem (MoTSPP) that maximises both the loading efficiency of the crane and the loading rate of the train. The MoTSPP also considers operation constraints related to steel coils, train wagons, and stowage modes in real-life railway transportation. An integer programming model is established to mathematically describe this problem. To obtain an efficient solution, a multiobjective analytical evolutionary algorithm (MAEA) that combines evolutionary algorithm (EA) with machine learning (ML) is presented. The EA part is a multiobjective differential evolution that introduces guided evolution and parameter adaptation to produce promising individuals and parameters, respectively. ML part adopts clustering algorithm and surrogate model to accelerate the search. Extensive comparisons and insight analyses are conducted from various perspectives to demonstrate the effectiveness and efficiency of the MAEA for solving the MoTSPP. [ABSTRACT FROM AUTHOR]

In this paper, stochastic optimisation of CVaR is applied to maintain risk-averse viability and improve resilience of a supply chain under propagated disruptions. In order to establish the risk-averse boundaries on supply chain viability space, two stochastic optimisation models are developed with the two conflicting objectives: minimisation of Conditional Cost-at-Risk and maximisation of Conditional Service-at-Risk. Then, the risk-averse viable production trajectory between the two boundaries is selected using a stochastic mixed integer quadratic programming model. The proposed approach is applied to maintain the supply chain viability in the smartphone manufacturing and the results of computational experiments are provided. The findings indicate that when the decision-making is more risk-aversive, the size of the viability space between the two boundaries is greater. As a result, more room is available for selecting viable production trajectories under severe disruptions. Moreover, the larger is viability space, the higher is both worst-case and average resilience of the supply chain. Risk-neutral, single-objective decision-making may reduce the supply chain viability. A single-objective supply chain optimisation which moves production to the corresponding boundary of the viability space, should not be applied under severe disruption risks to avoid greater losses. [ABSTRACT FROM AUTHOR]

Tree search algorithms, such as branch-and-bound, are the most widely used tools for solving combinatorial and non-convex problems. For example, they are the foremost method for solving (mixed) integer programs and constraint satisfaction problems. Tree search algorithms come with a variety of tunable parameters that are notoriously challenging to tune by hand. A growing body of research has demonstrated the power of using a data-driven approach to automatically optimize the parameters of tree search algorithms. These techniques use a training set of integer programs sampled from an application-specific instance distribution to find a parameter setting that has strong average performance over the training set. However, with too few samples, a parameter setting may have strong average performance on the training set but poor expected performance on future integer programs from the same application. Our main contribution is to provide the first sample complexity guarantees for tree search parameter tuning. These guarantees bound the number of samples sufficient to ensure that the average performance of tree search over the samples nearly matches its future expected performance on the unknown instance distribution. In particular, the parameters we analyze weight scoring rules used for variable selection. Proving these guarantees is challenging because tree size is a volatile function of these parameters: we prove that, for any discretization (uniform or not) of the parameter space, there exists a distribution over integer programs such that every parameter setting in the discretization results in a tree with exponential expected size, yet there exist parameter settings between the discretized points that result in trees of constant size. In addition, we provide data-dependent guarantees that depend on the volatility of these tree-size functions: our guarantees improve if the tree-size functions can be well approximated by simpler functions. Finally, via experiments, we illustrate that learning an optimal weighting of scoring rules reduces tree size. [ABSTRACT FROM AUTHOR]

Reconfigurable manufacturing systems (RMS) intend to bridge the gap between dedicated and flexible manufacturing systems. If the literature is mainly focused on the design step and tactical planning of such systems, few research projects have addressed scheduling at the operational level. While setup times may occur in flexible manufacturing systems, reconfiguration times considered in RMS may affect several resources at once, and hence require specific modelling and solving approaches to be considered. This paper first formalises the problem at hand through integer linear programming. An iterative search method is then provided to obtain solutions to larger-scale instances. Results obtained on generated instances show that managing even few possible configurations can yield significant improvements in solutions' quality. Meanwhile, the extended search space implied by the increase in available configurations hinders the convergence to a good solution in a reasonable computation time, which suggests further investigations. [ABSTRACT FROM AUTHOR]

A class of strong lower bounds on the solution value of a Linearised Integer Programming reformulation is introduced for the binary quadratic optimisation model to assign origin and destination nodes to strip and stack doors, resp., in a cross-dock infrastructure. The goal is to minimise the transportation cost of the commodities to be handled at the cross-dock. Strip- and stack-related decomposition submodels are developed by taking benefit of the Integer Linearisation Property that appears in the new model. A linear search heuristic is also provided for obtaining feasible solutions by exploiting the special structure of the problem. We present an extensive computational study on a testbed of 55 instances to show that the proposed joint scheme for lower bounding and feasible solution providing is very efficient. The results obtained by our proposal are similar to those obtained by CPLEX in the 50 instances taken from the literature, but usually the time is much smaller for the large instances. The comparison with CPLEX is particularly good for the new five largest instances, which make it very promising for its application in real-life cases. [ABSTRACT FROM AUTHOR]

Dynamic facility layout planning (DFLP) involves determining an appropriate arrangement scheme of the elements making up the production system for each time period into which the planning horizon is divided. When formulating the problem as an optimisation model, using the traditional top-down approach is usual, which firstly determines the block layout (BL) and then the detailed layout (DL) of each work cell. However by this approach, the BL generates area constraints in the detailed phase, which sometimes limit its implementation. In this context, the present paper presents a multi-objective mixed integer non-linear programming (MOMINLP) model that allows the problem to be addressed by considering an alternative approach, known in the literature as the bottom-up approach. The proposed model, called bottom-up mDFLP, considers three objective functions: (1) minimise the total material handling cost (TMHC) and the total rearrangement cost (TRAC); (2) maximise the total closeness rating (TCR) between departments; (3) maximise the area utilisation ratio (AUR). The original MOMINLP is transformed into a more computationally efficient multi-objective mixed integer linear programming (MOMILP) model. The proposed model is applied and validated in a case study of a company in the metal-mechanic sector with 12 departments for three 4-month periods. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the non-unit demand capacitated minimum spanning tree problem with arc time windows and flow costs. The problem is a variant of the capacitated minimum spanning tree problem with arc time windows (CMSTP_ATW). We devise a mixed integer programming (MIP) formulation to model the problem and solve it using CPLEX. Furthermore, we propose three sets of inequalities, and we prove that they are valid. These valid inequalities tighten the model and lead to better lower bounds. To examine the quality of the solutions obtained, we convert the original data sets of Solomon (1987, "Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints." Operations Research 35 (2): 254–265. ) to approximate the non-unit demand CMSTP_ATW instances and provide results for the problems with 100 nodes. We execute extensive computational experiments, and the results show the positive effect of the inclusion of valid inequalities in the MIP. [ABSTRACT FROM AUTHOR]

Urged by the necessity to establish sustainable supply chains (SCs), this study focuses on exploring the closed-loop inventory routing problem (CIRP) for perishable food packed by multi-type returnable transport items (RTIs). The selling revenue of perishable food is dependent on food's remaining shelf life and the specific type of RTIs used for packaging. RTI selection decisions need to be jointly considered in the CIRP to weigh the potential benefits against associated costs. For this problem, we first develop an integer linear programme (ILP) to maximise the total profit of the holistic SC. Subsequently, we design a tailored kernel search (KS) matheuristic as an efficient solution. A real CIRP with multi-type RTIs for fresh strawberries is used to demonstrate the practicality of the ILP. For this case study, we perform extensive sensitivity analysis of the relevant parameters, extracting valuable managerial insights. Finally, experiments are conducted on 170 randomly generated instances. Computational results show that the proposed KS manages to achieve competitive solutions for instances with up to 10 retailers much more efficiently than CLPEX. For instances with up to 40 retailers, the KS algorithm significantly outperforms CPLEX in terms of solution quality, improving the obtained profit by 80.03% on average under the same computational time. [ABSTRACT FROM AUTHOR]

In this paper, a new mixed integer programming (MIP) formulation is developed for balancing and scheduling of mixed model assembly lines with disjunctive precedence constraints among assembly tasks. To represent alternative precedence relations, AND/OR assembly graph was adopted. In case of alternative precedence relations, for each product multiple assembly plans exist, which can be represented by a set of alternative precedence subgraphs and only one of such subgraphs should be selected for each product. As the number of subgraphs exponentially increases with the number of disjunctive relations among the tasks, the computational complexity of simultaneous balancing and scheduling along with the assembly subgraph selection increases with the number of alternative precedence relations. Unlike the other MIP approaches known from the literature, the new model does not need the alternative assembly subgraphs to be to explicitly enumerated as input data and then used for indexing the variables. Instead, a new disjunctive precedence selection and task assignment variable and new constraints are introduced to optimally choose one relation for each subset of alternative precedence relations. The optimal solutions for computational examples of balancing and scheduling problems illustrate a superior performance of the new modelling approach. [ABSTRACT FROM AUTHOR]

In the era of Industry 4.0, the demand fluctuation has become fiercer due to the characteristics of diversification, customisation, and uncertainty. Reconfigurability of manufacturing systems has been proven to be a useful and necessary feature when it comes to handling demand uncertainty. This feature can be achieved through the implementation of reconfigurable manufacturing system (RMS) and delayed reconfigurable manufacturing system (D-RMS). D-RMS is a subclass of RMS that focuses primarily on improving the convertibility of the manufacturing system. The two main phases involved in implementing D-RMS are part family formation and configuration design. Therefore, we proposed a multi-objective joint optimisation method of part family formation and configuration design according to the philosophy of D-RMS. Firstly, we develop a multi-objective joint optimisation model that takes into account investment cost, reconfiguration cost, similarity coefficient, and delayed reconfiguration to optimise the part family and configuration of D-RMS simultaneously. Three types of machine tools namely dedicated machine tools, flexible machine tools, and reconfigurable machine tools are considered in the optimisation model. Secondly, the non-dominated sorting genetic algorithm-III (NSGA-III) is adopted to solve the proposed multi-objective integer programming problem. Finally, numerical experiments are presented to demonstrate the effectiveness of the proposed multi-objective joint optimisation method. [ABSTRACT FROM AUTHOR]

In this paper, a variant of the open shop scheduling problem is considered in which the intermediate storage is forbidden among two adjacent production stages (zero buffer or machine blocking constraint). The performance measure is to minimise the maximal completion time of the jobs (makespan). Since this is an NP-hard problem, a two-stage constraint programming approach is proposed as a new exact method. Computational experiments were carried out on 222 literature problem instances in order to test the performance of the proposed algorithm. The relative deviation is adopted as the performance criteria. Computational results point to the ability of the proposed method to solve large-sized instances in comparison with the developed mixed-integer linear programming model and a simple constraint programming model, both with user cuts. In all set of instances, the proposed two-stage method performed better than benchmarking methods and integer programming models, with average relative deviation regarding objective values as lower as 12%. In addition, the results point to a competitive efficiency in computational times of the proposed method with less than 200 s in the most instances to obtain the optimal solution, in comparison to competitive metaheuristics from literature of the problem, for the tested test instances. [ABSTRACT FROM AUTHOR]

This paper proposes a prediction-based product change recovery strategy for the SC (supply chain) under long-term disruptions. A real-world case composed of multi-period planning and dynamic customer demand is considered. First, to forecast dynamic customer demand, a data-based demand predictive method with feedback errors is designed. Second, to schedule procurement and production in advance, based on the predicted demand, the selection of the supply portfolio is transformed into a bi-objective mixed integer programming problem incorporating product change. Furthermore, goods allocation and customer order fulfillment strategy is also designed to finish the transportation of goods and delivery of customer orders. To systematically synthesise and address the problems aforementioned, a three-stage heuristic method is further developed. Finally, a case study is presented to substantiate the reliability of the proposed strategy via an actual SC model of Dongsheng Electronics Co., Ltd. Based on the results obtained after one month, the proposed disruption recovery strategy can reduce the unit product cost and improve the service level, which outperforms the original method adopted by Dongsheng. Additionally, sensitivity analysis of unit product change cost is conducted to reveal the effect of different unit product change costs on SC performance. [ABSTRACT FROM AUTHOR]

Order picking is the process of retrieving ordered products from storage locations in warehouses. In picker-to-parts order picking systems, two or more customer orders may be grouped and assigned to a single picker. Then routing decisions regarding the visiting sequence of items during a picking tour must be made. Won and Olafsson (2005) found that solving the integrated problem of batching and routing enables warehouse managers to organize order picking operations more efficiently compared with solving the two problems separately and sequentially. We therefore investigate the mathematical programming formulation of this integrated problem. We present several improved formulations of the problem based on the findings of Valle, Beasley, and Salles da Cunha (2017), that can significantly improve computational results. More specifically, we reconstruct the connectivity constraints and generate new cutting planes in our branch-and-cut framework. We also discuss some problem properties by studying the structure of a graphical representation of the warehouse, and we present two types of additional constraints. We also consider the no-reversal case of this problem. We present efficient formulations by building different auxiliary graphs. Finally, we present computational results for publicly available test problems for single-block and multiple-block warehouse configurations. [ABSTRACT FROM AUTHOR]

This study addresses a multi-stage flow shop scheduling problem in which a job is reworked when its queue time between two arbitrary stages exceeds an upper limit. The problem is to determine the start times of jobs and rework setups/operations if incurred for the objective of minimising makespan. As an extension of the previous studies, multiple overlapped queue time limits are considered, i.e. some in-between stages of queue time limits for a job are overlapped. A mixed integer programming model is developed and its performance is reported for small-sized test instances. Then, due to the limited applications of optimal solution approaches, a variable neighbourhood search (VNS) algorithm is proposed that generates an initial solution and improves it using a shaking and a local search improvement methods. In addition, it is extended to the general variable neighbourhood search (GVNS) algorithms with variable neighbourhood descent (VND) methods. Computational results show that the GVNS algorithms outperform the VNS algorithm significantly and also give near optimal solutions for small-sized test instances within a reasonable amount of computation times. [ABSTRACT FROM AUTHOR]

We seek to optimize the production planning of a three-echelon remanufacturing system under uncertain input data. We consider a multi-stage stochastic integer programming approach and use scenario trees to represent the uncertain information structure. We introduce a new dynamic programming formulation that relies on a partial nested decomposition of the scenario tree. We then propose a new approximate stochastic dual dynamic integer programming algorithm based on this partial decomposition. Our numerical results show that the proposed solution approach is able to provide near-optimal solutions for large-size instances with a reasonable computational effort. [ABSTRACT FROM AUTHOR]

We study a two-stage hybrid flow shop problem arising from a fine chemicals production facility, where the first stage is a continuous chemical reaction process and the second stage is a discrete filling-packaging process. The objective is to minimise the total weighted completion time through batching of the jobs and scheduling of the batches at first stage and scheduling of the jobs at second stage. We formulate the problem as a mixed integer programming model and develop a Lagrangian relaxation-based framework for solving it, where the original problem is decomposed into family-level subproblems, and each subproblem is transformed into a set-partitioning problem. The subproblems are solved to optimality via branch and price algorithm. We also propose two heuristic algorithms for reducing computational efforts without much loss of solution quality. Finally, we conduct computational experiments with both randomly generated and real data sets to test the performance of the three proposed algorithms and demonstrate that the algorithms perform efficiently. [ABSTRACT FROM AUTHOR]

Summary: Deterministic communication plays a crucial role for real‐time distributed embedded systems by guaranteeing a low end‐to‐end delay and minimal jitter. Conflict‐aware iterated ILP‐based scheduling (IIS) is an incremental approach to enhance the scalability of single‐shot ILP computation to solve the computationally hard Qbv‐compliant offline scheduling problem for IEEE 802.1 Time‐Sensitive Networking (TSN). Taking into account the conflicting demands of the streams, IIS computes no‐wait schedules by dividing the set of streams into disjoint partitions, each of which is incrementally scheduled by an ILP solver. In this work, defining the no‐wait communication constraints for TSN scheduling, we propose a novel iterated scheduling approach, namely, O‐IIS, with a backtracking mechanism and partial solution support extending the conventional IIS procedure. O‐IIS relies on an ordering strategy to determine the order in which the constructed partitions will be processed by an ILP solver. We evaluate the performance of our approach in terms of schedulability success rate and schedule synthesis time using various network topologies and different partitioning schemes to construct the partitions. The evaluation results show that our approach provides significantly better scheduling performance compared to the existing work in the literature. [ABSTRACT FROM AUTHOR]

This paper considers the examination timetabling problem (ETTP) at the College of Industrial Technology (CIT) of the King Mongkut's University of Technology North Bangkok in Thailand. A new integer linear programming (ILP) formulation for the ETTP at the CIT is presented. The objectives were to minimize both the number of examination days (the main objective) and the number of rooms used throughout the entire examination period (the secondary objective). In this paper, a course can have multiple sections, and an examination room can accommodate exams for more than one course section. To illustrate the proposed ILP model, real data on courses acquired from the CIT were used to generate two test problems: a small problem and a large problem. The small problem included 32 courses with 69 sections. The large problem included 73 courses with 341 sections, which was the real data required for generating the midterm examination timetable for all first‐year courses in the first semester of 2021. Both problems were solved using the CPLEX solver software. The results show that the proposed model could find an optimal examination timetable for the small problem with a computational time of 2 min and 46 s. It also could find a good feasible midterm examination timetable that satisfied the requirements of the CIT for the large problem within the 2‐h time limit, much less time than that compared to manual scheduling by the CIT's administrative staff. The obtained midterm examination timetable required five examination days and could reduce 104 examination rooms compared to assigning each course section to a separate examination room. The proposed ILP model can be used in a real‐life situation and can be a good option to generate an optimal schedule or a good feasible schedule for examinations at the CIT or other institutions that have similar requirements. [ABSTRACT FROM AUTHOR]

Background: The construction of a pangenome graph is a fundamental task in pangenomics. A natural theoretical question is how to formalize the computational problem of building an optimal pangenome graph, making explicit the underlying optimization criterion and the set of feasible solutions. Current approaches build a pangenome graph with some heuristics, without assuming some explicit optimization criteria. Thus it is unclear how a specific optimization criterion affects the graph topology and downstream analysis, like read mapping and variant calling. Results: In this paper, by leveraging the notion of maximal block in a Multiple Sequence Alignment (MSA), we reframe the pangenome graph construction problem as an exact cover problem on blocks called Minimum Weighted Block Cover (MWBC). Then we propose an Integer Linear Programming (ILP) formulation for the MWBC problem that allows us to study the most natural objective functions for building a graph. We provide an implementation of the ILP approach for solving the MWBC and we evaluate it on SARS-CoV-2 complete genomes, showing how different objective functions lead to pangenome graphs that have different properties, hinting that the specific downstream task can drive the graph construction phase. Conclusion: We show that a customized construction of a pangenome graph based on selecting objective functions has a direct impact on the resulting graphs. In particular, our formalization of the MWBC problem, based on finding an optimal subset of blocks covering an MSA, paves the way to novel practical approaches to graph representations of an MSA where the user can guide the construction. [ABSTRACT FROM AUTHOR]

Providing effective Through Train Services (TTSs) faces challenges due to complex infrastructure conditions, train performances and passenger demands. To enhance TTSs between two different classes of urban rail transit lines with variations in train speed and capacity, we propose a multi-objective Integer Non-Linear Programming (INLP) model. This model maximizes passenger travel time savings and average train load utilization, and develops an integrated approach to simultaneously optimize the frequencies of through express trains and local trains, as well as the operation zones, stopping patterns and type selection of through trains. Additionally, a Non-Dominated Sorting Genetic Algorithm II is designed to solve the INLP model based on a simple test network and a real-world case from the Nanjing Subway. The unique benefits of our proposed method are demonstrated by a comprehensive compared with the Single Line Operation Mode and the all-stop plans under Through Operation Mode. [ABSTRACT FROM AUTHOR]

For a simple, undirected graph G (V , E) without isolated vertices, a function h : V → { ϕ , { 1 } , { 2 } , { 1 , 2 } } which satisfies the following two conditions is called a total 2-rainbow dominating function (T2RDF) of G. (i) For all u ∈ V , if h (u) = ϕ then ∪ v ∈ N (u) h (v) = { 1 , 2 } and (ii) Every u ∈ V with h (u) ≠ ϕ is adjacent to a vertex v with h (v) ≠ ϕ. The weight of a T2RDF h of G is the value h (V) = ∑ u ∈ V | h (u) |. The total 2-rainbow domination number is the minimum weight of a T2RDF on G and is denoted by γ t r 2 (G). The minimum total 2-rainbow domination problem (MT2RDP) is to find a T2RDF of minimum weight in the input graph. In this article, we show that the problem of deciding if G has a T2RDF of weight at most l for star convex bipartite graphs, comb convex bipartite graphs, split graphs and planar graphs is NP-complete. On the positive side, we show that MT2RDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, we show that MT2RDP cannot be approximated within (1 −) ln | V | for any > 0 unless P=NP and also propose 2 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for it. Further, we show that MT2RDP is APX-complete for graphs with maximum degree 4. Next, it is shown that domination problem and the total 2-rainbow domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MT2RDP is presented. [ABSTRACT FROM AUTHOR]

Through the integration of Network Function Virtualization (NFV), Software-Defined Networks, cloud service providers can realize cost reduction, performance enhancement, and support for advanced application scenarios. Within this framework, Service Function Chain (SFC) has emerged as a pivotal approach for delivering network services, offering flexibility and cost-effectiveness in provisioning Virtual Network Functions (VNFs) dynamically and elastically across a network of physical devices. This paper concentrates on optimizing VNF placement within NFV-enabled networks to elevate the number of SFC Requests (SFCRs) successfully processed. Emphasizing the often-overlooked factors of time-varying workloads and VNF sharing via multi-tenancy technology, we present a novel Integer Linear Programming (ILP) formulation for the strategic placement of VNFs. To effectively solve this ILP, we introduce a Throughput Optimization Heuristic Solution (TOHS), comprising an algorithm based on correlation for assigning SFCRs to nodes, alongside a VNFR aggregation algorithm aimed at optimizing node resource utilization by consolidating VNFRs requiring identical VNF types. Through detailed numerical simulations and comparative analysis with existing literature, we demonstrate that TOHS approaches the performance of ILP solvers for small-scale problems, outperforming other solutions in diverse scenarios. Specifically, TOHS achieves higher network throughput and more efficient utilization of network resources, underscoring its efficacy in practical NFV-enabled network deployments. [ABSTRACT FROM AUTHOR]

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterization imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the ℓ 1 -norm of the Graver basis is bounded by a function of the maximum ℓ 1 -norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the ℓ 1 -norm of the Graver basis of the constraint matrix, when parameterized by the ℓ 1 -norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix. [ABSTRACT FROM AUTHOR]

In this paper, a special case of the generalized 4-block n-fold IPs is investigated, where B i = B and B has a rank at most 1. Such IPs, called almost combinatorial 4-block n-fold IPs, include the generalized n-fold IPs as a subcase. We are interested in fixed parameter tractable (FPT) algorithms by taking as parameters the dimensions of the blocks and the largest coefficient. For almost combinatorial 4-block n-fold IPs, we first show that there exists some λ ≤ g (γ) such that for any nonzero kernel element g , λ g can always be decomposed into kernel elements in the same orthant whose ℓ ∞ -norm is bounded by g (γ) (while g itself might not admit such a decomposition), where g is a computable function and γ is an upper bound on the dimensions of the blocks and the largest coefficient. Based on this, we are able to bound the ℓ ∞ -norm of Graver basis elements by O (g (γ) n) and develop an O (g (γ) n 3 + o (1) L ^ 2) -time algorithm (here L ^ denotes the logarithm of the largest absolute value occurring in the input). Additionally, we show that the ℓ ∞ -norm of Graver basis elements is Ω (n) . As applications, almost combinatorial 4-block n-fold IPs can be used to model generalizations of classical problems, including scheduling with rejection, bi-criteria scheduling, and a generalized delivery problem. Therefore, our FPT algorithm establishes a general framework to settle these problems. [ABSTRACT FROM AUTHOR]

First-Person Shooter (FPS) games are among the most popular latency-sensitive multiplayer online games. A separate game server manages each multiplayer group hosted appropriately to meet the given Quality of Service (QoS) and Quality of Experience (QoE) requirements of the game and the players. Cloud computing is typically used to host these game servers to cope with changing workload requirements, given its elasticity, scalability, and on-demand provisioning characteristics [1]. However, the Cloud still suffers from known latency limitations, especially when dealing with latency-sensitive applications such as FPS games. Hence, Fog computing can be a good alternative for hosting FPS game servers, given that Fog nodes hosting the servers can be placed close to the players, thereby reducing latency. However, a careful resource management is necessary given the Fog's capacity unpredictability. This paper introduces an optimization-based game server placement approach that minimizes server costs while optimizing latency delays and, eventually, QoE for the players. A static model for the server placement problem is formulated as an Integer Linear Program (ILP) with valid inequalities. Given the complexity of the problem, a resolution strategy based on a non-linear, double penalty relaxation technique in conjunction with a proven Genetic Algorithm (GA) is developed. A dynamic version of the placement problem is also formulated to cope with the realistic scenarios dealing with changing multiplayer groups and Fog servers. A two-step dynamic scheme, based on the developed GA, is applied. Extensive simulations are conducted showing a good performance of the proposed approach both in terms of solution quality and execution time. [ABSTRACT FROM AUTHOR]

This paper deals with linear integer optimization. We develop a technique that can be applied to provide improved upper bounds for two important questions in linear integer optimization. Given an optimal vertex solution for the linear relaxation, how far away is the nearest optimal integer solution (if one exists; proximity bounds)? If a polyhedron contains no integer point, what is the smallest number of integer parallel hyperplanes defined by an integral, nonzero, normal vector that intersect the polyhedron (flatness bounds)? This paper presents a link between these two questions by refining a proof technique that has been recently introduced by the authors. A key technical lemma underlying our technique concerns the areas of certain convex polygons in the plane; if a polygon K⊆R2 satisfies τK⊆K° , where τ denotes 90° counterclockwise rotation and K° denotes the polar of K, then the area of K° is at least three. Funding: J. Paat was supported by the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2021-02475]. R. Weismantel was supported by the Einstein Stiftung Berlin. [ABSTRACT FROM AUTHOR]

At present, the mainstream studies on route selection optimization at the railway station rarely considered the overall punctuality of the operation plans and the seizing route resource between shunting operation and train running, which can endanger the running safety and reduce the efficiency at the station. Therefore, this paper proposes an optimization method for the route selection under the integration of dispatching and control at the railway station. Firstly, the station‐type data structure, the route occupation conflict, and the operation task order were defined. Then, a 0‐1 programming model was constructed to minimize the total delay time and shorten the total travel time of all operations. Finally, a two‐stage solution algorithm based on depth‐first search algorithm and genetic algorithm was designed, and two actual cases of a technical station in China were designed. The instance verification results show that the algorithm can find the satisfactory route scheme in 250 iterations; different delay factors and travel coefficients will get different route schemes, which can provide decision support for dispatchers and operators to select routes. Through comparative analysis of algorithms, it is found that the two‐stage algorithm has higher solving efficiency than the individual depth‐first search algorithm and individual genetic algorithm. [ABSTRACT FROM AUTHOR]

This work considers a combinatorial optimization problem in graphs, the nilcatenation problem, and investigates its potential application for detecting money laundering activities in cryptocurrency networks. The nilcatenation problem consists of finding a set of arcs that can be removed from an arc‐weighted directed graph without changing the balance of any vertex. The balance of a vertex is defined as the difference between the sum of the weights of outgoing and incoming arcs. We propose a 0/1 integer linear programming formulation and a local branching algorithm. The approaches are computationally evaluated and compared using three sets of test instances, two of them generated from Bitcoin's testnet and mainnet networks. An experiment on the testnet showed that it is possible to retrieve a nilcatenation artificially introduced with fake bitcoin transactions. Experiments on the mainnet showed that it is possible to find large nilcatenations, possibly indicating money laundering activities. [ABSTRACT FROM AUTHOR]

Conference organisers often face the challenge of scheduling a scientific program. This problem usually involves many talks that must be scheduled in parallel, subject to time and space limitations. This paper adopts an Attendee-Based-Perspective to the conference scheduling problem, in which we collect (anonymised) data on attendees' preferences and use these as a main driver to schedule the talks. We test three optimization approaches for this problem, based on integer programming formulations. The main approach divides the problem into two stages: the first stage schedules predefined thematic sessions and the second stage schedules talks within these sessions. We report results using real data instances of three conferences. The results show that our main approach can produce solutions swiftly, accommodating the requirements of the organisers while allowing attendees to attend most of their preferred talks. Our work has been used in practice to generate the actual schedule of these three conferences. [ABSTRACT FROM AUTHOR]

Cryo-EM particle identification from micrographs ("picking") is challenging due to the low signal-to-noise ratio and lack of ground truth for particle locations. State-of-the-art computational algorithms ("pickers") identify different particle sets, complicating the selection of the best-suited picker for a protein of interest. Here, we present REliable PIcking by Consensus (REPIC), a computational approach to identifying particles common to the output of multiple pickers. We frame consensus particle picking as a graph problem, which REPIC solves using integer linear programming. REPIC picks high-quality particles even when the best picker is not known a priori or a protein is difficult-to-pick (e.g., NOMPC ion channel). Reconstructions using consensus particles without particle filtering achieve resolutions comparable to those from particles picked by experts. Our results show that REPIC requires minimal (often no) manual intervention, and considerably reduces the burden on cryo-EM users for picker selection and particle picking. Availability: https://github.com/ccameron/REPIC. Cryo-EM particle picking is difficult due to noise and no ground truth. Here, a computational method for finding consensus particles from different picking algorithms is presented. This method identifies high-quality particles with minimal user input. [ABSTRACT FROM AUTHOR]

We deal here with a general 2-commodity flow model over a time expanded network designed for the management of a shared mobility systems. The model involves an integral flow vector that represents carriers together with an integral flow vector that represents the items transported by those carriers. It simultaneously copes with temporal and resource issues, and is difficult to handle in the practice. So we propose here a Project and Lift approach to handle it. We start by projecting the time expanded network model on the original transit network to obtain a simpler two-commodity flow projected model. In order to make this projected model consistent with the original problem, we introduce some complex constraints, prove that these constraints can be separated in polynomial time and discuss the experimental behavior of the related Branch-and-Cut algorithm. Next, we introduce the Lift issue about the way one may turn an optimal solution of our projected model into a solution of the original problem. Finally, we thoroughly study a somewhat restrictive Strong Lift setting of this Lift issue, design and test an exact mixed integer programming Strong Lift model, and discuss some flexible alternative approaches. [ABSTRACT FROM AUTHOR]

With the connection and integration of renewable energy, the on-load tap-changer (OLTC) has become an important device for regulating voltage in distribution networks. However, due to non-smooth and non-linear characteristics of OLTC, traditional bad data identification and state estimation methods for transmission network are limited when applied to the distribution network. Therefore, the nonlinearity and droop control constraints of the OLTC model are considered in this paper. At the same time, the quadratic penalty function is introduced to realize the fast normalization of the tap position. It proposes a two-stage bad data identification method based on mixed-integer linear programming. In the first stage, suspicious measurements are identified using projection statistics and maximum normalized residual methods for preprocessing the measurement data. In the second stage, a linearization approach utilizing hyhrid data-physical driven is applied to handle nonlinear constraints, leading to the development of a bad data identification model based on mixed-integer linear programming. Finally, the proposed methodology is validated using a modified IEEE-33 node test feeder example, demonstrating the accuracy and efficiency of bad data identification. [ABSTRACT FROM AUTHOR]

In typical business situations, sellers usually offer discount schemes to buyers to increase overall profitability. This study aims to design a supply chain network under uncertainty of demand by integrating an all-unit quantity discount policy. The objective is to maximize the profit of the entire supply chain. The proposed model is formulated as a mixed integer nonlinear programming model, which is subsequently linearized into a mixed integer linear programming model and hence able to obtain a global solution. Numerical examples in the manufacturing supply chain where customer demand follows normal distributions are used to assess the effect of quantity discount policies. Key findings demonstrate that the integration of quantity discount policies significantly reduces total supply chain costs and improves inventory management under demand uncertainty, and decision makers need to decide a balance level between service levels and profits. [ABSTRACT FROM AUTHOR]

In recent years, parcel volumes have reached record highs, prompting the logistics industry to explore innovative solutions to meet growing demand. In densely populated areas, delivery robots offer a promising alternative to traditional truck-based delivery systems. These autonomous electric robots operate on sidewalks and deliver time-sensitive goods, such as express parcels, medicine and meals. However, their limited cargo capacity and battery life require a return to a depot after each delivery. This challenge can be modeled as an electric vehicle-routing problem with soft time windows and single-unit capacity constraints. The objective is to serve all customers while minimizing the quadratic sum of delivery delays and ensuring each vehicle operates within its battery limitations. To address this problem, we propose a mixed-integer quadratic programming model and introduce an enhanced formulation using a layered graph structure. For this layered graph, we present two solution approaches based on relaxations that reduce the number of nodes and arcs compared to the expanded formulation. The first approach, Iterative Refinement, solves the current relaxation to optimality and refines the graph when the solution is infeasible for the expanded formulation. This process continues until a proven optimal solution is obtained. The second approach, Branch and Refine, integrates graph refinement into a branch-and-bound framework, eliminating the need for restarts. Computational experiments on modified Solomon instances demonstrate the effectiveness of our solution approaches, with Branch and Refine consistently outperforming Iterative Refinement across all tested parameter configurations. [ABSTRACT FROM AUTHOR]

This paper addresses a real-world Integrated Operating Room Planning and Scheduling (IORPS) problem encountered by a local hospital in Naples, characterized by stringent emergency management constraints, requiring treatment initiation within a 20-minute time-window. We tackle this problem by an original Integer Linear Programming formulation, capable of dealing with different operating room management strategies (open, block and block-modified). Our work differs from conventional cost-focused models by adopting a patient-oriented objective function, aligning with public hospitals obligations. The proposed method has been validated using real-world data provided by the hospital. The performed experimentation demonstrates the efficiency of the approach, capable of determining the optimal solution within an acceptable computation time that aligns with hospital requirements. Moreover, it also highlights the relevance of using our optimization approach to reduce delays in emergency responsiveness. This confirms its practical usage as a substitute for the current manual procedure. [ABSTRACT FROM AUTHOR]

In this paper, we present an integer programming formulation for the windy profitable location rural postman problem (WPLRPP). We state and prove a theorem concerning the dimension of the associated polyhedron. Then, we use this theorem to study some trivial facets of the presented polyhedron. Furthermore, we adapt and validate several large families of valid inequalities for the WPLRPP. We also develop an efficient branch-and-cut algorithm for solving large WPLRPP instances, which leverages those inequalities. We compare our presented branch-and-cut algorithm with other efficient algorithms in the literature. The numerical results show that our algorithm solves larger problem instances and requires considerably less computing time than other algorithms in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we consider a project-based organization that deals with an assignment problem in which a set of projects must be assigned to a group of project managers. This assignment is done based on the relative contributions of projects to the organizational mission and a matching score between each pair of a project and a project manager. We assume that some projects are deterministic, and the organization has signed their corresponding contracts while others are stochastic, i.e. the organization has submitted bids for these projects and may or may not win them in the future. Furthermore, we consider a finite planning horizon and presume a predetermined start time for each deterministic and stochastic project. We develop two models including a multi-stage stochastic integer programming model and a stochastic dynamic programming model to solve the problem. The latter shows better performance for small-size and less complex instances whereas the former gives better performance for more complex instances. We also developed a heuristic algorithm to solve large-size and more complex instances. Computational results indicate that the developed heuristic algorithm can reach near-optimal solutions in reasonable CPU run times and dominates the two other solution approaches particularly for large-size instances. [ABSTRACT FROM AUTHOR]

Copyright of Machine Tool & Hydraulics is the property of Guangzhou Mechanical Engineering Research Institute (GMERI) 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.)

Faced with the land use heterogeneity and trip distribution non-equilibrium along the corridor connecting urban district and rural area, the operation characteristics of the all-stop bus, the express bus and the shuttle bus running on the transportation corridor should be given full consideration, as well as the tradeoff between passenger trip cost and bus operation cost during the peak-hour period. In order to realize the reliable decision of bus resources configuration for urban-rural public transportation, a bi-objective programming model of multi-modal urban-rural bus operation scheme is established, where the decision variables include the departure frequency of different bus modals, the terminals of shuttle buses, and the stop scheme of express buses, under the constraints of departure interval, passenger volume, vehicle occupancy, section capacity usage and modal competition. To validate the feasibility of proposed optimization model, an urban-rural bus corridor from Rural Jasmine Ecological Park in Hanjiang District to West Xiangyang Bridge in Songqiao Town was chosen as a study case, and the operation organization scheme of three bus modals were solved by the mathematical solver Lingo using mixed integer programming. Meanwhile, the scheme differences under different subobjective weights were discussed, taking into account the uncertain passenger demand and operation supply. The result shows that the increase of passenger trip cost weight will increase the departure frequency of all three bus modals, while the increase of operation cost weight will decrease the total operating vehicles, but the stop frequency at middle stations for express buses will increase accordingly. Compared to the current operation scheme, the optimized scheme can greatly enhance the section capacity usage at a slight sacrifice of passenger trip time with fewer bus vehicles. [ABSTRACT FROM AUTHOR]

This study explores enhancing carsharing services by integrating gasoline and electric vehicles into a one-way mixed fleet carsharing system (OMFCS). The focus is on optimizing configurations (fleet and staff size, initial deployment) and operational strategies (vehicle relocation and staff rebalancing) while considering carbon emission costs. Employing a space-time-electricity network modeling approach, we developed an integer linear programming model to tackle the configurations and operational strategies optimization problem. For solving this model, we introduce a Lagrangian relaxation-branch bound approach, which integrates subgradient, dynamic programming and greedy-based heuristics algorithm. An illustrative case and a real-world case are conducted to demonstrate the efficiency of the proposed solution method and the analysis sheds light on the configurations and operational strategies of OMFCS. The sensitive analysis results suggest that OMFCS is more profitable and balances user service quality and carbon emissions better than carsharing systems using only one type of vehicle. [ABSTRACT FROM AUTHOR]

In this paper, we consider a discrete tomography problem, which aims at characterizing given projections of a binary matrix assuming nonrepeatability property of the matrix rows. We discuss Integer Linear Programming representation, and the ways of generating learning instances of this problem, to solve it using the machine learning methods. [ABSTRACT FROM AUTHOR]

Underwater acoustic sensors are vital for monitoring marine environments and detecting targets, but their optimal placement presents challenges, particularly in deep-sea environments. This paper addresses the question of determining the optimal sensor placement in a specific ocean region through a principled optimization approach. While previous studies mainly utilized heuristic algorithms without exploiting problem-specific structures, this work explores leveraging the complex three-dimensional acoustic environment through principled modeling and tailored optimization. Specifically, intricate three-dimensional multi-directional acoustic maps are constructed for each sensor. Based on these maps, the sensor placement problem is then cast as an integer linear programming, allowing the study to leverage established theoretical results from operations research. Additionally, an alternative algorithm with its performance indicator is presented to find near-optimal solutions efficiently and can empirically reach over 99% coverage of the optimal solution. Experimental results using real-life data from the South China Sea demonstrate the effectiveness of the proposed approach in achieving much larger detection coverage compared to random and empirical strategies. Notably, the alternative fast algorithm approaches the optimal solution in significantly less time. Furthermore, experiments show that any further simplification of this approach leads to the performance degradation. [ABSTRACT FROM AUTHOR]