Optimal semi-online algorithm for scheduling with rejection on two uniform machines

In this paper we consider a semi-online scheduling problem with rejection on two uniform machines with speed 1 and s≥1, respectively. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. Further, two rejection strategies are permitted thus an algorithm can propose two different schemes, from which the better solution is chosen. For the above version, we present an optimal semi-online algorithm H that achieves a competitive ratio ρ _H (s) as a piecewise function in terms of the speed ratio s.     

A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times

We consider a single batch machine on-line scheduling problem with delivery times. In this paper on-line means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J _j , its processing time and delivery time are denoted by p _j and q _j , respectively. We consider two restricted models: (1) the jobs have small delivery times, i.e., for each job J _j , q _j ≤p _j ; (2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J _i and J _j , p _i >p _j implies q _i ≥q _j . We provide an on-line algorithm with competitive ratio for both problems, and the results are the best possible. Project supported by NSFC (10671183).     

An almost four-approximation algorithm for maximum weight triangulation

We consider the following planar maximum weight triangulation (MAT) problem: given a set of n points in the plane, find a triangulation such that the total length of edges in triangulation is maximized. We prove an $\Omega(\sqrt{n})$ lower bound on the approximation factor for several heuristics: maximum greedy triangulation, maximum greedy spanning tree triangulation and maximum spanning tree triangulation. We then propose the Spoke Triangulation algorithm, which approximates the maximum weight triangulation for points in general position within a factor of almost four in O(nlog?n) time. The proof is simpler than the previous work. We also prove that Spoke Triangulation approximates the maximum weight triangulation of a convex polygon within a factor of two.     

An optimal run-mode scheduling for oil refinery production–a case study on Taiwan CPC Corporation

The refinery industries have been going through very difficult time from fierce competition and high price of crude oil. To increase compatibility, it is essential to increase efficiency in the inventory, production and transportation. Refineries start generating revenues while their products are sold in the market. This article examines the possible costs of additional inventories and recurrent times of refineries derived from early or late shipment in a continuous production system. Then, based on the developed mathematical programming model, an optimal production structure with the minimum total cost of production, inventory and start-up is proposed. Tolerance analysis is conducted to cope with uncertain environment. A case study on applying the proposed model to perform scenario analysis for CPC Corporation, Taiwan is demonstrated. The results show that the developed model is able to provide useful information towards developing cost-effective oil refinery strategies.     

An effective algorithm for obtaining the whole set of minimal cost pairs of disjoint paths with dual arc costs

In telecommunication networks design the problem of obtaining optimal (arc or node) disjoint paths, for increasing network reliability, is extremely important. The problem of calculating k _c disjoint paths from s to t (two distinct nodes), in a network with k _c different (arbitrary) costs on every arc such that the total cost of the paths is minimised, is NP-complete even for k _c =2. When k _c =2 these networks are usually designated as dual arc cost networks.     

Semi-online scheduling on two uniform machines with the known largest size

This paper investigates semi-online scheduling on two uniform machines with the known largest size. Denote by s _j the speed of each machine, j=1,2. Assume 0<s ₁≤s ₂, and let s=s ₂/s ₁ be the speed ratio. First, for the speed ratio \(s\in [1,\sqrt{2}]\), we present an optimal semi-online algorithm \(\mathcal{LSMP}\) with the competitive ratio \(\mathrm{max}\{\frac {2(s+1)}{2s+1},s\}\). Second, we present a semi-online algorithm \(\mathcal{HSMP}\). And for \(s\in(\sqrt{2},1+\sqrt{3})\), the competitive ratio of \(\mathcal{HSMP}\) is strictly smaller than that of the online algorithm \(\mathcal{LS}\). Finally, for the speed ratio s≥s ^*≈3.715, we show that the known largest size cannot help us to design a semi-online algorithm with the competitive ratio strictly smaller than that of \(\mathcal{LS}\). Moreover, we show a lower bound for \(s\in(\sqrt{2},s^{*})\).     

A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem

This paper addresses a constrained two-dimensional (2D), non-guillotine restricted, packing problem, where a fixed set of small rectangles has to be placed into a larger stock rectangle so as to maximize the value of the rectangles packed. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose also a new fitness function to drive the optimization. The approach is tested on a set of instances taken from the literature and compared with other approaches. The experimental results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

An extension of the relaxation algorithm for solving a special case of capacitated arc routing problems

In this paper, we propose an exact method for solving a special integer program associated with the classical capacitated arc routing problems (CARPs) called split demand arc routing problems (SDARP). This method is developed in the context of monotropic programming theory and bases a promising foundation for developing specialized algorithms in order to solve general integer programming problems. In particular, the proposed algorithm generalizes the relaxation algorithm developed by Tseng and Bertsekas (Math. Oper. Res. 12(4):569–596, 1987) for solving linear programming problems. This method can also be viewed as an alternative for the subgradient method for solving Lagrangian relaxed problems. Computational experiments show its high potential in terms of efficiency and goodness of solutions on standard test problems.     

A hybrid beam search looking-ahead algorithm for the circular packing problem

In this paper, we study the circular packing problem. Its objective is to pack a set of n circular pieces into a rectangular plate R of fixed dimensions L×W. Each piece’s type i, i=1,…,m, is characterized by its radius r _i and its demand b _i . The objective is to determine the packing pattern corresponding to the minimum unused area of R for the circular pieces placed. This problem is solved by using a hybrid algorithm that adopts beam search and a looking-ahead strategy. A node at a level ℓ of the beam-search tree contains a partial solution corresponding to the circles already placed inside R. Each node is then evaluated using a looking-ahead strategy, based on the minimum local-distance heuristic, by computing the corresponding complete solution. The nodes leading to the best solutions at level ℓ are then chosen for branching. A multi-start strategy is also considered in order to diversify the search space. The computational results show, on a set of benchmark instances, the effectiveness of the proposed algorithm.     

Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times

We study the problem of semi-online scheduling on 2 machines under a grade of service (GoS). GoS means that some jobs have to be processed by some machines to be guaranteed a high quality. The problem is online in the sense that jobs are presented one by one, and each job shall be assigned to a time slot on its arrival. Assume that the processing time p _i of every job J _i is bounded by an interval [a,α a], where a>0 and α>1 are two constant numbers. By knowing the bound of jobs’ processing times, we denote it by semi-online problem. We deal with two semi-online problems.     

Lower bounds and a tabu search algorithm for the minimum deficiency problem

An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S _v (G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D _v (G,c) the minimum number of integers which must be added to S _v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ _v∈V D _v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.     

Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan

We consider the scheduling of n family jobs with release dates on m identical parallel batching machines. Each batching machine can process up to b jobs simultaneously as a batch. In the bounded model, b<n, and in the unbounded model, b=∞. Jobs from different families cannot be placed in the same batch. The objective is to minimize the maximum completion time (makespan). When the number of families is a constant, for both bounded model and unbounded model, we present polynomial-time approximation schemes (PTAS).     

A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

In the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ??V, a set of demands (i.e., clients) $\mathcal{D}\subseteq VIn the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ℱ⊆V, a set of demands (i.e., clients) D í V\mathcal{D}\subseteq V , and a parameter M≥1. Each facility i has a nonnegative opening cost f _i and each client j has d _j units of demand. Our objective is to open some facilities, say F⊆ℱ, assign each demand j to some open facility i(j)∈F and connect all open facilities using a Steiner tree T such that the total cost, which is ?_{i ? F}f_i+?_{j ? D}d_jc_i(j)j+M?_{e ? T}c_e\sum_{i\in F}f_{i}+\sum_{j\in \mathcal{D}}d_{j}c_{i(j)j}+M\sum_{e\in T}c_{e} , is minimized. We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation algorithm given by Swamy and Kumar (Algorithmica 40:245–269, 2004).     

Complexity analysis for maximum flow problems with arc reversals

We provide a comprehensive study on network flow problems with arc reversal capabilities. The problem is to identify the arcs to be reversed in order to achieve a maximum flow from source(s) to sink(s). The problem finds its applications in emergency transportation management, where the lanes of a road network could be reversed to enable flow in the opposite direction. We study several network flow problems with the arc reversal capability and discuss their complexity. More specifically, we discuss the polynomial time algorithms for the maximum dynamic flow problem with arc reversal capability having a single source and a single sink, and for the maximum (static) flow problem. The presented algorithms are based on graph transformations and reductions to polynomially solvable flow problems. In addition, we show that the quickest transshipment problem with arc reversal capability and the problem of minimizing the total cost resulting from arc switching costs are NP\mathcal{NP} -hard.     

Exact closed-form solutions for “optimal inventory model for items with imperfect quality and shortage backordering”

Wee et al. [Optimal inventory model for items with imperfect quality and shortage backordering. Omega 2007;35(1):7–11] recently contributed an optimal inventory model for items with imperfect quality and shortage backordering. This article revisits their study and applies the well-known renewal-reward theorem to obtain a new expected net profit per unit time. We derive the exact closed-form solutions to determine the optimal lot size, backordering quantity and maximum expected net profit per unit time, specifically without differential calculus. We also solve the same model algebraically from another direction, which has been mentioned, but the process has not been finished yet. The problem parameter effects upon the optimal solutions are examined analytically and numerically.     

Keeping partners together: algorithmic results for the hospitals/residents problem with couples

The Hospitals/Residents problem with Couples (HRC) is a generalisation of the classical Hospitals/Residents problem (HR) that is important in practical applications because it models the case where couples submit joint preference lists over pairs of hospitals (h _i ,h _j ). We consider a natural restriction of HRC in which the members of a couple have individual preference lists over hospitals, and the joint preference list of the couple is consistent with these individual lists in a precise sense. We give an appropriate stability definition and show that, in this context, the problem of deciding whether a stable matching exists is NP-complete, even if each resident’s preference list has length at most 3 and each hospital has capacity at most 2. However, with respect to classical (Gale-Shapley) stability, we give a linear-time algorithm to find a stable matching or report that none exists, regardless of the preference list lengths or the hospital capacities. Finally, for an alternative formulation of our restriction of HRC, which we call the Hospitals/Residents problem with Sizes (HRS), we give a linear-time algorithm that always finds a stable matching for the case that hospital preference lists are of length at most 2, and where hospital capacities can be arbitrary.     

(1+ε)-competitive algorithm for online OVSF code assignment with resource augmentation

This paper studies the online Orthogonal Variable Spreading Factor (OVSF) code assignment problem with resource augmentation introduced by Erlebach et al. (in STACS 2004. LNCS, vol. 2996, pp. 270–281, 2004). We propose a (1+1/α)-competitive algorithm with help of (1+?α?)lg^? h trees for the height h of the OVSF code tree and any α≥1. In other words, it is a (1+ε)-competitive algorithm with help of (1+?1/ε?)lg^? h trees for any constant 0<ε≤1. In the case of α=1 (or ε=1), we obtain a 2-competitive algorithm with 2lg^? h trees, which substantially improves the previous resource of 3h/8+2 trees shown by Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358–367, 2009). In another aspect, if it is not necessary to bound the incurred cost for individual requests to a constant, an amortized (4/3+δ)-competitive algorithm with (11/4+4/(3δ)) trees for any 0<δ≤4/3 is also designed in Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358–367, 2009). The algorithm in this paper gives us a new trade-off between the competitive ratio and the resource augmentation when α≥3 (or ε≤1/3), although the incurred cost for individual requests is bounded to a constant.     

Optimal on-line algorithms for one batch machine with grouped processing times

In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1+φ)p], where p>0 and \(\phi=(\sqrt{5}-1)/2\). Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio \((\sqrt{5}+1)/2\) are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio \((\sqrt{5}+1)/2\). The two class of algorithms are optimal for the problems studied here.     

Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling

We consider semi on-line scheduling on two uniform machines. The speed of the slow machine is normalized to 1 while the speed of the fast machine is assumed to be s≥1. Jobs of size J ₁,J ₂,… arrive one at a time, and each J _i (i≥1) has to be assigned to one of the machines before J _i+1 arrives. The assignment cannot be changed later. The processing time of the ith job is J _i on the slow machine and J _i /s on the fast one. The objective is to minimize the makespan. We study both the case where the only information known in advance is the total size ∑_i≥1 J _i of the jobs and the case where the only information known in advance is the optimum makespan. For each of these two cases, we almost completely determine the best possible competitive ratio of semi on-line algorithms compared to the off-line optimum, as a function of s in the range \(1\le s<\frac{1+\sqrt{17}}{4}\approx1.2808\), except for a very short subinterval around s=1.08. We also prove that the best competitive ratio achievable for known optimum is at least as good as the one for known sum, even for any number of uniform machines of any speeds.     

Interactive bacterial foraging optimization algorithm for aircraft base maintenance technician scheduling; [基于交互式细菌觅食优化算法的 飞机基地维修人员调度]

In recent years, with the reform of industry segmentation, more and more airlines outsource maintenance tasks to aircraft base maintenance service providers to reduce operational costs. As the most important part of aircraft base maintenance service providers, the scheduling scheme of the aircraft maintenance technicians determines whether the maintenance service could be completed on time. However, aircraft maintenance technicians often face a tense and difficult working environment. The shortage of the rest time and huge psychological pressure decrease working efficiency and quality, which is not conducive to the timely delivery of maintenance orders. In addition, at present, the complex and distributed maintenance technician scheduling mainly depends on the project managers according to personal experience. Therefore, for a maintenance technician scheduling scheme, both efficiency and fairness cannot be guaranteed. To solve the above problems, this paper studies the distributed aircraft base maintenance technician scheduling problem considering the fairness of workload distribution and designs an interactive bacterial foraging optimization algorithm according to the characteristics of the considered NP-hard problem. First, different from the traditional aircraft maintenance technician scheduling model, this paper distinguishes the maintenance tasks on different aircrafts and considers the maintenance task-technician assignment problem from four dimensions, including aircraft, maintenance task, maintenance technician, and maintenance shift. Instead of simplifying the maintenance tasks of all aircrafts into a single task sequence, the task-technician assignment for maintenance aircrafts in the hangar is abstracted as a distributed maintenance technician scheduling problem. Moreover, since multiple aircrafts in the hangar need to share the same group of maintenance technicians at the same time, the distributed technician scheduling is carried out by accumulating the maintenance time of each aircraft to ensure that maintenance tasks on multiple aircrafts can be performed synchronously. Based on the above analysis, both optimization objective and constraints are designed from the aspects of on-time delivery of the whole maintenance work, cost control, and reasonable and fair workload distribution, so as to make the scheduling scheme of maintenance technicians more specific and meet the requirements of actual maintenance scenarios. Then, according to the distributed, nonlinear, discrete, and multi-dimensional characteristics of the considered NP-hard problem, this paper proposes the interactive bacterial foraging optimization (IBFO) algorithm based on bacterial foraging optimization (BFO) algorithm to obtain excellent characteristics, such as strong adaptability to the environment and outstanding parallelism. Compared with BFO, IBFO improves both structure and information interaction mode. In terms of algorithm structure, the three-tier nested loop in the original BFO is disassembled. Chemotaxis, replication, and dispersion are regarded as three parallel operations. In terms of information interaction mode, the bacterial swarm is divided into multiple sub-swarms. By designing the information interaction mode of bacterial individuals among each sub swarm, the effective communication and learning of the whole group are realized, including information interaction within its historical position and information interaction with other individuals. Through the above improvements, bacterial individuals can obtain information from more individuals to enhance the overall optimization ability and search efficiency. Next, this paper depicts a unique encoding mechanism to connect the IBFO algorithm with the built model, and four groups of comparative experiments are designed to verify the effectiveness of IBFO in solving the above model. The BFO, swarm intelligence bacterial foraging optimization (SiBFO), bacterial colony optimization (BCO), particle swarm optimization (PSO), comprehensive learning particle swarm optimizer (CLPSO), and genetic algorithm (GA) are chosen as comparison algorithms. The experimental results show that compared with the other six algorithms, the interactive bacterial foraging optimization algorithm owns stronger search ability, higher search accuracy, better robustness as well as convergence performance. Additionally, with the expansion of the problem scales and the prominence of the distributed mode, compared with other algorithms, IBFO has more obvious advantages in cost-saving and fairness improvement than the other listed intelligent algorithms. In summary, different from the previous simplified aircraft base maintenance technician scheduling model, this paper constructs a distributed one based on the maintenance technician′s concern about the fairness of workload distribution and the aircraft base maintenance service provider′s consideration of cost control, which is more in line with the actual scenario requirements of the synchronous execution of maintenance tasks on multiple aircrafts in the maintenance hangar. This paper also devises an interactive bacterial foraging optimization algorithm suitable for solving the above model. The improvement of the algorithm structure, the division within the swarm, and the communication and learning mechanism between different sub-swarms enhance the optimizing performance and solving ability of the algorithm. The proposed method not only provides a more reasonable and humanized technician scheduling scheme for aircraft maintenance base service providers but also effectively solves the problems of time-consuming, poor fairness, and laborious manual scheduling and enhances the operational efficiency of aircraft maintenance bases. © (2023). All Rights Reserved.