Search

In modern manufacturing and service industries, urgent orders and service tasks are common, and the speed of handling such urgent tasks is an important indicator of production and service efficiency. In this study, we consider scheduling jobs on two parallel machines with the random arrival of an emergency job. The objective is to minimise the makespan, subject to a given maximum waiting time of the emergency job. We first show that the worst-case ratio of the existing algorithm LPT $ _l $ l -SPT $ _{m-l} $ m − l is at least 3/2 when m = 2. We then analyse some properties of the optimal schedule and derive lower bounds on the optimal makespan. Finally, we present an improved approximation algorithm with a tight worst-case ratio of 4/3. We also provide numerical results showing that our proposed algorithm outperforms algorithm LPT $ _l $ l -SPT $ _{m-l} $ m − l . [ABSTRACT FROM AUTHOR]

This paper studies a two-agent scheduling problem on mixed batch machines in parallel. A mixed batch machine can process several jobs simultaneously as a batch, as long as the number of jobs in the batch does not exceed the machine capacity. The processing time of a mixed batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective is to minimise the weighted sum of two agents' makespans. We present four approximation algorithms based on two strategies: the machine-centric strategy and the agent-centric strategy. For each strategy, a full batch longest processing time (FBLPT) rule and a longest processing time greedy (LPTG) rule are used. We conduct theoretical analyses based on the worst-case performance ratio to provide the provable guarantees on the performances of the algorithms, and simulation analyses based on randomly generated instances to evaluate the average performances of the algorithms. Furthermore, we verify the consistency between the theoretical and simulation results. The algorithms using agent-centric strategy perform better than ones using machine-centric strategy. Finally, we provide managerial insights for the problem by analysing the technological parameters of batches, importance of agents, and demand seasonality. [ABSTRACT FROM AUTHOR]

We consider parallel-machine scheduling with identical machine resource capacity limits and DeJong's learning effect. Each job has a resource consumption requirement and a normal processing time. The actual processing time of a job is a function of its normal processing time, subject to DeJong's learning effect, while the resource consumption of a job is a function of its actual processing time. Each machine has the same resource capacity limit. The objective is to maximise the minimum machine load. Considering three resource consumption functions, namely, linear, concave, and convex, we show that all three scheduling models are NP-hard and propose two approximation algorithms for the models and analyse their worst-case ratios. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a double Roman dominating function (DRDF) is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f (v) = 0 , then vertex v must have at least two neighbours assigned 2 under f or at least one neighbour u with f (u) = 3 , and if f (v) = 1 , then vertex v must have at least one neighbour u with f (u) ≥ 2. In this paper, we consider the double Roman domination problem, which is an optimization problem of finding the DRDF f such that ∑ v ∈ V f (v) is minimum. We propose five integer linear programming (ILP) formulations and one mixed integer linear programming formulation with polynomial number of constraints for this problem. Some additional valid inequalities and bounds are also proposed for some of these formulations. Further, we prove that the first four models indeed solve the double Roman domination problem, and the last two models are equivalent to the others regardless of the variable relaxation or usage of a smaller number of constraints and variables. Additionally, we use one ILP formulation to give an H (2 (Δ + 1)) -approximation algorithm. All proposed formulations and approximation algorithm are evaluated on randomly generated graphs to compare the performance. [ABSTRACT FROM AUTHOR]

We consider the following optimisation problem that we encountered during the consolidation process of trains in a container transhipment terminal as well as in the intermediate storage of containers in sea ports in order to accelerate the loading and unloading of the vessels. There arenordered pairs of points in them-dimensional metric space:. The problem is to find a permutationof numbersminimising the functionwhereis the metric of the space. The problem can be considered as a special case of the asymmetric travelling salesman problem. As for Euclidean, Manhattan and Chebyshev metric the problem is NP-hard (as a generalisation of the well-known TSP problem) we propose the simple approximation algorithm with the approximation guarantee equal to 3. The approximation guarantee is tight as will be shown by a sequence of instances for which the approximation ratio converges to 3. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of vector scheduling with rejection on two identical parallel machines, where the objective is to minimize the sum of maximum load over all dimensions and machines and the total penalty cost. We present a 3-approximation algorithm and a 2.54-approximation algorithm based randomized rounding for the general case. When the number of dimensions is fixed, we design a fully polynomial time approximation scheme based on dynamic programming. Finally, we design an online algorithm with competitive ratio 1.62d, where d is the number of dimensions. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of scheduling a set of jobs having only two possible processing times on a set of unrelated parallel machines. This problem is a generalisation of the much more common problem of scheduling equal-length jobs on identical machines. Such a situation may occur in the production of two different types of products. First, we show that an earlier open problem of scheduling jobs with two possible processing times and on unrelated machines with the objective to minimise the makespan can be polynomially solved by an algorithm consisting of two phases. A slight modification of this algorithm yields an absolute worst-case error of for the case of two arbitrary processing times and ,. Thus, for practical problems of a large size with two types of products and two possible processing times, the approximation algorithm generates schedules very close to an optimal one. [ABSTRACT FROM AUTHOR]

The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature. [ABSTRACT FROM PUBLISHER]

This article considers a new variation of the online interval scheduling problem, which consists of scheduling C-benevolent jobs on multiple heterogeneous machines with different positive weights. The reward for completing a job assigned to a machine is given by the product of the job value and the machine weight. The objective of this scheduling problem is to maximize the total reward for completed jobs. Two classes of approximation algorithms are analyzed, Cooperative Greedy algorithms and Prioritized Greedy algorithms, with competitive ratios provided. We show that when the weight ratios between machines are small, the Cooperative Greedy algorithm outperforms the Prioritized Greedy algorithm. As the weight ratios increase, the Prioritized Greedy algorithm outperforms the Cooperative Greedy algorithm. Moreover, as the weight ratios approach infinity, the competitive ratio of the Prioritized Greedy algorithm approaches four. We also provide a lower bound of 3/2 and 9/7 for the competitive ratio of any deterministic algorithm for scheduling C-benevolent jobs on two and three machines with arbitrary weights, respectively. [ABSTRACT FROM AUTHOR]

This article addresses permutation flowshop scheduling problems with simple linear deterioration. The objectives are to minimize logarithm of the makespan, total logarithm of the completion time, total weighted logarithm of the completion time, and the sum of the quadratic job logarithms of the completion times. Approximation algorithms and their worst-case bounds are presented and analysed. Branch-and-bound algorithms are also proposed to solve the problems optimally. Computational experiments are performed to illustrate the algorithms. [ABSTRACT FROM AUTHOR]

Observational or nonrandomized studies of treatment effects are often constructed with the aid of polynomial-time algorithms that optimally form matched treatment-control pairs or matched sets. Because each observational comparison may potentially be affected by bias, investigators often reinforce a single comparison with an additional comparison that is unlikely to be affected by the same biases, for instance using multiple control groups or evidence factors or control + instrument designs. Use of two comparisons affected by different biases may detect bias if the two comparisons disagree, or may show that two comparisons with different weakness concur in their conclusions. Even this simplest addition—a second comparison—creates design problems without polynomial-time solutions. Faced with a problem that no polynomial-time algorithm can solve, a so-called approximation algorithm is a type of compromise: it provides a solution in polynomial time that is provably not much worse than the unattainable optimal solution. Building upon existing techniques for related problems in operations research, we develop an approximation algorithm for minimum distance matching with near-fine balance for three comparison groups. This algorithm is a practical approach to most observational designs that add a second comparison. The method is applied to an observational study of the effects of side airbags on injury severity in the U.S. Fatality Analysis Reporting System. For many car makes and models, side airbags were initially unavailable, then later available as optional equipment for an additional fee, then still later provided as standard equipment. Within sets matched for make and model of car, for safety belt use, for direction of impact, and other covariates, we compare crashes in these three periods, where each comparison has different limitations. The method is implemented in the R package approxmatch, whose example reproduces some of the calculations. for this article are available online. [ABSTRACT FROM AUTHOR]

The capacitated unit covering problem is a generalization of the bin packing and the unit covering problems. In its one-dimensional case, there arenweighted points on a line and we want to partition them into a minimum number of sets such that (i) the total weight of points in each set is no more than one and (ii) the points in each set can be covered by a unit-length interval. The problem is not approximable within a factor better than 1.5 unless P = NP. We analyse a generalization of the first-fit algorithm for this problem, which runs inO(nlogn) time, and prove that when no point has weight more than, its approximation ratio is exactly ≈ 1.667. [ABSTRACT FROM AUTHOR]

In this paper, the authors study a class of supply chain scheduling problems. The manufacturer has batch-processing machines with limited capacity and provides products for the customers. The products are in different sizes which are ordered by the customer and when processed, the products are divided into batches given that the total size of a batch does not exceed the machine capacity. After the completion of products, they are delivered to customers by vehicles of the manufacturer. The authors investigate two classes of problems where the manufacturer has single customer and multiple customers, respectively. In each class of problems, two machine configurations are considered including single machine and identical parallel machines. The authors analyse the computational complexity of the problems and present integer programming models. Then the authors propose polynomial time algorithms using approximation algorithms and dynamic programming. For each algorithm, the time complexity and the performance guarantee are analysed. [ABSTRACT FROM PUBLISHER]

In this article, we present a primal-dual 3-approximation algorithm for the stochastic priority facility location problem. Combined with greedy augmentation procedure, such performance factor is further improved to 1.8526. [ABSTRACT FROM PUBLISHER]

In this article, the job shop scheduling problem with two batch-processing machines is considered. The machines have limited capacity and the jobs have non-identical job sizes. The jobs are processed in batches and the total size of each batch cannot exceed the machine capacity. The processing times of a job on the two machines are proportional. We show the problem of minimising makespan is NP-hard in the strong sense. Then we provide an approximation algorithm with worst-case ratio no more than 4, and the running time of the algorithm is O(n log n). Finally, the performance of the proposed algorithm is tested by different levels of instances. Computational results demonstrate the effectiveness of the algorithm for all the instances. [ABSTRACT FROM PUBLISHER]