Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2007.10.019 Byline: Kazuki Matsumoto (a), Hiroyoshi Miwa (b), Toshihide Ibaraki (b) Keywords: Scheduling; Corrugated paper; Complexity; Contiguous set; Integer programming Abstract: Corrugated paper is produced by gluing three types of papers of the same breadth. Given a set of orders, we first assign each order to one of the standard breadths, and then sequence those assigned to each standard breadth so that they are continuously manufactured from the three rolls of the specified standard breadth equipped in the machine called corrugator. Here we are asked to achieve multi-goals of minimizing total length of roll papers, total loss of papers caused by the differences between standard breadths and real breadths of the orders, and the number of machine stops needed during production. We use integer programming to assign orders to standard breadths, and then develop a special purpose algorithm to sequence the orders assigned to each standard breadth. This is a first attempt to handle scheduling problems of the corrugator machine. Author Affiliation: (a) Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Sakyo-ku, Kyoto 606-8501, Japan (b) Department of Informatics, School of Science and Technology, Kwansei Gakuin University, 2-1 Gakuen Sanda, Hyogo 669-1337, Japan Article History: Received 24 March 2007; Accepted 5 October 2007

Keywords Scheduling; Staff rostering; Task assignment; Integration; Clique Highlights * Shift-based model outperforms the task- and roster-based models to solve the integrated staff rostering and task assignment (ISRTA) problem. * Shift-based ISRTA model is extended to six operational considerations, i.e., shift flexibility, qualification, travel time, contractual rules, task connection preference, and fairness, which ensure the applicability of the result schedule. * A clique-based aggregated reformulation is proposed to enhance the performance of the shift-based ISRTA model. Two heuristics, i.e., rolling horizon algorithm and iterative shift selection algorithm, are also proposed to speed up the solution process. Abstract Due to the computational complexity, the staff scheduling problem is generally decomposed into two subproblems, i.e. staff rostering and task assignment problems. Very often, this could result in suboptimal solutions. Thus, we study an integrated staff rostering and task assignment (ISRTA) problem in this paper. Previous studies formulate this problem as task- and roster-based ISRTA models, which can only solve small-scale problems. To overcome this limitation, this paper proposes a novel shift-based ISRTA model, which exhibits less symmetry and greatly reduces the number of variables and constraints. We extend the shift-based ISRTA model to six real-world requirements, i.e., shift flexibility, qualification, travel time, contractual rules, task connection preference, and fairness, which ensure the applicability of the result schedule. To efficiently solve the shift-based ISRTA model, we propose a clique-based aggregated model that enhances the performance of the basic shift model. Further, two heuristics, i.e., rolling horizon algorithm and iterative shift selection algorithm, are proposed to speed up the solution process. Based on randomly generated 24 benchmark instances and 16 real-world instances from a major airline, computational results show that the shift-based ISRTA model outperforms the task- and roster-based ISRTA models. For small- and mid-scale problems, the shift-based ISRTA model can be solved optimally or near-optimally directly using a commercial solver, and the rolling horizon algorithm and iterative shift selection algorithm can solve large-scale problems and obtain high-quality solutions. Author Affiliation: (a) School of Economics and Management, Tongji University, Shanghai 200092, China (b) China Eastern Aircateting Co. Ltd., Shanghai 201202, China (c) SILC Business School, Shanghai University, Shanghai, China * Corresponding author. Article History: Received 22 November 2021; Accepted 27 February 2023 Byline: Wenshu Wang [2010083@tongji.edu.cn] (a), Kexin Xie [2110079@tongji.edu.cn] (a), Siqi Guo [2110078@tongji.edu.cn] (a), Weixing Li [lwx@ceair.com] (b), Fan Xiao [xiaofan@tongji.edu.cn] (c,*), Zhe Liang [liangzhe@tongji.edu.cn] (a)

Keywords Scheduling; Parallel batch machines; Non-identical capacities; Total completion time; Ant colony optimization Highlights * A parallel batch scheduling problem with non-identical capacities is considered. * The objective of scheduling is to minimize the total completion time. * A modified elite ant system algorithm with the local search is proposed. Abstract This paper considers the problem of scheduling a group of jobs with arbitrary release times, non-identical sizes, and different processing times on non-identical parallel batch processing machines to minimize the total completion time. A mixed-integer programming (MIP) model is firstly constructed in this paper to solve this problem. Then since the studied problem is strongly NP-hard, a modified elite ant system algorithm with the local search (MEASL) is also proposed to solve it, which is compared with several meta-heuristic algorithms and the commercial optimization solver (Gurobi) through extensive simulation experiments. Finally, the experimental results verify the effectiveness of the proposed algorithm. Author Affiliation: (a) School of Management, Hefei University of Technology, Hefei 230009, PR China (b) Key Laboratory of Process Optimization and Intelligent Decision-Making, Ministry of Education, Hefei 230009, PR China (c) School of Computer Science and Technology, Anhui University, Hefei 230039, PR China (d) School of Economics & Management, Fuzhou University, Fuzhou 350116, PR China (e) Université Gustave-Eiffel, ESIEE Paris, COSYS-GRETTIA, Marne-la-Vallée F-77454, France * Corresponding author at: School of Management, Hefei University of Technology, Hefei 230009, PR China. Article History: Received 29 May 2022; Accepted 13 February 2023 Byline: Han Zhang [hanzhang3411@outlook.com] (a), Kai Li [hfutlk@139.com] (*,a,b), Zhao-hong Jia [zhjia@mail.ustc.edu.cn] (c), Chengbin Chu [chengbin.chu@univ-eiffel.fr] (d,e)

Keywords Transportation; Routing; Set orienteering; Matheuristic Highlights * The paper proposes an adaptive memory matheuristic for the set orienteering problem. * Local search is equipped with mathematical programming components. * Solution reconstruction mechanisms exploit high-quality node sequences stored in an adaptive memory structure. * The algorithm outperforms the results of the state-of-the-art methodologies. * New very large-scale test problems are introduced and solved for the first time. Abstract This paper proposes a novel matheuristic algorithm for the Set Orienteering Problem (SOP). The set orienteering problem generalizes the Orienteering Problem (OP) by considering customers to be divided into mutually exclusive clusters. The profit associated with each cluster is collected by visiting at least one of the customers belonging to this cluster. The problem calls for the determination of the closed route that maximizes the collected profit without violating a given maximum route duration. We propose a matheuristic algorithm based on local search. The proposed algorithm is equipped with mathematical programming components for dealing with various subproblems, as well as an adaptive memory structure for producing high-quality starting solutions. Promising and diverse solutions are collected and multiple solution reconstruction mechanisms are presented. Extensive computational experiments are conducted for parameter tuning, and for evaluating the contribution of the mathematical programming components and the adaptive memory mechanism. The proposed solution approach is compared against previously published SOP algorithms. It produces the best solutions for 98.20% of the instances of the classic SOP benchmark data set. For 102 of the total 612 instances a new best solution is obtained. In addition, a new large data set of 304 instances is introduced with instances of up to 3162 customers and 634 clusters to evaluate the scalability of the proposed algorithm, and the effectiveness of the various adaptive memory schemes. The proposed algorithm manages to outperform or match the best-known solution for 281 out of 304 instances when compared with a state-of-the-art open source SOP algorithm. Author Affiliation: Department of Management Science and Technology, School of Business, Athens University of Economics and Business, Athens, Greece * Corresponding author. Article History: Received 12 March 2022; Accepted 7 February 2023 Byline: Michael Dontas [mdontas@aueb.gr], Georgios Sideris [geosideris@aueb.gr], Eleftherios G. Manousakis [lmanousakis@aueb.gr] (*), Emmanouil E. Zachariadis [ezach@aueb.gr]

Keywords Logistics; Container stacking; Dynamic programming; Self-attention-based neural network; Rollout algorithm Highlights * A new bay representation is proposed, leading to the new dynamic programming model. * Two neural network algorithms are learnt from optimal solutions to tackle large-scale instances. * A data-driven rollout algorithm is proposed. * The proposed models and algorithms are validated through benchmark data. Abstract In this paper, we investigate the stacking problem of outbound containers. It focuses on developing an optimal stacking strategy to allocate the arriving containers in a preassigned yard bay, with the aim of reducing extra rehandles during later retrieval. Some studies employ dynamic programming models to tackle the problem, which can offer exact solutions. Following this line of research, we propose an alternative dynamic programming model by redefining the bay representation and adjusting the formulations accordingly. The results show that the new model strikes a good balance between stacking quality and computational time. Considering that the dynamic programming model encounters difficulty in solving large-scale instances, we design two neural network algorithms that adopt a self-attention mechanism to enhance the fitting ability of the network. The neural network algorithms learn the decision patterns from the optimal results for small-scale instances obtained by dynamic programming and then are applied to solve large-scale instances. In addition, we propose a data-driven rollout algorithm by integrating the branching strategy and the aforementioned neural network algorithms to prevent the myopic drawback of using solely the neural network. To the best of our knowledge, this is the first paper that integrates the optimization method and machine learning techniques to tackle the container stacking problem. Finally, extensive computational experiments are performed to verify the effectiveness of the proposed models and algorithms. Author Affiliation: Research Center for Modern Logistics, Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, China * Corresponding author. Article History: Received 25 August 2021; Accepted 2 December 2022 Byline: Canrong Zhang [crzhang@sz.tsinghua.edu.cn] (*), Qi Wang, Guoping Yuan

Keywords Unmanned aerial vehicles (UAV); Flying ad hoc network (FANET); Topology construction; Topology adjustment; Relay transmission Abstract A flying ad hoc network (FANET) is formed by multiple unmanned aerial vehicles (UAVs) in an ad hoc manner in which UAVs can cooperate more effectively to complete complex tasks. In this paper, we mainly investigate the topology construction and topology adjustment for FANETs in which relay UAVs are used for relay transmission between mission UAVs and a ground control station (GCS), so that each mission UAV can communicate with the GCS through a multi-hop communication connection. Firstly, we propose an alternating optimization algorithm to optimize the routing paths and the positions of relay UAVs alternately, so as to construct a feasible FANET topology using the minimal number of relay UAVs. Then, we propose a greedy algorithm to deploy new relay UAVs to the FANET topology constructed by the alternating optimization algorithm, so as to construct a high-performance FANET topology using the given number of relay UAVs. Both the alternating optimization algorithm and the greedy algorithm need to be executed in a centralized manner, so these two algorithms can only be used for FANET topology construction. Furthermore, we propose a distributed algorithm to adjust the existing FANET topology when the positions of mission UAVs change, so as to improve the FANET network performance. This distributed algorithm can be executed in a distributed manner, so this algorithm can be used for FANET topology adjustment. The simulation results show that the algorithms proposed in this paper are superior to other baselines. Author Affiliation: Command & Control Engineering College, Army Engineering University, Nanjing 210007, China * Corresponding author. Article History: Received 19 August 2022; Revised 23 March 2023; Accepted 31 March 2023 Byline: Yaqun Liu, Jun Xie [xiejun@aeu.edu.cn] (*), Changyou Xing, Shengxu Xie

Keywords Virtual computer networks; Automatic network security; Security function selection Abstract The incessant growth of network virtualization determined the proliferation of Virtual Network Functions (VNFs), software programs that can run on general-purpose servers and that can also integrate security controls for protection from cyber-attacks. However, a high availability of VNFs may be counterproductive for the network administrators who have to select the most suitable ones to establish the security configuration of their network. On the one hand, the vendor-dependent technicalities of each VNF may cloud the security controls it can actually perform. On the other hand, VNF selection traditionally occurs before the synthesis of the virtual network graph, so it does not employ any network information and it may outcome unoptimized results. In light of these shortcomings, this paper proposes a novel security configuration workflow, based on new abstractions that we call projections. They represent the security-related operations that VNFs should perform to enforce a security policy. Thanks to these abstractions, the actual selection of the VNFs can be postponed to the moment their deployment in the physical network is actually required. In fact, projections are enough for the synthesis of the virtual security graph. This paper also proposes a two-step algorithm for computing projection chains as candidate solutions for graph synthesis. The proposed approach has been implemented as a Java framework and a set of tests have validated its applicability to real-world VNFs, correctness, scalability and optimization. These tests showed that the new security configuration workflow can achieve a significant reduction for the number of selected VNFs and their deployment cost. Specifically, in the analyzed scenario, the improvement percentages for these two parameters are 79% and 90% with respect to the worst-case strategy, while 68% and 77% with respect to a traditional more optimized configuration strategy. Author Affiliation: Dipartimento di Automatica e Informatica, Politecnico di Torino, Torino, Italy * Corresponding author. Article History: Received 17 January 2023; Revised 17 March 2023; Accepted 25 March 2023 Byline: Daniele Bringhenti [daniele.bringhenti@polito.it] (*), Riccardo Sisto [riccardo.sisto@polito.it], Fulvio Valenza [fulvio.valenza@polito.it]

Keywords Stochastic programming; Scenario tree generation; Recursive algorithms; Model error; Distributionally robust solutions HIGHLIGHTS * This is an elaboration of the semiplenary talk I held in Athens at EURO 2021. * The paper summarizes some earlier work, a new aspect is however included by emphasizing the recursive structure of data structures and algorithms. * The role of the ambiguity radius as a tradeoff between model information and efficiency of the optimal decisions is elaborated for several informative examples. Abstract Stochastic multistage decision problems appear in many - if not all - application areas of Operations Research. While to define such problems is easy, to solve them is quite difficult, since they are of infinite dimension. Numerical solution can only be found by solving an approximate, easier problem. In this paper, we show good approximations can be found, where we emphasize the recursive structure of the involved algorithms and data structures. In a second part, the problem of coping with the model error of approximations is discussed. We present algorithms for finding distributionally robust solutions for the model error problem. We also review some application cases of such situations from the literature. Author Affiliation: Faculty of Economics and Statistics, University of Vienna, Wien Oskar-Morgenstern Platz, Vienna A-1090, Austria Article History: Received 6 December 2021; Revised 20 March 2022; Accepted 2 April 2022 (footnote)[white star] This paper is an elaboration of a semiplenary talk held at the EURO21 conference in Athens Byline: Georg Ch. Pflug [georg.pflug@univie.ac.at]

Keywords Reconfigurable intelligent surface; UAV network; Multicast communication; Resource allocation; MP-DQN Abstract This paper investigates an unmanned aerial vehicle (UAV)-enabled multicast network, where the UAV serves as a mobile transmitter to send typical contents to its corresponding ground receivers. A reconfigurable intelligent surface (RIS) is deployed to enhance the service quality with a limited power supply in the UAV-enabled multicast network. It can reconfigure the signal propagation environment and improve the received power of ground receivers by adjusting the reflection coefficients. The sum rate maximization problem is formulated by jointly designing the UAV movement, RIS reflection matrix, and beamforming design from the UAV to users. This paper proposes a Beamforming control and Trajectory design algorithm based on a Multi-Pass Deep Q-Network (BT-MP-DQN). In the proposed algorithm, the UAV acts as an agent for periodically observing the state of the UAV multicast network and takes actions to adapt to the dynamic environment. Specifically, the movement of the UAV is discrete action, and the beamforming design is continuous action. The simulation results show that this proposed algorithm can effectively improve the achievable rate and satisfy the minimum rate of multicast group users. The deployment of the RIS is beneficial to network performance enhancement. In addition, the multicast network with UAV also outperforms the conventional multicast channel with a fixed-location transmitter. Author Affiliation: (a) School of Computer Science and Engineering, Northeastern University, Shenyang, Liaoning, 110819, China (b) Engineering Research Center of Security Technology of Complex Network System, Ministry of Education, China * Corresponding author at: School of Computer Science and Engineering, Northeastern University, Shenyang, Liaoning, 110819, China. Article History: Received 8 October 2022; Revised 22 February 2023; Accepted 9 March 2023 Byline: Pengshuo Ji (a,b), Jie Jia [jiajie@mail.neu.edu.cn] (a,b,*), Jian Chen (a,b), Liang Guo (a), An Du (a), Xingwei Wang (a)

Keywords Social networks; Competitive propagation; Target user; Influence maximization Highlights * To make the dissemination targeted and the revenue maximized, we propose the lowest cost problem to achieve dominant coverage for target users under competitive propagation(LC-CTU problem), using target user profiles and setting the objective to dominate coverage. * To better model this scene, this paper proposes the IC-CRA model, which adds competing, delay and attribute to the basic cascade model. After proving that the objective function is monotonic and submodular, the LCH-TU problem can be solved by a greedy algorithm. * To improve the efficiency of the algorithm, we propose the LCH-TU algorithm. It simplifies the calculation by restricting the influence of nodes in the maximum activation probability path and calculating the local influence recursively using the linear relationship of the path. Abstract Multiple pieces of information disseminated in social networks can create a competitive environment where the influence of each message will be reduced. Thus, how to increase the influence under competitive propagation is significant for many applications such as product marketing and rumor suppression. In this paper, to make the dissemination targeted and maximize revenue, we propose the lowest cost problem to achieve dominant coverage for target users under competitive propagation(LC-CTU problem), using target user profiles and setting the objective to dominate coverage. To better model this scene, this paper proposes a competitive restricted propagation independent cascade model based on weights of attribute-generating edges(IC-CRA model), which adds competition, delay, and attributes to the basic independent cascade model. After proving that the LC-CTU problem under the IC-CRA model is NP-hard and the objective function is monotonic and submodular, the problem can be solved by a greedy algorithm. However, the greedy algorithm is time-consuming for large social networks. Thus, to improve the efficiency of the algorithm, we propose the lowest cost heuristic algorithm based on target users and restricted competition (LCH-TU algorithm), which uses the local influence update of each node for selecting the seed node. Finally, this paper demonstrates the effectiveness, efficiency, and scalability of the LCH-TU algorithm through extensive experiments on seven datasets, including real and artificial networks. Author Affiliation: Institute of Cyber Science and Technology, Shanghai Jiao Tong University, Shanghai 200240, China Shanghai Key Laboratory of Integrated Administration Technologies for Information Security, Shanghai, China * Correspondence to: School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China. Article History: Received 31 December 2022; Revised 5 March 2023; Accepted 8 March 2023 (footnote)[white star] This work is supported by the National Natural Science Foundation of China under Grant 62172278. Byline: Jiaxing Zheng, Li Pan [panli@sjtu.edu.cn] (*)

Keywords OR in environment and climate change; Multistage distributionally robust optimization; Phi-divergences; Water resources; Nested benders decomposition Highlights * Multistage distributionally robust optimization (MDRO) with [phi]-divergences is studied. * A nested Benders decomposition algorithm is proposed and its properties are examined. * The approach is applied to allocate water under climate uncertainties in Tucson, AZ. * Water allocation and infrastructure planning via MDRO helps reduce extreme shortages. Abstract This paper investigates a Multistage Distributionally Robust Optimization (MDRO) approach to water allocation under climate uncertainty. The MDRO is formed by creating sets of conditional distributions (called conditional ambiguity sets) on a finite scenario tree. The distributions in the conditional ambiguity sets remain close to a nominal conditional distribution according a [phi]-divergence (e.g., Kullback-Leibler divergence, Hellinger distance, Burg entropy, etc.). The paper discusses a decomposition algorithm to solve the resulting MDRO with [phi]-divergences, which uses the dual formulation and solves only linear subproblems instead of convex ones. Some properties of the algorithm such as generating feasible policies and valid upper/lower bounds are established. The paper then applies the modeling and solution techniques to allocate water in a rapidly-developing area of Tucson, Arizona. Tucson, like many arid and semi-arid regions around the world, faces considerable uncertainty in its ability to provide water for its citizens in the future. The primary sources of uncertainty in the Tucson region include (1) unpredictable population growth, (2) the availability of water from the Colorado River, and (3) the effects of climate variability on water consumption. This paper integrates forecasts for all these sources of uncertainty into a single optimization model for robust and sustainable water allocation. Then, it uses this model to analyze the value of constructing additional treatment facilities to reduce future water shortages. The results indicate that the MDRO approach can be very valuable for water managers by providing insights to minimize their risks and help them plan for the future. Author Affiliation: (a) Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley CA 94720, USA (b) Department of Integrated Systems Engineering, The Ohio State University, Columbus OH 43210, USA * Corresponding author. Article History: Received 21 November 2019; Accepted 24 June 2022 Byline: Jangho Park [janghopark.1814@gmail.com] (a), Güzin Bayraksan [bayraksan.1@osu.edu] (*,b)

Keywords LEO routing; LEO SLA; Demand Island Abstract Low Earth Orbit (LEO) constellations create a network that includes the satellites (as routing nodes) connected by Inter-Satellite Links (ISLs) and the terminals dynamically connected to one or more satellites. The combination of transient high rate changes in the network topology due to terminals handover, and the end-to-end high propagation time between the routing nodes presents a unique challenge for designing a guaranteed-bandwidth routing protocol that can support the frequent changes. In addition, terminals connected to multiple satellites can balance their traffic between multiple paths in a frame granularity based on the links conditions, and require real-time multipath guaranteed-bandwidth. Prior work focuses on end-to-end routing between multiple gateways and terminals and does not provide a multipath guaranteed-bandwidth service. This paper addresses the problem of sending traffic from a source terminal to a destination terminal connected through multiple satellites, while guaranteeing and enabling planning of the multipath service metrics (bandwidth and latency) and handling satellite handovers. A novel paradigm called Demand Islands is presented. This paradigm takes advantage of the geographical properties of the demand. The service area is split into geographical rectangles (Demand Islands), with a gateway (GW) located at the center of each island. Each Demand Island is dynamically associated with a set of satellites that cover it. We model the set of satellites as a grid. The routing algorithm uses the grid properties to provide real-time multipath guaranteed-bandwidth routing for the demand allocated to each terminal. Each satellite executes the algorithm to calculate the next hop for a received message in the time complexity of O(1). The analysis and simulation demonstrate the unique offering of the algorithm to route real-time guaranteed-bandwidth to terminals connected to multiple satellites. Author Affiliation: School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel * Corresponding author. Article History: Received 21 April 2022; Revised 9 February 2023; Accepted 20 February 2023 (footnote)[white star] Preliminary version of this paper was published in IEEE ICC 2021. Byline: Oren Markovitz [orenmar@post.bgu.ac.il], Michael Segal [segal@bgu.ac.il] (*)

Keywords Edge computing; DDoS attacks; Collaborative prediction; Distributed SDN; LSTM Abstract Edge computing (EC) has greatly facilitated the deployment of networked services with fast responses and low bandwidth, by deploying computing and storage at the network edge which is closer to the data sources. However, it is challenging to have the EC servers gain security protections like those in centralized data centers, making them more vulnerable to security attacks, especially distributed denial-of-service (DDoS) attacks. Existing detection approaches relying on the feedback from EC servers under the attacks can incur high bandwidth costs and service performance degradation. In this paper, we propose a new framework CoWatch for collaborative prediction and detection of DDoS Attacks in EC scenarios. Based on the distributed software-defined networking (SDN) architecture, CoWatch can collaboratively predict the DDoS attacks towards the EC servers and detect the attack flows in time. To efficiently filter the suspicious flows in distributed SDN, we devise an optimal threshold model by balancing the trade-off between collaboration efficiency and prediction effectiveness. We also explore and build on the LSTM model to design an algorithm for collaborative prediction and detection of DDoS Attacks. Experiment results on a number of datasets demonstrate the promising performance of CoWatch in effectiveness and efficiency. Author Affiliation: (a) School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen, China (b) Department of Computer Science, City University of Hong Kong, Hong Kong, China (c) Cyberspace Security Research Center, Peng Cheng Laboratory, Shenzhen, China * Corresponding author. Article History: Received 2 August 2022; Revised 8 January 2023; Accepted 15 February 2023 (footnote)[white star] A preliminary version (Zhou et al., 2021) of this paper was presented at The IEEE Global Communications Conference (GLOBECOM), 2021. Byline: Hongliang Zhou [hlzhou@hit.edu.cn] (a), Yifeng Zheng [yifeng.zheng@hit.edu.cn] (a,*), Xiaohua Jia [csjia@cityu.edu.hk] (a,b), Jiangang Shu [shujg@pcl.ac.cn] (c)

Keywords Measuring sentiment; Machine learning; Earnings calls; 10-Ks; WSJ Abstract Our paper relies on stock price reactions to colour words, in order to provide new dictionaries of positive and negative words in a finance context. We extend the machine learning algorithm of Taddy (2013), adding a cross-validation layer to avoid over-fitting. In head-to-head comparisons, our dictionaries outperform the standard bag-of-words approach (Loughran and McDonald, 2011) when predicting stock price movements out-of-sample. By comparing their composition, word-by-word, our method refines and expands the sentiment dictionaries in the literature. The breadth of our dictionaries and their ability to disambiguate words using bigrams both help to colour finance discourse better. Author Affiliation: (a) University of Colorado Boulder, United States (b) Southern Methodist University, United States (c) Norwegian School of Economics, Norway * Corresponding author. Article History: Received 9 December 2021; Revised 15 November 2022; Accepted 17 November 2022 (footnote)[white star] Dimitris Papanikolaou was the editor for this paper. We thank Simona Abis (discussant), Will Cong, Tony Cookson, Gerard Hoberg (discussant), Byoung-Hyoun Hwang (discussant), Jim Martin, David Stolin (discussant), Chenhao Tan, and Brian Waters for comments on an early draft, as well as seminar participants at Indiana University, INSEAD, the CU Boulder CS-NLP lab, the CU Boulder Finance division, the FutFinInfo webinar, NHH Finance brown bag, the 2021 FMA conference, the 2021 SFS Cavalcade, The Third Toronto Fintech Conference, the 2020 European Finance Association meetings, and the Michigan State University Fall 2019 conference. This work utilized the RMACC Summit supercomputer, which is supported by the National Science Foundation (Awards ACI-1532235 and ACI-1532236), the University of Colorado Boulder, and Colorado State University. The Summit supercomputer is a joint effort of the University of Colorado Boulder and Colorado State University. Byline: Diego García [http://leeds-faculty.colorado.edu/garcia/] (*,a), Xiaowen Hu [https://www.smu.edu/cox/Our-People-and-Community/Faculty/Xiaowen-Hu] (b), Maximilian Rohrer [https://www.maxrohrer.com] (c)

Keywords Rational inattention; Spectral analysis; Foresight Abstract This paper solves a dynamic rational inattention problem by formulating it in the frequency domain. The main result is a rational inattention version of the classical Wiener-Kolmogorov filter. This filter permits an infinite-dimensional state vector, provides a new line of attack for obtaining closed-form solutions, and can be implemented numerically using a simple iterative algorithm. The frequency-domain approach also sheds new light on why rational inattention produces forward-looking behavior: inattentive agents are willing to accept more uncertainty about the timing of disturbances in exchange for less uncertainty about fluctuations at the most important frequencies. Author Affiliation: Department of Economics, Duke University, 419 Chapel Drive, Durham, NC 27708, United States of America Article History: Received 30 December 2021; Revised 23 December 2022; Accepted 30 December 2022 (footnote)[white star] I would like to thank Hassan Afrouzi, Anna Bykhovskaya, Ryan Chahrour, Victoria Kostina, Andrea Lanteri, Andrew Patton, Galen Reeves, and Mirko Wiederholt for helpful comments, Ian Lee for research assistance, and the Pinetops Foundation for financial support during part of the time this paper was being written. Byline: Kyle Jurado [kyle.jurado@duke.edu]

Keywords Validation of OR computations; Maximum flow; Instance space analysis; Instance selection; Feature selection Highlights * Six key features of instances capture behaviors of popular maxflow algorithms; * Instance Space Analysis reveals regions of algorithm strength and weakness; * Representation bias via oversampling is mitigated by an instance selection procedure; * Selected maxflow instances are diverse and unbiased to study algorithm performance; * Resulting insights reveal impact of arc/path finding strategies on algorithm success. Abstract The Maximum Flow Problem (MFP) is a fundamental network flow theory problem, for which many algorithms, supported by strong theoretical worst-case analyses, have been proposed. However, their practical efficiency depends on the network structure, making it unclear which algorithm is best for a particular instance or a class of MFP. Instance Space Analysis (ISA) is a methodology that provides insights into such per-instance analysis. In this paper, the instance space of MFP is constructed and analysed for the first time. Novel features from the networks are extracted, capturing the performance of MFP algorithms. Additionally, this paper expands the ISA methodology by addressing the issue of how benchmark instances should be selected to reduce bias in the analysis. Using the enhanced ISA methodology with MFP as the case study, this paper demonstrates that the most important features can be detected, and machine learning methods can identify their impact on algorithm performance, whilst reducing the bias caused by over-representation within the selected sample of test instances. The enhanced methodology enables new insights into the performance of state-of-the-art general purpose MFP algorithms, as well as recommendations for the construction of comprehensive and unbiased benchmark test suites for MFP algorithm testing. Author Affiliation: School of Mathematics and Statistics, The University of Melbourne, Parkville, VIC 3010, Australia * Corresponding author. Article History: Received 14 June 2021; Accepted 9 April 2022 Byline: Hossein Alipour [h.alipour@unimelb.edu.au] (*), Mario Andrés Muñoz [munoz.m@unimelb.edu.au], Kate Smith-Miles [smith-miles@unimelb.edu.au]

Keywords Fully homomorphic encryption; Cross blockchain; Privacy-preserving; Edge computing Abstract The growing development of blockchain technology has led to the emergence of blockchain applications for various fields. One significant use of blockchain technology is the edge blockchain network, which is a blockchain network made up of connected edge computer nodes. However, on-chain privacy data leaking is a concern on the present edge blockchain network. The demand for collaborative interaction amongst edge computing nodes in many domains is growing more critical as the Internet of Things continues to evolve. In this paper, we propose a data privacy-preserving scheme for cross edge blockchain network, which uses the privacy protection technology of fully homomorphic encryption to encrypt the data on the chain to ensure the 'available and invisible' of the on-chain privacy data. First of all, this paper designs a cross edge blockchain model and give details of the interaction and privacy computing process in the cross edge blockchain. a distributed private key sharing scheme is designed in this work to provide the relay chain's auditable functionality. Subsequently, we describe the security of the scheme in detail. Finally, we implement this scheme using the CKKS algorithm. Through simulation experiments, we evaluate the performance of the instantiation process of the scheme. The test results manifest that the proposed scheme has excellent practicability and security. Author Affiliation: (a) School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing 100876, China (b) School of Cyberspace Science and Technology, Beijing Institute of Technology, Beijing 100876, China * Corresponding author. Article History: Received 5 June 2022; Revised 1 September 2022; Accepted 2 November 2022 (footnote)[white star] The research work is supported by Beijing Natural Science Foundation, China (Grant No. M21034) and the National Key Research and Development Plan in China (Grant No. 2020YFB1005500). Byline: Zhaofeng Ma (a), Jingyu Wang (a), Keke Gai [gaikeke@bit.edu.cn] (b,*), Pengfei Duan (a), Yuqing Zhang (a), Shoushan Luo (a)

Keywords Deep learning; 6G; 5G; Federated learning; Reinforcement learning; O-RAN; Zero-trust architecture Abstract In this position paper, we discuss the critical need for integrating zero trust (ZT) principles into next-generation communication networks (5G/6G). We highlight the challenges and introduce the concept of an intelligent zero trust architecture (i-ZTA) as a security framework in 5G/6G networks with untrusted components. While network virtualization, software-defined networking (SDN), and service-based architectures (SBA) are key enablers of 5G networks, operating in an untrusted environment has also become a key feature of the networks. Further, seamless connectivity to a high volume of devices has broadened the attack surface on information infrastructure. Network assurance in a dynamic untrusted environment calls for revolutionary architectures beyond existing static security frameworks. To the best of our knowledge, this is the first position paper that presents the architectural concept design of an i-ZTA upon which modern artificial intelligence (AI) algorithms can be developed to provide information security in untrusted networks. We introduce key ZT principles as real-time Monitoring of the security state of network assets, Evaluating the risk of individual access requests, and Deciding on access authorization using a dynamic trust algorithm, called MED components. To ensure ease of integration, the envisioned architecture adopts an SBA-based design, similar to the 3GPP specification of 5G networks, by leveraging the open radio access network (O-RAN) architecture with appropriate real-time engines and network interfaces for collecting necessary machine learning data. Therefore, this work provides novel research directions to design machine learning based components that contribute towards i-ZTA for the future 5G/6G networks. Author Affiliation: (a) Marconi-Rosenblatt AI/ML Innovation Laboratory, ANDRO Computational Solutions, LLC, Rome, 13440, NY, USA (b) Department of Electrical Engineering, University at Buffalo, The State University of New York, Buffalo, 14260, NY, USA * Corresponding author at: Marconi-Rosenblatt AI/ML Innovation Laboratory, ANDRO Computational Solutions, LLC, Rome, 13440, NY, USA. Article History: Received 19 February 2022; Revised 26 July 2022; Accepted 3 September 2022 Byline: Keyvan Ramezanpour (a), Jithin Jagannath [jjagannath@androcs.com] (a,b,*)

Keywords Multiple objective programming; Branch and bound; Combinatorial optimization; Linear relaxation; Warm-starting Highlights * Develops a branch-and-bound algorithm for multi-objective integer problems. * Uses the linear relaxation as a lower bound set in the algorithm. * Warm-starts the linear relaxation using information from the father node. * Warm-starting the linear relaxation improves efficiency considerably. * Reports extensive computational results. Abstract In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. In the recent literature, competitive frameworks has been proposed for bi-objective 0--1 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, however, the polyhedral structure of the linear relaxation becomes more complex, and consequently requires more computational effort to obtain. In this paper we overcome this obstacle by speeding up the computations. To do so, in each branching node we use information available from its father node to warm-start a Bensons-like algorithm. We show that the proposed algorithm significantly reduces the CPU time of the framework on several different problem classes with three, four and five objective functions. Moreover, we point out difficulties that arise when non-binary integer variables are introduced in the models, and test our algorithm on problem that contains non-binary integer variables too. Author Affiliation: Department of Economics and Business Economics, School of Business and Social Sciences, Aarhus University, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark * Corresponding author. Article History: Received 5 August 2021; Accepted 31 January 2022 Byline: Nicolas Forget [nforget@econ.au.dk] (*), Sune Lauth Gadegaard, Lars Relund Nielsen

Keywords Marketing networks; Distributed micro manufacturing; AI mediated consumption; Innovation clusters; Distributed marketing platforms Highlights * Business environments have become hyperturbulent due to exponential growth in knowledge and disruptive technologies. Interfirm marketing networks have to evolve more resilient structures by distributing functions closer to the sources of turbulence. * Manufacturing is being postponed and distributed closer to consumption. * Consumer markets are increasingly mediated by intelligent devices and algorithms. The markets are approaching perfect information and perfect heterogeneity. * Innovation is being distributed in clusters of technology firms and multiplex ecosystems. * The marketing hub at the center of the interfirm network is evolving into a technology platform and organizer of distributed manufacturing franchises. Abstract Interfirm networks are fundamental to market organization. The business environment is experiencing disruptive changes--uncertainty is increasing to levels of turbulence due to exponential growth in knowledge and technologies. There is a growing gap in our understanding of how all the changes are affecting the structure of interorganizational networks. This paper makes the case that networks are likely to reorganize around four strategic foci--distributed micro manufacturing, AI mediated consumption, distributed innovation, and distributed marketing. Our analysis suggests that the distributed networks will employ more polyarchic market mechanisms than the hierarchical or relational mechanisms of the past, and marketing will evolve a horizontal strategic posture, as well as reintegrate production but in a distributed micro-manufacturing framework. Author Affiliation: (a) The George Washington University School of Business, 307 Funger Hall, 2201 G Street, NW, Washington, DC 20052, United States (b) S. C. Johnson Distinguished Professor of Marketing, Kellogg School of Management, Northwestern University (emeritus), Evanston, IL, United States Article History: Received 13 August 2021; Revised 9 June 2022; Accepted 15 June 2022 (footnote)[white star] The authors thank two editors and two reviewers for their careful analyses and suggestions for the development of this paper. Byline: Ravi S. Achrol [achrol@gwu.edu] (a), Philip Kotler [pkotler@aol.com] (b)

Keywords Wireless networks; Proactive caching; Multipath routing; Energy saving; Integer linear programming; Simulated annealing Abstract The ever-continuing explosive growth of on-demand content distribution has imposed great pressure on mobile/wireless network infrastructures. To ease congestion in the network and to increase perceived user experience, caching of popular content closer to the end-users can play a significant role and as such this issue has received significant attention over the last few years. Additionally, energy saving is treated as a fundamental requirement in the design of next-generation mobile networks. However, there has been little attention to the overlapping area between energy saving and network caching especially when considering multipath routing. To this end, this paper proposes an energy-efficient caching with multipath routing support. The proposed scheme provides a joint anchoring of popular content into a set of potential caching nodes with optimized multipath support whilst ensuring a balance between transmission and caching energy cost. The proposed model also considers different content delivery modes, such as multicast and unicast. Two separated Integer-Linear Programming (ILP) models are formulated for each delivery mode. To tackle the curse of dimensionality we then provide a greedy simulated annealing algorithm, which not only reduces the time complexity but also provides a competitive performance. A wide set of numerical investigations reveal that the proposed scheme reduces the energy consumption up to 75% compared with other widely used caching approaches under the premise of network resource limitation. Sensitivity analysis to different parameters is also meticulously discussed in this paper. Author Affiliation: (a) School of Information Science and Engineering, Shandong Normal University, Changqing District, 250358, Ji'nan, China (b) Center of Telecommunication Research, Department of Engineering, King's College London, Strand, WC2R 2LS, London, UK * Corresponding author. Article History: Received 8 January 2022; Revised 30 July 2022; Accepted 6 August 2022 Byline: Yantong Wang [yantong@sdnu.edu.cn] (a,*), Vasilis Friderikos [vasilis.friderikos@kcl.ac.uk] (b)

Keywords DDoS attack; Cloud; DEHO; SVM; KPCA; Databases; Data samples; Cyber security Highlights * Proposing SVM based DEHO classifier to detect DDoS attack for the cloud computing environment. * Utilizing KPCA algorithm to obtain optimal features for further detection of normal and attack or malicious data. * Performing experiments for four different databases namely NSL-KDD, UNSW-NB15, ISCX IDand CIC-IDS2017 databases to determine the effectiveness of the proposed approach. Abstract Distributed denial of service (DDoS) attacks is rising exponentially and creates a severe threat to security. Generally, the DDoS attack may appear uncomplicated but they are hard to prevent and considered as one of the most significant cybersecurity issues. Hence, addressing against DDoS attacks turns out to be imperative. The major goal of this paper involves the optimal detection of data samples as normal data samples and malicious/attacked data samples. This paper proposes a security algorithm against DDoS attacks by employing four significant phases namely the Database training phase, Data pre-processing phase, Feature selection phase and Classification phase. Initially, the data samples are to be trained before using it for attack detection. Later, the sample group is created for every file and the data samples are pre-processed in the data pre-processing phase. Secondly, in feature selection phase, the selected features are optimized by employing kernel principal component analysis (KPCA) to obtain optimal features. Later, in the classification phase, a support vector machine-based discrete elephant herding optimization (SVM-DEHO) classifier is utilized to detect the data sample as normal data and attacked or malicious data. Finally, the proposed approach is examined for four different databases namely NSL-KDD, UNSW-NB15, ISCX ID and CIC-IDS2017 databases respectively. The experimental analyses are performed for various simulation metrics and the outcome reveals that the detection system performances are high using SVM-DEHO approach than other approaches. Author Affiliation: (a) Department of Computer Science and Engineering, Presidency University, Bengaluru, India (b) School of Computing Science and Engineering, Galgotias University, Greater Noida, India (c) Department of Computer Science and Engineering, Vardhaman College of Engineering, Hyderabad, India * Corresponding author. Article History: Received 12 May 2021; Revised 23 April 2022; Accepted 28 June 2022 Byline: Gowthul Alam MM [gowthulalam2005@gmail.com] (a,*), Jerald Nirmal Kumar S (b), Uma Mageswari R (c), Michael Raj TF (b)

Keywords Mobile crowdsourcing; Privacy protection; Blockchain; Edge computing; Federated learning; Localized Differential Privacy Abstract With the rapid popularization and development of the Internet of Things (IoT) and 5G networks, mobile crowdsourcing (MCS) has become an indispensable part in today's society. However, when task participants submit tasks, they are likely to expose their data privacy and location privacy. These privacy will be maliciously attacked and exploited by attackers (external attackers and untrusted third party). With the rapid increase of MCS data throughput, traditional cloud platforms can no longer meet the huge data processing needs. To solve these problems, this paper proposes an MCS federated learning system based on Blockchain and edge computing. This paper uses federated learning as the framework of the MCS system. The system protects data privacy and location privacy by using the Double local disturbance Localized Differential Privacy (DLD-LDP) proposed in this paper. Because the sensed data exists in multiple modalities (text, video, audio, etc.), this paper uses the Multi-modal Transformer (MulT) method to merge the multi-modal data before subsequent operations. To solve the problem that the third party is untrusted, we utilize Blockchain to distribute tasks and collect models in a distributed way. A reputation calculation method (Sig-RCU) is proposed to calculate the real-time reputation of task participants. Through conducting experiments on real data sets, the effectiveness and adaptation of the proposed DLD-LDP algorithm and Sig-RCU algorithm are verified. Author Affiliation: (a) School of Computer and Control Engineering, Yantai University, 264005, China (b) The Yantai Key Laborary of High-end Ocean Engineering Equipment and Intelligent Technology, Yantai, 264005, China (c) Department of Software Enportraitgineering & Game Development at Kennesaw State University (KSU), 1100 South Marietta Pkwy, Marietta, GA 30060, USA (d) Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA * Corresponding author at: School of Computer and Control Engineering, Yantai University, 264005, China. Article History: Received 14 February 2022; Revised 3 July 2022; Accepted 17 July 2022 Byline: Weilong Wang (a,b), Yingjie Wang [wangyingjie@ytu.edu.cn] (a,b,*), Yan Huang [yhuang24@kennesaw.edu] (c), Chunxiao Mu (a,b), Zice Sun (a,b), Xiangrong Tong (a,b), Zhipeng Cai [zcai@gsu.edu] (d)

Keywords Assignment; Dormitories; Stable matching; Many-to-many matching; Incentive compatibility Highlights * Socio-economic and academic achievements considerations in the assignment process of student-groups to dormitories. * Stable assignment under common preference-lists of dormitories over the student-groups. * Polynomial time algorithm for assigning student-groups to dormitories. * Polynomial time algorithm for listing all the stable assignments. * Incentive compatibility issues in student-groups assignment. Abstract This paper generalizes results of former papers on the assignment of students to dormitories, under an entrance criterion, by allowing students to apply in groups. A group-application means that its applicants ask to be assigned to the same dormitory, and otherwise they prefer living off-campus. The underlying assumption in our model is that the dormitories share a common preference over the student-groups, which is given by a strictly increasing ranking of their credit scores. The definition of a quasi-stable outcome is adjusted in order to incorporate student-group applications, and we prove that such an outcome always exists. Furthermore, a polynomial-time algorithm that finds all the quasi-stable outcomes is proposed. Apparently, not all properties of the single students' model continue to hold under group-applications. Finally, we consider the incentive compatibility property of the proposed algorithm, and describe a specific quasi-stable outcome for which no subset of student-groups can gain by misrepresenting their preferences over the dormitories. Author Affiliation: Coller School of Management, Tel Aviv University, Tel Aviv 69978, Israel * Corresponding author. Article History: Received 18 February 2020; Accepted 30 December 2021 Byline: Nitsan Perach [nitsan.perah@gmail.com] (*), Shoshana Anily [anily@tauex.tau.ac.il]

Keywords Occasionally binding constraints; Effective lower bound; Computational methods Abstract Structural estimation of macroeconomic models and new HANK-type models with extremely high dimensionality require fast and robust methods to efficiently deal with occasionally binding constraints (OBCs). This paper proposes a novel algorithm that solves for the perfect foresight path of piecewise-linear dynamic models. In terms of computation speed, the method outperforms its competitors by more than three orders of magnitude. I develop a closed-form solution for the full trajectory given the expected duration of the constraint. This allows to quickly iterate and validate guesses on the expected duration until a perfect-foresight equilibrium is found. A toolbox, featuring an efficient implementation, a model parser and various econometric tools, is provided in the Python programming language. Benchmarking results show that for medium-scale models with an occasionally binding interest rate lower bound, more than 150,000 periods can be simulated per second. Even simulating large HANK-type models with almost 1000 endogenous variables requires only 0.2 milliseconds per period. Author Affiliation: Institute for Macroeconomics and Econometrics, University of Bonn, Adenauerallee 24--42, Bonn 53113, Germany Article History: Received 31 January 2022; Revised 6 July 2022; Accepted 6 September 2022 (footnote)[white star] I am grateful to Flora Budianto, Hans-Martin von Gaudecker, Alexander Meyer-Gohde, Tom Holden, Kenneth Judd, Alexander Richter, Felix Strobel, two anonymous reviewers and participants of the 2018 Stanford MMCI Conference, the 2018 EEA Annual Congress and the 2018 VfS Jahrestagung for discussions and helpful comments on the contents of this paper. Part of the research leading to the results in this paper has received financial support from the Alfred P. Sloan Foundation under the grant agreement G-2016-7176 for the Macroeconomic Model Comparison Initiative (MMCI) at the Institute for Monetary and Financial Stability. I gratefully acknowledge financial support by the DFG under CRC-TR 224 (projects C01 and C05) and under project number 441540692. Byline: Gregor Boehl [gboehl@uni-bonn.de]

Keywords Predictive inference; State space models; Stochastic volatility; Time-varying parameters Abstract This paper proposes methods for Bayesian inference in time-varying parameter (TVP) quantile regressions (QRs) featuring conditional heteroskedasticity. I use data augmentation schemes to render the model conditionally Gaussian and develop an efficient sampling algorithm. Regularization of the high-dimensional parameter space is achieved via dynamic shrinkage priors. The merits of the proposed approach are illustrated in a simulation study, and a simple version of TVP-QR based on an unobserved components model is applied to dynamically trace the quantiles of inflation in the United States, the United Kingdom and the euro area. In an out-of-sample forecast exercise, I find the proposed model to be competitive and perform particularly well for higher-order and tail forecasts. A detailed analysis of the resulting predictive distributions reveals that they are sometimes skewed and occasionally feature heavy tails. Author Affiliation: Department of Economics, University of Salzburg, Mönchsberg 2a, 5020 Salzburg, Austria Article History: Received 13 April 2022; Revised 31 May 2022; Accepted 8 July 2022 (footnote)[white star] This paper was previously circulated as 'Tail forecasts of inflation using time-varying parameter quantile regressions' (arXiv:2103.03632). I gratefully acknowledge valuable comments and suggestions by Niko Hauzenberger, Paul Hofmarcher, Florian Huber, Gary Koop, James Mitchell, Christoph Pfarrhofer and Anna Stelzer, and financial support by the Austrian Science Fund (FWF, grant no. ZK 35). Codes and replication files are available at github.com/mpfarrho/tvp-qr. Byline: Michael Pfarrhofer [michael.pfarrhofer@plus.ac.at]

Keywords Real-time systems; Constrained deadlines; DAG tasks Abstract The development of real-time systems has stimulated studies of real-time scheduling algorithms and schedulability analysis methods for parallel tasks, whose number has increased from year to year. For parallel tasks that cannot be converted to sequential tasks, the existing scheduling strategies mostly use one scheduling strategy. From the experiment results when we use different scheduling strategies to schedule the same tasks, we can observe these strategies have advantages for tasks with specific parameter characteristics. We combine the strengths of three algorithms: the partitioned algorithm, the federated scheduling algorithm and the GFP algorithm. A BH-Mixed scheduling algorithm for directed acyclic graph tasks with constrained deadlines is proposed in this paper. We design a classification method according to the feature of these three algorithms. The tasks are divided into three groups and scheduled by the partitioned algorithm, the federated scheduling algorithm and the GFP algorithm respectively. Experimental results show that the BH-Mixed scheduling algorithm outperforms other algorithms tested in this paper. Author Affiliation: (a) School of Electronics and Information Engineering, Harbin Institute of Technology, China (b) Department of Computer Science and Technology, Northeast Forestry University, China * Corresponding authors. Article History: Received 12 March 2022; Revised 12 June 2022; Accepted 6 August 2022 Byline: Jiaqing Qiao [qiaojiaqing@hit.edu.cn] (a), Langyu Liu [20s105149@stu.hit.edu.cn] (a), Fei Guan [fei.guan@nefu.edu.cn] (b,*), Wenbin Zheng [zhengwenbin@hit.edu.cn] (a,*)

Keywords Production; Assembly line balancing; Optimization; Survey Highlights * We survey the assembly line balancing research of the past 15 years. * Progress in all stages of the decision-making process is elaborated. * Important new problems, models, and algorithms are surveyed. * Future research needs are identified. Abstract Ever since the times of Henry Ford up to today's industry 4.0 era, flow-oriented assembly processes, where an assembly line conveys the workpieces from workstation to workstation, are very important for mass-producers in manifold branches of industry. Among the most elementary optimization problems in this context is the assembly line balancing problem, which decides on the division of labor among the stations of an assembly line. This paper surveys the scientific literature on assembly line balancing that has been published since the last major review papers have appeared in 2006 and 2007, respectively. We cover all essential stages of the decision making process: we address novel methods to efficiently gather the relevant (precedence graph) data, review especially new problem variants and models treated in the literature, and survey the most important algorithmic developments. Furthermore, we outline a possible research agenda for the next fifteen years. Author Affiliation: (a) Lehrstuhl für Operations Management, Friedrich-Schiller-Universität Jena, Carl-Zeiß-Straße 3, Jena 07743, Germany (b) Lehrstuhl für Management Science, Friedrich-Schiller-Universität Jena, Carl-Zeiß-Straße 3, Jena 07743, Germany * Corresponding author. Article History: Received 20 August 2021; Accepted 22 November 2021 Byline: Nils Boysen [https://www.om.uni-jena.de] (*,a), Philipp Schulze [philipp.schulze@uni-jena.de] (b), Armin Scholl [https://www.mansci.uni-jena.de] (b)

Keywords Integer programming; Robust optimization; Branch-and-price; Parallel machine scheduling Highlights * A robust reformulation of a machine scheduling problem that minimizes the worst-case total tardiness for unrelated parallel machines with sequence-dependent setups and uncertain processing times has been proposed. * An efficient solution methodology that utilizes a branch-and-price algorithm that exploits the particular properties of the problem has been developed. * The importance of Pareto efficiency has been shown, and extensions of the related solution methodology are presented. * Monte Carlo simulation results have shown that the robust approach's improvement can get as high as 56% compared with the deterministic approach. Abstract This paper studies a machine scheduling problem that minimizes the worst-case total tardiness for unrelated parallel machines with sequence-dependent setup and uncertain processing times. We propose a robust optimization reformulation of the related machine scheduling problem and discuss several important properties of the mathematical model and the reformulation approach. The proposed model generalizes robust parallel machine scheduling problems by including sequence-dependent setup times and ellipsoidal uncertainty sets. Another key contribution of the paper is to show that scheduling problems usually have alternative optimal solutions for the worst-case tardiness objective, whose performance under nominal processing times may vary or vice a versa. This issue has been addressed by studying the Pareto efficient extensions of the proposed robust optimization models to provide solutions that are immune to changes in processing times. A branch-and-price algorithm has been developed to solve realistically sized instances in less than one hour, which a commercial solver cannot achieve. Numerical results show the effectiveness of the proposed approach since realistically sized instances such as (4 machines, 32 jobs) and (150 machines, 300 jobs) can be solved to optimality within the time limit, and the (average) objective function value improvement made by the robust approach can get as high as 56% compared with the (nominal) optimal solutions that ignore uncertainty in problem data. Author Affiliation: (a) Özyegin University, Istanbul, Turkey (b) Istanbul Bilgi University, Istanbul, Turkey * Corresponding author. Article History: Received 3 May 2021; Accepted 12 November 2021 Byline: Ihsan Yanikoglu (*,a), Tonguc Yavuz (a,b)

Keywords Fog computing; Task offloading; Delay & latency; Energy & power consumption; Cost; Machine learning Abstract The exponential growth in Internet of Things (IoT) devices and the limitations of cloud computing in terms of latency and quality of service for time-sensitive applications have led to the unfolding of the efficient middleware technology called fog. Fog computing circumvents the limitations of the cloud by creating a seamless continuum between the things/IoT/end-user devices and the cloud and reducing the effective distance. However, fog computing faces challenges for offloading tasks for their remote computation at some level. Hence, the optimality of task offloading is the primary research area in fog computing. Several contemporary papers exist on this important subject. The research gap in reviewing all these task offloading algorithms has motivated us for their presentation in the form of a detailed survey in this paper. There exist some survey papers which deal with the task offloading. However, none of them has covered the basics of optimization techniques and their solution approaches. The primary objective of this paper is to provide the readers with a complete overview of the journey from a task offloading idea to its mathematical problem formulation and finally to its solution with all details of optimization techniques. We begin by introducing fog computing, and task offloading process followed by several task offloading factors governing decision-making process and their surveys. A section is fully dedicated to the survey of offloading objectives with examples. We also present several optimization approaches used in task offloading. Finally, the last section dedicates to the challenges and future direction in fog computing. The outcomes of the survey will benefit readers in learning the optimization used in task offloading, and it will also provide them a systematic design of offloading scheme with specific objectives. Author Affiliation: Department of Computer Science and Engineering, Indian Institute of Technology (ISM) Dhanbad, Jharkhand 826004, India * Corresponding author. Article History: Received 21 February 2022; Revised 2 June 2022; Accepted 28 June 2022 Byline: Nidhi Kumari [nidhi3rdjan1995@gmail.com] (*), Anirudh Yadav [yadavanirudh1997@gmail.com], Prasanta K. Jana [prasantajana@iitism.ac.in]

Keywords Forward security; Group signature; Lattice, Message authentication; Vehicular ad hoc networks (VANETs); Traceability; Applied cryptography; Information security Abstract Message authentication has been a research hotspot in current vehicular ad hoc networks (VANETs). Many researchers adopt group signatures based on number-theoretic assumptions to authenticate the vehicular users' identities. Nevertheless, the classical group signature is vulnerable to quantum computing attacks and without considering the negative consequences of secret key disclosure. In this paper, to address these problems, we propose a novel group signature protocol for authentication in VANETs, which is based on lattice cryptography to achieve quantum-resistance and Bonsai-tree signature architecture to achieve forward security. Our scheme is proven secure in terms of traceability, anonymity, and forward-security under the Short Integer Solution (SIS) and Learning With Errors (LWE) hardness. Through comprehensive performance evaluation, we demonstrate that the storage overhead of our scheme is relatively diminutive and the computation cost of the sign and verify algorithms are efficient and practical compared with other existing schemes. Author Affiliation: (a) School of Information Engineering, North China University of Technology, China (b) School of Cyberspace Security, Beijing University of Posts and Telecommunications, China (c) Department of Computer Science, The University of Hong Kong, China (d) Department of Computing, The Hong Kong Polytechnic University, China (e) Institute of Information Engineering, Chinese Academy Sciences, China * Corresponding authors. Article History: Received 29 March 2022; Revised 6 June 2022; Accepted 30 June 2022 (footnote)1 Yibo Cao and Shiyuan Xu have the same contribution to this paper. Byline: Yibo Cao (a,b,1), Shiyuan Xu [13501199447@163.com] (a,c,1,*), Xue Chen (a,d), Yunhua He (a,e,*), Shuo Jiang (a)

Keywords Internet of Things; Edge Networks; Time-Expanded Graph; Utility Maximization; Task Offloading Abstract This paper comprehensively investigates spatio-temporal dynamics for task offloading in the Internet of Things (IoT) Edge Network (iTEN) in order to maximize utility. Different from the previous works in the literature that only consider partially dynamic factors, this paper takes into account the time-varying wireless link quality, communication power, wireless interference on task offloading, and the spatiotemporal dynamics of energy harvested by terminals and their charging efficiency. Our goal is to maximize utility during the task offloading by considering the above-mentioned factors, which are relatively complex but closer to reality. This paper designs the Time-Expanded Graph (TEG) to transfer network dynamics and wireless interference into some static weight in the graph so as to devise the algorithm easily. This paper firstly devises the Single Terminal (ST) utility maximization algorithm on the basis of TEG when there is only one terminal. In the case of multiple terminals, it is very complicated to directly solve the utility maximization of the task offloading. This paper adopts the framework of Garg and Könemann and devises a multi-terminal algorithm (MT) to maximize the total utility of all terminals. MT is a fast approximate algorithm and its approximate ratio is 1-3[final sigma], where 0 Author Affiliation: (a) School of Computer Science and Technology, Hangzhou Dianzi University, Hangzhou, 310018, China (b) Hangzhou Hikvision Digital Technology Co., Ltd., Hangzhou, 310052, China * Corresponding author. Article History: Received 22 December 2021; Revised 27 June 2022; Accepted 4 July 2022 (footnote)1 Equal contribution and shared co-first authorship. Byline: Jiacheng Wang [jcwang@hdu.edu.cn] (a,1), Jianhui Zhang [jh_zhang@hdu.edu.cn] (a,1), Liming Liu [limingliu@hdu.edu.cn] (a), Xuzhao Zheng [zhengxuzhao66@163.com] (b), Hanxiang Wang [hx_wang@hdu.edu.cn] (a), Zhigang Gao [gaozhigang@hdu.edu.cn] (a,*)

Keywords LEO; Stepping beam; Tracking beam; Satellite; User beams Abstract A stepping (or tracking) beam LEO constellation provides service to predefined areas instead of full coverage. As a result, satellites using stepping beams are more efficient, as power is used only for populated areas. When the constellation shifts, each satellite adjusts its beams locations and sizes, such that each area is serviced by one of the satellites that has the area in its FoV. Current algorithms do not scale well and require considerable satellite compute resources. This paper proposes two novel algorithms to manage the beam allocation. The Dynamic Service Cell Beam Allocation algorithm (DSBA) allocates the beam dynamically in O (m.sup.2) time complexity, where m is the number of service cells in the satellite FoV. A novel Pre-planning Service Cell Beam Allocation algorithm (PSBA) is the first to use pre-planning of the user beams. The algorithm is executed once (before the dynamic allocations are made) requiring O (n.sup.2[middle dot]k.sup.3) time, where n is the number of service cells served by the constellation and k is the number of satellite beams. PSBA has demonstrated similar dynamic beam allocation efficiency as DSBA with performance improvements of up to 100%. Author Affiliation: School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel * Corresponding author. Article History: Received 29 December 2021; Revised 1 July 2022; Accepted 2 July 2022 (footnote)[white star] Preliminary version of this paper appeared in IEEE WiMob 2021. Byline: Oren Markovitz [orenmar@post.bgu.ac.il], Michael Segal [segal@bgu.ac.il] (*)

Keywords Packing; 2D bin packing; Guillotine; Heuristic; Variable-sized bins Highlights * Heuristic for solving the 2D bin packing problem with guillotine constraints. * Supports variants with variable-sized bins and 90-degree rotation of items. * Combines the ruin and recreate paradigm with a goal-driven approach. * Experiments demonstrate the effectiveness of the introduced heuristic. Abstract This paper addresses the two-dimensional bin packing problem with guillotine constraints. The problem requires a set of rectangular items to be cut from larger rectangles, known as bins, while only making use of edge-to-edge (guillotine) cuts. The goal is to minimize the total bin area needed to cut all required items. This paper also addresses variants of the problem which permit 90.sup.[ring operator] rotation of items and/or a heterogeneous set of bins. A novel heuristic is introduced which is based on the ruin and recreate paradigm combined with a goal-driven approach. When applying the proposed heuristic to benchmark instances from the literature, it outperforms the current state-of-the-art algorithms in terms of solution quality for all variants of the problem considered. Author Affiliation: KU Leuven, Department of Computer Science, NUMA, Belgium * Corresponding author. Article History: Received 13 January 2021; Accepted 17 November 2021 Byline: Jeroen Gardeyn [jeroen.gardeyn@kuleuven.be] (*), Tony Wauters [tony.wauters@kuleuven.be]

Keywords Routing; Electric vehicles; Recharging; Battery swapping; Scheduling and synchronisation Highlights * An EVRPTW with RSs and synchronised mobile battery swapping is proposed. * An exact and a heuristic solution method are developed. * Comparative analyses of different logistics scenarios by ECVs are performed. * Cost and emissions savings and ECVs extra-urban delivery opportunities are reported. Abstract A primary challenge in goods distribution using Electric Commercial Vehicles (ECVs) pertains to tackling their limited driving range. This paper proposes a multi-faceted approach towards increasing the driving range of ECVs by coordinating the options of: (i) intra-route recharging at an intermediate Recharging Station (RS), with (ii) synchronised en-route battery swapping services performed by Battery Swapping Vans (BSVs) at a pre-planned rendezvous time and space. We introduce and solve a variant corresponding to an Electric Vehicle Routing Problem with Time Windows, RSs and Synchronised Mobile Battery Swapping (EVRPTW-RS-SMBS). In the proposed model, route planning is carried out synchronously for two interdependent fleets, i.e., ECVs and BSVs, which work in tandem to complete the delivery tasks. To address methodological complications arising from the simultaneous consideration of intra-route recharging at RSs and the synchronised battery swapping on-the-fly, the paper develops a pre-optimisation procedure based on a Non-Dominated Path Identification (NDPI) algorithm that is used in deriving a significantly strengthened path-based formulation of the problem, and an efficient dynamic programming based heuristic algorithm. To gain practical insights on the economic and environmental added value and viability of the proposed logistics model, we compare different scenarios for goods distribution using ECVs in urban and regional levels in London and Southeast England, respectively. A set of numerical experiments are further performed to demonstrate the efficiency of the proposed algorithms. Our results indicate significant cost and emissions savings and an opportunity for going beyond last mile local deliveries using ECVs with the proposed logistics model. Author Affiliation: (a) Centre for Logistics and Heuristic Optimisation (CLHO), Kent Business School, University of Kent, Chatham ME4 4TE, UK (b) Centre for Transport and Logistics (CENTRAL), Department of Management Science, Lancaster University Management School, Lancaster LA1 4YX, UK * Corresponding author. Article History: Received 17 December 2020; Revised 22 September 2021; Accepted 25 September 2021 Byline: Ramin Raeesi [r.raeesi@kent.ac.uk] (a,*), Konstantinos G. Zografos [k.zografos@lancaster.ac.uk] (b)

Keywords Service Function Chaining; Network Function Virtualization; Multi-cloud; Latency; Routing; Linear programming Abstract The advent of virtualization-based infrastructure needed for 5G brought new challenges in utilizing the existing physical network infrastructure effectively. Designing physical routes between virtual network functions in a multi-cloud environment is usually handled as a maximum flow problem, separately considering latency requirements. This paper presents an algorithm designed for low latency edge-cloud environments, where results meet both bandwidth and latency requirements of the planned traffic in one step. The proposed algorithm is much faster compared to the wide-spread linear program based flow maximization approach as the incorporated filtering of route candidates by latency allows more efficient search. The paper demonstrates the operation of the algorithm by a detailed example. Author Affiliation: H-1083 Bókay János Street 36-42., Budapest, Hungary Article History: Received 22 July 2021; Revised 28 January 2022; Accepted 13 April 2022 Byline: Péter Hegyi [peter.hegyi@nokia-bell-labs.com]

Keywords Humanitarian coverage path planning; Unmanned aerial vehicle routing; Greedy randomized adaptive search procedure Highlights * A novel approach for humanitarian coverage path planning using UAVs. * The cumulative UAV routing problem formulation. * Three effective multithreaded GRASP-VND metaheuristic implementations. * Obtained best known solutions for the cumulative capacitated vehicle routing problem. Abstract This paper presents a Cumulative Unmanned Aerial Vehicle Routing Problem (CUAVRP) approach to optimize Humanitarian Coverage Path Planning (HCPP). Coverage path planning consists of finding the route which covers every point of a certain area of interest. This paper considers a Search & Rescue mission, using a homogeneous fleet of Unmanned Aerial Vehicles (UAVs). In this scenario, the objective is to minimize the sum of arrival times at all points of the area of interest, thus, completing the search with minimum latency. The HCPP problem is transformed into a Vehicle Routing Problem by using an approximate cellular decomposition technique to discretize the area into a grid, where the rectangles represent the UAV sensor's field of view. The center points of the formed rectangles, become the nodes used for a UAV routing problem. This approach uses the objective of minimizing the sum of arrival times at customers, found in the Cumulative Capacitated Vehicle Routing Problem (CCVRP), adjusted for the Search & Rescue Coverage Path Planning using UAVs. The Min-max objective is also implemented and tested. Three versions of a Parallel Weighted Greedy Randomized Adaptive Search Procedure - Variable Neighborhood Decent (GRASP-VND) algorithm is implemented to solve the Cumulative UAV Routing Problem for Humanitarian Coverage Path Planning. Author Affiliation: Technical University of Crete, School of Production Engineering and Management, University Campus, Chania 73100, Greece * Corresponding author. Article History: Received 2 November 2020; Accepted 7 September 2021 Byline: Nikolaos A. Kyriakakis [nkyriakakis@isc.tuc.gr], Magdalene Marinaki [magda@dssl.tuc.gr], Nikolaos Matsatsinis [nikos@ergasya.tuc.gr], Yannis Marinakis [marinakis@ergasya.tuc.gr] (*)

Keywords Software defined networking (SDN); Distributed control plane; Load balancing; Lyapunov optimization; Approximation algorithm Abstract A distributed control plane is more scalable and robust in software defined networking. This paper focuses on controller load balancing using packet-in request redirection, that is, given the instantaneous state of the system, determining whether to redirect packet-in requests for each switch, such that the overall control plane response time (CPRT) is minimized. To address the above problem, we propose a framework based on Lyapunov optimization. First, we use the drift-plus-penalty algorithm to combine CPRT minimization problem with controller capacity constraints, and further derive a non-linear program, whose optimal solution is obtained with brute force using standard linearization techniques. Second, we present a greedy strategy to efficiently obtain a solution with a bounded approximation ratio. Third, we reformulate the program as a problem of maximizing a non-monotone submodular function subject to matroid constraints. We implement a controller prototype for packet-in request redirection, and conduct trace-driven simulations to validate our theoretical results. The results show that our algorithms can reduce the average CPRT by 81.6% compared to static assignment, and achieve a 3x improvement in maximum controller capacity violation ratio. Author Affiliation: (a) State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210023, China (b) Department of Computer Science and Engineering, Chinese University of Hong Kong, Shatin, Hong Kong Special Administrative Region of China * Corresponding authors. Article History: Received 16 February 2022; Revised 13 May 2022; Accepted 25 May 2022 (footnote)[white star] This paper is an extended version of work published in . This work was supported in part by the National Natural Science Foundation of China under Grant No. 61872178, 61832005, 61672276, 61872173, 61802172, in part by the Natural Science Foundation of Jiangsu Province, China under Grant No. BK20181251, in part by the Fundamental Research Funds for the Central Universities, China under Grant 021014380079, in part by funding from the Research Grants Council of Hong Kong (GRF 11209520) and from CUHK, Hong Kong Special Administrative Region of China (4937007, 4937008, 5501329, 5501517). Byline: Rui Xia [xiarui@smail.nju.edu.cn] (a), Haipeng Dai [haipengdai@nju.edu.cn] (a,*), Jiaqi Zheng [jzheng@nju.edu.cn] (a,*), Hong Xu [hongxu@cuhk.edu.hk] (b), Meng Li [menson@smail.nju.edu.cn] (a), Guihai Chen [gchen@nju.edu.cn] (a,*)

Keywords Graph neural networks; Degree-based quantization; Sensitive node; Protective mask Abstract Recently, graph neural networks (GNNs) have achieved excellent performance on many graph-related tasks. Existing typical GNNs follow the neighborhood aggregation strategy, which updates nodes' information by aggregating the feature of neighboring nodes. However, these hybrid execution patterns limit their deployment on resource-limited devices. Quantification is an effective technique for deep neural networks (DNNs) inference acceleration, but few studies have considered exploring suitable quantization algorithms for GNNs. In this paper, we propose a degree-based quantization (DBQ) that can identify sensitive nodes in the graph structure. The protective masks are used to ensure that sensitive nodes perform full-precision operations, and the remaining nodes are quantized. In this way, the effect of dynamically changing the precision is achieved to achieve greater acceleration while retaining better classification accuracy. To support DBQ and convert it into performance improvements, we design a new architecture. Elaborate pipelines and specialized optimizations effectively improve inference speed and accuracy. Compared to state-of-the-art GNN accelerators, DBQ gains on 2.4 x speedups and improves accuracy by 27.7%. Author Affiliation: (a) School of microelectronics, Shanghai University, Shanghai, 201899, China (b) College of Information Science and Engineering, Hunan University, Hunan, 410082, China (c) Electrical and Computer Engineering, National University of Singapore, Singapore, 119077, Singapore (d) Institute for Infocomm Research (I2R), A*STAR, Singapore, 138632, Singapore (e) Shanghai University, Shanghai, 201899, China * Corresponding author. Article History: Received 31 December 2021; Revised 7 April 2022; Accepted 19 May 2022 (footnote)[white star] This document is the result of a research project funded by Shanghai University in China. (footnote)1 Yilong Guo and Yuxuan Chen contributed equally to this paper. Byline: Yilong Guo [wdz_gyl@shu.edu.cn] (a,1), Yuxuan Chen [chenyuxuan123@shu.edu.cn] (a,1), Xiaofeng Zou [zouxiaofeng@hnu.edu.cn] (b,c,*), Xulei Yang [yang_xulei@i2r.a-star.edu.sg] (d), Yuandong Gu [Alex.Gu@shu.edu.cn] (e)

Keywords TCP; P4; Programmable data plane; Congestion control; AQM; SmartNICs; Network diagnosis Abstract The increasing performance requirements of today's Internet applications demand a reliable mechanism to transfer data. Many applications rely on the Transmission Control Protocol (TCP) as the transport protocol, due to its ability to adapt to properties of the network and to be robust in the face of many kinds of failures. However, improving the performance of applications that rely on TCP has been limited by the closed nature of legacy switches, which do not provide accurate visibility of network events. With the emergence of P4-programmable devices, developers can rapidly implement and test customized solutions that use fine-grained telemetry, provide sub round-trip time feedback to end devices to enhance congestion control, precisely isolate traffic to offer better Quality of Service (QoS), quickly detect congestion and re-route traffic via alternate paths, and optimize server resources by offloading protocols. This paper first surveys recent works on P4-programmable devices, focusing on schemes aimed at enhancing TCP performance. It provides a taxonomy classifying the aspects that impact TCP's behavior, such as congestion control, Active Queue Management (AQM) algorithms, TCP offloading, and network measurement schemes. Then, it compares the P4-based solutions, and contrasts those solutions with legacy implementations. Lastly, the paper presents challenges and future trends. Author Affiliation: (a) College of Engineering and Computing, University of South Carolina, Columbia, USA (b) Department of Mathematics and Computer Science, Brandon University, Canada * Corresponding author. Article History: Received 3 September 2021; Revised 3 April 2022; Accepted 6 May 2022 Byline: Jose Gomez [gomezgaj@email.sc.edu] (a), Elie F. Kfoury [ekfoury@email.sc.edu] (a), Jorge Crichigno [jcrichigno@cec.sc.edu] (a,*), Gautam Srivastava [srivastavag@brandonu.ca] (b)

Keywords Edge computing; Network function virtualization; Network security Abstract Edge computing emerges as a new paradigm to provide low-latency network services in close proximity to end users. Based on the network function virtualization (NFV) technology, network services can be flexibly and scalably provisioned as virtual network function (VNF) chains deployed at edge servers. With such advantages, both the industry and research communities have done extensive studies on deploying VNF chains at network edge. The existing works mainly take an ideal assumption that the network is totally safe and there are no malicious users. Therefore, they leverage all available resources to serve their users. However, such an assumption is impractical in real networks. Security services, such as firewall, deep packet detection, intrusion detection, are always required for production networks. The existing service deployment methods fail to consider the co-existence of security services and functionality services. In this paper, we present the topic of joint deployment of both security and functionality services, wherein the security services are responsible to check the data flows before being processed by the functionality services. To solve this problem, we propose the Secure Deployment Pattern, which aims to simultaneously satisfy the security protection and QoS requirements at network edge. It divides the services into two kinds, i.e., the user-oriented functionality services, and the service provider-oriented security services. In this case, it is very challenging to jointly deploy the security services and functional services with respect to the resource and latency constraints. We formulate this problem as an integer programming model, and propose the heuristic algorithms to solve it. As far as we know, this paper is the first step, which targets at a proper orchestration of security and functionality services in edge computing. Extensive evaluations show that the proposed algorithms are effective and efficient, in terms of the execution time and the average number of served requests. Author Affiliation: (a) College of Computer Science and Technology, National University of Defense Technology, Changsha, China (b) Science and Technology Laboratory on Information Systems Engineering, National University of Defense Technology, Changsha, China (c) State Key Laboratory of High Performance Computing, National University of Defense Technology, Changsha, China * Corresponding author. Article History: Received 25 November 2021; Revised 3 March 2022; Accepted 4 April 2022 Byline: Yudong Qin [qinyudong12@nudt.edu.cn] (a), Deke Guo [dekeguo@nudt.edu.cn] (b,c,*), Lailong Luo [luolailong09@nudt.edu.cn] (a,b), Ming Xu [xuming@nudt.edu.cn] (a)

Keywords Combinatorial optimization; Flow shop scheduling; Early and late work; Dynamic programming; FPTAS Highlights * Two-machine ow shop scheduling to maximize total early work is considered. * A dynamic programming approach running in O(n.sup.2d.sup.2) time is proposed. * A fully polynomial time approximation scheme (FPTAS) is developed. * The approximation results work for the weighted model - if a specific constraint is satisfied. Abstract This paper considers scheduling in a two-machine flow shop to maximize the total early work subject to a common due date. The early work of a job is a parameter defined as the total amount of the job that is processed before the specified due date. We mainly focus on the unweighted model in this paper, and propose a dynamic programming approach running in O(n.sup.2d.sup.2) time (compared with the previous result in O(n.sup.2d.sup.4) time for the weighted case discussed in the literature). Then we analyse the problem from an approximation point of view, in which we first show that Johnson's algorithm, one of the most classical ones in flow shop scheduling, can only achieve the worst performance ratio for the considered problem (although it is an optimal one for makespan minimization). With the motivation of proposing better approximation algorithms, we further design a fully polynomial time approximation scheme (FPTAS). Finally, we point out that the approximation results also work for the weighted model - if a specific constraint is satisfied. Author Affiliation: (a) Liaoning University of Technology, School of Electronics and Information Engineering, Shiying 169, Jinzhou 121001, China (b) Dalian University of Technology, School of Software, Tuqiang 321, Dalian 116023, China (c) National Yang Ming Chiao Tung University, Institute of Information Management, Shinchu 300, Taiwan (d) Poznan University of Technology, Institute of Computing Science, Piotrowo 2, Poznan 60-965, Poland (e) European Centre for Bioinformatics and Genomics, Polish Academy of Sciences, Piotrowo 2, Poznan 60-965, Poland * Corresponding author. Article History: Received 21 February 2021; Accepted 30 July 2021 Byline: Xin Chen (a), Qian Miao (b), Bertrand M.T. Lin [bmtlin@mail.nctu.edu.tw] (*,c), Malgorzata Sterna (d), Jacek Blazewicz (d,e)

Keywords Routing; Pickup and delivery problems; Ring; Computational complexity Highlights * A new class of Pickup and Delivery problems on circular routes (rings) is introduced. * A classification scheme is proposed. * Complexity proofs are given for variants with single direction of travel on the ring. * Polynomial algorithms and ILP models are proposed. * Computational experiments demonstrate the efficiency of the mathematical formulations. Abstract In this paper we introduce a new class of Pickup and Delivery problems on circles (or rings). These problems arise in the field of public transportation systems where autonomous (i.e. driverless) vehicles travel on circular networks. We consider a set of stations arranged in a circle and a set of transportation requests. Each request asks for the transportation of a certain quantity from a pickup station to a delivery station. A fleet of capacitated vehicles is available at the depot. In the first part of the paper we propose a classification scheme for these problems. In the second part, we address the variants in which the vehicles are allowed to move in a single direction of the circle (either clockwise or counterclockwise) and the objective is to minimize the number of tours on the ring while serving all the requests. We provide a complexity analysis for this class of problems. We develop polynomial time algorithms for the variants that are polynomially solvable and proofs of NP-hardness for the variants that are NP-hard. In addition, for the latter, we provide mathematical formulations and perform computational tests that show the effectiveness of these formulations. Finally, we compare optimal solutions with those obtained using a straightforward greedy algorithm. Author Affiliation: (a) Université Clermont Auvergne, CNRS, UMR 6158 LIMOS, F-13541 Gardanne France (b) ESSEC Business School, 3 Avenue Bernard Hirsch, 95000 Cergy, France (c) Mines Saint-Etienne, Univ. Clermont Auvergne, CNRS, UMR 6158 LIMOS, Centre CMP, F-13541 Gardanne France (d) LIMOS, Institut Supérieur d'Informatique de Modélisation et leurs Applications and ISIMA, Campus des Cézeaux, Aubiére Cedex, France * Corresponding author. Article History: Received 23 January 2021; Accepted 28 July 2021 (footnote)1 This work was sponsored by a public grant overseen by the French National Research Agency as part of the 'Investissements d'Avenir' through the IMobS3 Laboratory of Excellence (ANR-10-LABX-0016) and the IDEX-ISITE initiative CAP 20--25 (ANR-16-IDEX-0001). Byline: Manuel Trotta [manuel.trotta@emse.fr] (*,1,a), Claudia Archetti [archetti@essec.edu] (b), Dominique Feillet [dominique.feillet@mines-stetienne.fr] (c), Alain Quilliot [alain.quilliot@isima.fr] (d)

Keywords ICOs; ICO success; Blockchain; Machine learning; Whitepaper Highlights * We apply machine learning techniques to initial coin offerings (ICOs). * We use machine learning techniques to identify successful ICOs. * We find an increase in forecast accuracy with respect to standard model approaches. * An algorithm-based approach makes the analysis of whitepaper content available to all. * We show that the structure of ICO white papers forecasts success likelihood. Abstract The identification of ventures that are more likely to be successful is a complex task for equity investors, such that a mix of assessment criteria is typically employed. Machine learning (ML) techniques may provide valid support to investors in processing the set of available information. This paper applies ML to initial coin offerings (ICOs), which allows firms to raise blockchain finance through public online offerings. After implementing this novel approach to a sample of 383 ICOs launched between August 2014 and December 2019, we found an increase in forecast accuracy, from 54.3% when using standard Logit models to 72.8% when using ML techniques. Therefore, we contribute to the scientific debate and practice by introducing an algorithm-based approach that makes the analysis of whitepaper content available to individual investors. Importantly, we document that the structure of ICO white papers, a so far neglected dimension, is a significant determinant of the success of ICOs. Author Affiliation: (a) University of Bergamo, Department of Management, Information and Production Engineering, Bergamo, Italy (b) University of Bergamo, Department of Management, Bergamo, Italy * Correspondence to: Via Pasubio 7b, 24044 Dalmine, BG, Italy. Article History: Received 31 August 2021; Revised 20 April 2022; Accepted 9 May 2022 (footnote)[white star] We thank Edoardo Orsi for superb research assistance. Byline: Michele Meoli [michele.meoli@unibg.it] (a,*), Silvio Vismara (b)

Keywords Constrained random assignment; Probabilistic serial mechanism; sd-efficiency; Fairness Abstract This paper generalizes the Probabilistic Serial (PS) mechanism of to matching markets with arbitrary constraints. The constraints are modeled as a set of permissible ex post allocations. A result of independent interest gives a simple geometric characterization of all lotteries over the set of permissible allocations: they are the ones that satisfy a collection of simple and tractable linear inequalities determined by the constraints. The inequalities correspond to the hyperplanes defining a convex polytope that is intuitively constructed from the given set. When a general version of the PS algorithm is executed under these inequalities, the outcome is an efficient and fair lottery over the set of permissible allocations. The method is general, can be applied to both one-sided and two-sided matching markets, and allows for multi-unit demand. Author Affiliation: Department of Economics, University of Melbourne, Australia Article History: Received 8 March 2019; Revised 16 April 2022; Accepted 24 April 2022 (footnote)1 Address: Department of Economics, Level 4 Building 105 (Business and Economics), University of Melbourne VIC 3010, Australia. This paper is based on Chapter 2 of my PhD dissertation and was previously circulated as the second half of a longer manuscript titled 'Short Trading Cycles: Kidney Exchange with Strict Ordinal Preferences.' I have benefited from the comments and suggestions of many people, who have discussed this work with me, as well as the kind attention and feedback of a number of seminar audiences. I am particularly grateful to my dissertation advisor, Haluk Ergin, as well as David Ahn, Haris Aziz, Yuichiro Kamada, Fuhito Kojima, Maciej H. Kotowski, Simon Loertscher, Chris Shannon, M. Utku Ünver, and Steven R. Williams. An associate editor and two anonymous referees helped improve the paper. Jacob Coreno provided excellent research assistance. The research was partly supported by funding received through NSF grant SES-1227707. Byline: Ivan Balbuzanov [ivan.balbuzanov@unimelb.edu.au] (1)