Search

Developed a method based on 0-1 linear programming to stratify an item pool optimally for use in alpha-stratified adaptive testing. Applied the method to a previous item pool from the computerized adaptive test of the Graduate Record Examinations. Results show the new method performs well in practical situations. (SLD)

Discusses how to improve the quality of Internet search systems and introduces the Ghosts Consensus Method which is free from the drawbacks of digital democracy algorithms and is based on linear programming tasks. Highlights include vector space models; determining relevant documents; and enriching query terms. (LRW)

Discussion of the interaction of instructional strategies and learner characteristics focuses on linearity versus nonlinearity, self-regulated learning, and advance organizers in knowledge acquisition in a Web-based hypermedia learning environment. Highlights include results from an analysis of covariance; variables including computer anxiety and prior computer knowledge; and recommendations for further study. (Contains 44 references.) (LRW)

Proposes an algorithm for the assembly of multiple test forms in which the multiple-form problem is reduced to a series of computationally less intensive two-form problems. Illustrates how the method can be implemented using 0-1 linear programming and gives two examples. (SLD)

Proposes a model for constrained computerized adaptive testing in which the information in the test at the trait level (theta) estimate is maximized subject to the number of possible constraints on the content of the test. Test assembly relies on a linear-programming approach. Illustrates the approach through simulation with items from the Law School Admission Test. (SLD)

Discusses problems of diagnosing and repairing infeasible linear-programming models in computerized test assembly. Demonstrates that it is possible to localize the causes of infeasibility, although this is not always easy. (SLD)

Derives a set of linear conditions of item-response functions that guarantees identical observed-score distributions on two test forms. The conditions can be added as constraints to a linear programming model for test assembly. An example illustrates the use of the model for an item pool from the Law School Admissions Test (LSAT). (SLD)

Introduces a new generalization of inner product measures which removes the aesthetic deficiencies in previous research. Discusses linear similarity measures; proves the existence theorem for acceptable ranking functions in the case of a linear measure; and defines asymptotic inner product measures. (AEF)

Validated quantitative models for lean supply chain planning (LSCP) are still scarce in the literature, particularly because conventional push systems have not been widely integrated and tested with pull systems in sustainable and resilient environments in the Industry 4.0 context. Hence the main contribution of this paper is to develop an optimisation model that is able to contribute to the LSCP with the combination of push and pull strategies. Here we present an integrated just-in-time (JIT) production system with material requirement planning (MRP) for a SC that takes a traditional five-level structure based on a mixed-integer linear programming model (MILP) dubbed as LSCP 4.0. The model is able to simultaneously plan the production and inventory of materials and finished goods to satisfy demand from forecasts and firm orders. The selection of alternative suppliers as a proactive measure to face disruptive events is also considered. Furthermore, sustainable practices are included in the objective function for profit maximisation by considering CO2 emissions. This proposal is tested in the footwear sector. The results demonstrate that the combined use of JIT and MRP through a quantitative approach improve performance in leanness, sustainability and resilience by decreasing the bullwhip effect at different SC levels. [ABSTRACT FROM AUTHOR]

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

Increasing energy efficiency in manufacturing has significant environmental and cost benefits. Turning on or off a machine dynamically while considering the production rate requirements can offer substantial energy savings. In this work, we examine the optimal policies to control production and turn on and off a machine that operates in working, idle, off, and warmup modes for the case where demand inter-arrival, production, and warmup times have phase-type distributions. The optimal control problem that minimises the expected costs associated with the energy usage in different energy modes and the inventory and backlog costs is solved using a linear program associated with the underlying Markov Decision Process. We also present a matrix-geometric method to evaluate the steady-state performance of the system under a given threshold control policy. We show that when the inter-arrival time distribution is not exponential, the optimal control policy depends on both the current phase of the inter-arrival time and inventory position. The phase-dependent policy implemented by estimating the current phase based on the time elapsed since the last arrival yields a buffer- and time-based policy to control the energy mode and production. We show that policies that only use the inventory position information can be effective if the control parameters are chosen appropriately. However, the control policies that use both the inventory and time information further improve the performance. [ABSTRACT FROM AUTHOR]

Assembly lines commonly run for dozens of years before being decommissioned. As product families may evolve several times per year by following the needs of sales and marketing, process engineers reconfigure the lines several dozens of times throughout their life cycle. If the line is not flexible enough, these reconfigurations may be costly, and they can lead to poor efficiency. The present work investigates the possibility of designing a line while accounting for product evolution throughout the life cycle of the line. The evolution of the product family is unknown and we consider a robust optimisation approach. We study a mixed-model assembly line, where each station contains a worker/robot and its equipment. The line produces different product models from the same family, and a reconfiguration occurs when a new product model replaces one of the current variants in the product family. Reconfiguration re-arranges resources and equipment pieces, and it can re-assign some tasks. In this study, we formulate a novel Mixed-Integer Linear Programming (MILP) that minimizes the total cost of the initial design and future reconfigurations of the line over some future product family evolution for the worst case. We consider the worst-case among different scenarios that represent possible production requirements of the new product model. An adversarial approach is also developed to solve large-size instances. We perform computational experiments on the benchmark data from the literature. The results show the proposed adversarial approach performs well, and the proposed robust model significantly reduces the design and reconfiguration costs when compared to the classical approach that designs and reconfigures by accounting only for the current product family. [ABSTRACT FROM AUTHOR]

This paper addresses a serial distributed permutation flowshop scheduling problem (SDPFSP) inspired by a printed circuit board assembly process that contains two production stages linked by a transportation stage, where the scheduling problem in each production stage can be seen as a distributed permutation flowshop scheduling problem (DPFSP). A sequence-based mixed-integer linear programming model is established. A solution representation consisting of two components, one component per stage, is presented and a makespan calculation method is given for the representation. Two suites of accelerations based on the insertion neighbourhood are proposed to reduce the computational complexity. A cooperative iterated greedy (CIG) algorithm is developed with two subloops, each of which optimises a component of the solution. A collaboration mechanism is used to conduct the collaboration of the two subloops effectively. Problem-specific operators including the NEH-based heuristics, destruction, reconstruction and three local search procedures, are designed. Extensive computational experiments and statistical analysis verify the validity of the model, the effectiveness of the proposed CIG algorithm and the superiority of the proposed CIG over the existing methods for solving the problem under consideration. [ABSTRACT FROM AUTHOR]

In this paper, a three-echelon supply chain problem under demand uncertainty is considered. The problem is formulated as a multiperiod two-stage stochastic optimisation model. The first stage, consisting of production and replenishment decisions, is integrated with the second stage, which comprises reactive fulfillment decisions, allowing seamless determination as demands are revealed over time. The demand in each period is characterised by an uncertainty set based on the nominal value and demand bounds. We propose a target-based robust optimisation (TRO) approach to determine the most robust planning with respect to a pre-specified cost target. The proposed TRO approach can trade off the total cost (performance) and model feasibility in the presence of demand perturbation (robustness) by fine-tuning the cost target. The robust counterpart is converted to a quadratically constrained linear programming (QCLP) problem, which can be solved by commercial solvers. Numerical experiments demonstrate that the TRO approach can outperform traditional robust optimisation methods in terms of both cost and feasibility against demand uncertainty by enabling precise adjustment of the cost target. Importantly, the TRO approach provides a flexible means to strike a balance between performance and robustness metrics, making it a valuable tool for supply chain planning under uncertain conditions. [ABSTRACT FROM AUTHOR]

The paper presents a discrete-time mixed-integer linear programming (MILP) model for a generalised flexible job-shop scheduling problem as represented by a state-task network. The problem is characterised by reentrant flow, sequence-dependent changeover time, machine downtime, and skilled labour requirements. Two preprocessing procedures are proposed to reduce the size of the MILP model, and represent a major contribution of the research. The procedures reduce the number of assignment variables by exploiting job precedence and workforce qualifications. Machine availability for each task is determined as a function of possible start and end times, given duration, and maintenance schedule. The overall objective is to maximise the number of scheduled tasks while minimising their total finish time. Computational experiments are conducted with real and randomly generated instances. The results show that optimal solutions can be obtained for medium-size problems within a reasonable amount of time, primarily due to the use of the preprocessing procedures. [ABSTRACT FROM AUTHOR]

A solution approach is proposed for the interday problem of assigning chemotherapy sessions at a network of treatment centres with the goal of increasing the cost-efficiency of system-wide capacity use. This network-based scheduling procedure is subject to the condition that both the first and last sessions of a patient's treatment protocol are administered at the same centre the patient is referred to by their oncologist. All intermediate sessions may be administered at other centres. It provides a systematic way of identifying effective multi-appointment scheduling policies that exploit the total capacity of a networked system, allowing patients to be treated at centres other than their home centre. The problem is modelled as a Markov decision process which is then solved approximately using techniques of approximate dynamic programming. The benefits of the approach are evaluated and compared through simulation with the existing manual scheduling procedures at two treatment centres in Santiago, Chile. The results suggest that the approach would obtain a 20% reduction in operating costs for the whole system and cut existing first-session waiting times by half. A key conclusion, however, is that a network-based scheduling procedure brings no real benefits if it is not implemented in conjunction with a proactive assignment policy like the one proposed in this paper. [ABSTRACT FROM AUTHOR]

This work considers an industrial production site partially powered by a decentralised energy system based on intermittent renewable energy sources. Our objective is to simultaneous plan the industrial production and the energy supply in this site so as to minimise the total cost. A new way of modelling this combinatorial optimisation problem is proposed: it relies on the extension of a multi-product single-resource small-bucket lot-sizing model called the proportional lot-sizing and scheduling problem. This extension involves among others sequence-dependent changeover times overlapping multiple periods and energy-related constraints. Our numerical results show that the resulting mixed-integer linear programming model enables to obtain good-quality production and energy supply plans with a computational effort much smaller than the one required by a previously published large-bucket lot-sizing model. [ABSTRACT FROM AUTHOR]

Current studies on scheduling of machines and transporters assume that either a single transporter or an infinite number of homogeneous transporters such as AGVs or mobile robots are available to transport semi-finished jobs, which seems very restrictive in practice. This paper addresses this gap by studying a job-shop scheduling problem that incorporates a limited number of heterogeneous transporters, where the objective is to minimize the makespan. The problem is modelled using mixed-integer linear programming and constraint programming. Different structure-based branch-and-bound algorithms with two lower-bounding strategies are also developed. A comprehensive numerical study evaluates the proposed models and algorithms. The research demonstrates that the adjustment of the proposed MILP model outperforms the existing formulation when applied to the homogeneous case. The study also uncovers interesting practical implications, including the analysis of the impact of different transporter types in the system. It shows that utilizing a fleet of heterogeneous transporters can improve the overall performance of the job shop compared to a relevant homogeneous case. The importance of the study is emphasized by highlighting the negative consequences of disregarding transporters' differences during the scheduling phase. [ABSTRACT FROM AUTHOR]

In this work, we study the multi-product dynamic lot-sizing problem with capacity constraints and batch ordering. This problem arises in short to medium range production scheduling for several products over a finite number of periods to meet known demand. Each period has a capacity for placing orders, and every order for each product must have a fixed quantity, or batch size, though multiple orders can be placed for each product. We define three mixed-integer linear programming (MILP) models and apply Lagrangian relaxation to formulate the corresponding dual problems by relaxing the capacity constraints. The aim is to identify the dual problem that is the easiest to solve and provides the solution with the smallest duality gap. Subgradient optimisation is applied to solve the preferred Lagrangian dual model, which uses one of two heuristics to find good feasible solutions. We also show that the special case, where the batch sizes for all products are the same, can be modeled as a transportation problem. A set of numerical experiments is designed to compare the performance of the Lagrangian relaxation approach with a commercial MILP solver to identify the version of the subgradient algorithm and the MILP model that provide the best solutions. [ABSTRACT FROM AUTHOR]

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

This work extends the energy-efficient job shop scheduling problem with transport resources by considering speed adjustable resources of two types, namely: the machines where the jobs are processed on and the vehicles that transport the jobs around the shop-floor. Therefore, the problem being considered involves determining, simultaneously, the processing speed of each production operation, the sequence of the production operations for each machine, the allocation of the transport tasks to vehicles, the travelling speed of each task for the empty and for the loaded legs, and the sequence of the transport tasks for each vehicle. Among the possible solutions, we are interested in those providing trade-offs between makespan and total energy consumption (Pareto solutions). To that end, we develop and solve a bi-objective mixed-integer linear programming model. In addition, due to problem complexity we also propose a multi-objective biased random key genetic algorithm that simultaneously evolves several populations. The computational experiments performed have show it to be effective and efficient, even in the presence of larger problem instances. Finally, we provide extensive time and energy trade-off analysis (Pareto front) to infer the advantages of considering speed adjustable machines and speed adjustable vehicles and provide general insights for the managers dealing with such a complex problem. [ABSTRACT FROM AUTHOR]

We consider the context of machining systems design where both equipment selection and line balancing decisions have to be taken in order to minimise the total cost of the system. The designed flow line employs multi-positional machines with rotary tables where vertical and horizontal machining modules can be used for the realisation of machining processes. For this challenging optimisation problem in production research, we develop an innovative mathematical model based on a mixed-integer linear programme and a heuristic algorithm for an approximate solution. An extensive numerical experiment is conducted in order to evaluate the performances of the proposed mathematical model and the developed heuristic. The obtained results show that the decision makers can use the elaborated methods for solving efficiently even large-scale industrial problems. [ABSTRACT FROM AUTHOR]

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

Scheduling is an important decision-making problem in production planning and the resulting decisions have a direct impact on reducing waste, including energy and idle capacity. Batch scheduling problems occur in various industries from automotive to food and energy. This paper introduces the parallel p-batch scheduling problem with batch delivery, content-dependent loading/unloading times and energy-aware objective function. The problem has been motivated by a real system used for freezing products in a food processing company. A mixed-integer linear programming model (MILP) has been developed and explained through a numerical example. As it is not practical to solve large-size instances via a mathematical model, the discrete differential evolution algorithm has been improved (iDDE) and hybridised with the genetic algorithm (GA). A release-oriented vector generation procedure and a heuristic batch formation mechanism have been developed to efficiently solve the problem. The performance of the proposed approach (iDDEGA) has been compared with CPLEX, iDDE and GA through a comprehensive computational study. A case study was conducted based on real data collected from the freezing process of the company, which also verified the practical use and advantages of the proposed methodology. [ABSTRACT FROM AUTHOR]

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

Manufacturers experience random environmental fluctuations that influence their supply and demand processes directly. To cope with these environmental fluctuations, they typically utilise operational hedging strategies in terms of pricing, manufacturing, and procurement decisions. We focus on this challenging problem by proposing an analytical model. Specifically, we study an integrated problem of procurement, manufacturing, and pricing strategies for a continuous-review make-to-stock system operating in a randomly fluctuating environment with exponentially distributed processing times. The environmental changes are driven by a continuous-time discrete state-space Markov chain, and they directly affect the system's procurement price, raw material flow rate, and price-sensitive demand rate. We formulate the system as an infinite-horizon Markov decision process with a long-run average profit criterion and show that the optimal procurement and manufacturing strategies are of state-dependent threshold policies. Besides that, we provide several analytical results on the optimal pricing strategies. We introduce a linear programming formulation to numerically obtain the system's optimal decisions. We, particularly, investigate how production rate, holding cost, procurement price and demand variabilities, customers' price sensitivity, and interaction between supply and demand processes affect the system's performance measures through an extensive numerical study. Furthermore, our numerical results demonstrate the potential benefits of using dynamic pricing compared to that of static pricing. In particular, the profit enhancement being achieved with dynamic pricing can reach up to 15%, depending on the problem parameters. [ABSTRACT FROM AUTHOR]

Manufacturing companies strive to identify and manage the effects of unexpected disruptions (risks) on their production processes, which affect their performance and resilience. In this study, we propose a decision framework to capture the impact of interconnected risk sources, on the efficiency of manufacturing companies. The proposed framework utilises a novel mixed-integer linear programming (MILP) model to minimize the time of satisfying the orders while it considers the risk associated with suppliers and manufacturers. The MILP model considers the relationships among (i) material and suppliers and (ii) work centers to measure the propagation of risks throughout the production system. The proposed framework also utilises the Monte Carlo simulation to calculate the associated likelihood of delay and the distribution of the delivery time of orders. To show the complication of the propagation of risk, two distinct scenarios are compared. The first scenario considers zero risks, while the second one assigns probabilistic risk to the suppliers and work centers. The results highlight the magnitude and the complexity of the risk propagation from various interconnected sources through the production system. It also identifies the most vulnerable components of the production system affected more by various types of risk. [ABSTRACT FROM AUTHOR]

The celebrated minimax principle of Yao says that for any Boolean-valued function f with finite domain, there is a distribution µ over the domain of f such that computing f to error against inputs from µ is just as hard as computing f to error on worst-case inputs. Notably, however, the distribution µ depends on the target error level1: the hard distribution which is tight for bounded error might be trivial to solve to small bias, and the hard distribution which is tight for a small bias level might be far from tight for bounded error levels. In this work, we introduce a new type of minimax theorem which can provide a hard distribution µ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, some randomized circuit models, quantum query and communication complexities, approximate polynomial degree, and approximate logrank. We also prove an improved version of Impagliazzo's hardcore lemma. Our proofs rely on two innovations over the classical approach of using Von Neumann's minimax theorem or linear programming duality. First, we use Sion's minimax theorem to prove a minimax theorem for ratios of bilinear functions representing the cost and score of algorithms. Second, we introduce a new way to analyze low-bias randomized algorithms by viewing them as "forecasting algorithms" evaluated by a certain proper scoring rule. The expected score of the forecasting version of a randomized algorithm appears to be a more fine-grained way of analyzing the bias of the algorithm. We show that such expected scores have many elegant mathematical properties--for example, they can be amplified linearly instead of quadratically. We anticipate forecasting algorithms will find use in future work in which a fine-grained analysis of small-bias algorithms is required. [ABSTRACT FROM AUTHOR]

This study reports the test results of a two-stage stochastic linear programming (SLP) model with recourse using a user-friendly generic decision support system (DSS) in a North American steel company. This model has the flexibility to configure multiple material facilities, activities and storage areas in a multi-period and multi-scenario environment. The value of stochastic solution (VSS) with a real-world example has a potential benefit of US$ 24.61 million. Experiments were designed according to the potential joint probability distribution scenarios and the magnitude of demand variability. Overall, 144 SLP optimisation model instances were solved across four industries, namely, steel, aluminium, polymer and pharmaceuticals. The academic contribution of this research is two-fold: first, the potential contribution to profit in a steel company using an SLP model; and second, the optimisation empirical experiments confirm a pattern that the VSS and expected value of perfect information (EVPI) increase with the increase in demand variability. This study has implications for practicing managers seeking business solutions with prescriptive analytics using stochastic optimisation-based DSS. This study will attract more industry attention to business solutions, and the prescriptive analytics discipline will garner more scholarly and industry attention. [ABSTRACT FROM AUTHOR]

In automated manufacturing systems (AMSs), because of unpredictable failures, resources can lose functions such that the deadlock control methods, in existence, are invalidated. In this paper, a robust deadlock control approach is proposed for AMSs with multiple unreliable resources. The considered AMSs modelled by Petri nets (PNs) allow to acquire different types of resources at each processing stage. In order to visualise the fact that resource failures occur in AMSs, recovery subnets are designed for the modelling AMSs to depict the failures and recoveries of resources. Based on a siphon detection method performed by a set of integer linear programming formulations, a control specification is proposed. Control places (monitors) with their control variables are designed for the detected unmarked siphons at a marking to guarantee that they are always marked even if some unreliable resources break down. Iteratively, all unmarked siphons are detected and controlled. Therefore, a robust deadlock supervisor is synthesised to ensure the controlled system's liveness no matter there exist resource failures or not. The theoretical analyses and proof are given to verify the correctness of the proposed method. Finally, the comparative studies are presented to expound the proposed method's effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

This paper studies the supplier selection and order allocation (SS&OA) problem, where risks include a series of disruption scenarios with uncertain probability of occurrence. It is a challenge for industry decision-makers to balance the average cost and the level of risk under the ambiguity set for probabilities. To address this challenge, a two-stage distributionally robust (DR) Mean-CVaR model is presented for the SS&OA problem. A procedure is developed for constructing the ambiguity set, and Polyhedral and Box ambiguity sets are constructed to characterise the uncertain probabilities. The worst-case Mean-CVaR criterion is employed for the second-stage cost within the ambiguity set to trade off the expected cost and CVaR value. Three measures are incorporated to increase the resilience of the supply chain. The proposed robust model is reformulated into two mixed-integer linear programming models. A real case of the Huawei cell phone manufacturer is used to illustrate the validity of the proposed approach in numerical settings. Experimental results show that the new optimising approach can provide a robust SS&OA solution to immunise against the influence caused by uncertain probabilities. By comparative analyses, some management insights are obtained for industry decision-makers. [ABSTRACT FROM AUTHOR]