Tabu search for discrete–continuous scheduling problems with heuristic continuous resource allocation

Problems of scheduling non-preemptable, independent jobs on parallel identical machines under an additional continuous renewable resource to minimize the makespan are considered. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. The processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. A heuristic procedure for allocating the continuous resource is used. The tabu search metaheuristic to solve the considered problem is presented. The results produced by tabu search are compared with optimal solutions for small instances, as well as with the results generated by simple search methods – multi-start iterative improvement and random sampling for larger instances.     

On a methodology for discrete–continuous scheduling

Discrete–continuous problems of scheduling nonpreemptable jobs on parallel machines are considered. The problems arise e.g. when jobs are assigned to multiple parallel processors driven by a common electric, hydraulic or pneumatic power source. Existing models have assumed job processing rates as a function of the number of jobs currently being processed, or equivalently the number of machines currently in operation. In this paper a more general model is proposed in which processing rates of a job assigned to a machine depend on the amount of a continuous, i.e. continuously divisible resource (e.g. power) allotted to this job at a time. Thus the problem consists of two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to allocate the continuous resource among jobs already sequenced. We provide a comprehensive analysis of the problem. This includes properties of optimal schedules, efficiently (in particular analytically) solvable cases, formulations of the possibly simplest mathematical programming problems for finding optimal schedules in the general case, heuristics and the worst-case analysis. Although our objective function in this paper is to minimize makespan of a set of independent jobs, the presented methodology can be applied to other criteria, precedence-related jobs, and many resource types (apart from, or instead of machines).     

Tabu list management methods for a discrete–continuous scheduling problem

A problem of scheduling jobs on parallel, identical machines under an additional continuous resource to minimize the makespan is considered. Jobs are non-preemtable and independent and all are available at the start of the process. The total amount of the continuous resource available at a time is limited and the resource is a renewable one. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. Processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimizes the makespan. The tabu search (TS) metaheuristic is presented to attack the problem. Three different tabu list management methods: the tabu navigation method (TNM), the cancellation sequence method (CSM) and the reverse elimination method (REM) are discussed and examined. A computational experiment is described and the results obtained for the methods tested are compared to optimal solutions. A few conclusions and final remarks are presented.     

Resource level minimization in the discrete–continuous scheduling

A discrete–continuous problem of non-preemptive task scheduling on identical parallel processors is considered. Tasks are described by means of a dynamic model, in which the speed of the task performance depends on the amount of a single continuously divisible renewable resource allotted to this task over time. An upper bound on the completion time of all the tasks is given. The criterion is to minimize the maximum resource consumption at each time instant, i.e., the resource level. This problem has been observed in many industrial applications, where a continuously divisible resource such as gas, fuel, electric, hydraulic or pneumatic power, etc., has to be distributed among the processing units over time, and it affects their productivity. The problem consists of two interrelated subproblems: task sequencing on processors (discrete subproblem) and resource allocation among the tasks (continuous subproblem). An optimal resource allocation algorithm for a given sequence of tasks is presented and computationally tested. Furthermore, approximation algorithms are proposed, and their theoretical and experimental worst-case performances are analyzed. Computer experiments confirmed the efficiency of all the algorithms.     

Optimal discrete and continuous mono‐implicit Runge–Kutta schemes for BVODEs

Recent investigations of discretization schemes for the efficient numerical solution of boundary value ordinary differential equations (BVODEs) have focused on a subclass of the well‐known implicit Runge–Kutta (RK) schemes, called mono‐implicit RK (MIRK) schemes, which have been employed in two software packages for the numerical solution of BVODEs, called TWPBVP and MIRKDC. The latter package also employs continuous MIRK (CMIRK) schemes to provide C ¹ continuous approximate solutions. The particular schemes implemented in these codes come, in general, from multi‐parameter families and, in some cases, do not represent optimal choices from these families. In this paper, several optimization criteria are identified and applied in the derivation of optimal MIRK and CMIRK schemes for orders 1–6. In some cases the schemes obtained result from the analysis of existent multi‐parameter families; in other cases new families are derived from which specific optimal schemes are then obtained. New MIRK and CMIRK schemes are presented which are superior to those currently available. Numerical examples are provided to demonstrate the practical improvements that can be obtained by employing the optimal schemes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Green’s functions for discrete mTH-order problems*

We investigate an mth-order discrete problem with additional conditions, described by m linearly independent linear functionals. We find the solution to this problem and present a formula and the existence condition of Green??s function if the general solution of a homogeneous equation is known. We obtain a relation between Green??s functions of two nonhomogeneous problems. It allows us to find Green??s function for the same equation, but with different additional conditions. The obtained results are applied to problems with nonlocal boundary conditions.     

Fixed–charge continuous knapsack problems and pseudogreedy solutions

Received February 12, 1993 / Revised version received February 6, 1998 Published online February 25, 1999     

Nonlinear discrete Sturm–Liouville problems with global boundary conditions

This paper is devoted to the study of nonlinear difference equations subject to global nonlinear boundary conditions. We provide sufficient conditions for the existence of solutions based on properties of the nonlinearities and the eigenvalues of an associated linear Sturm–Liouville problem.     

An Eulerian–Lagrangian mixed discrete least squares meshfree method for incompressible multiphase flow problems

Mixed discrete least squares meshfree (MDLSM) method has been developed as a truly meshfree method and successfully used to solve single-phase flow problems. In the MDLSM, a residual functional is minimized in terms of the nodal unknown parameters leading to a set of positive-definite system of algebraic equations. The functional is defined using a least square summation of the residual of the governing partial differential equations and its boundary conditions at all nodal points discretizing the computational domain. Unlike the discrete least squares meshfree (DLSM) which uses an irreducible form of the governing equations, the MDLSM uses a mixed form of the original governing equations allowing for direct calculation of the gradients leading to more accurate computational results. In this study, an Eulerian–Lagrangian MDLSM method is proposed to solve incompressible multiphase flow problems. In the Eulerian step, the MDLSM method is used to solve the governing phase averaged Navier–Stokes equations discretized at fixed nodal points to get the velocity and pressure fields. A Lagrangian based approach is then used to track different flow phases indexed by a set of marker points. The velocities of marker points are calculated by interpolating the velocity of fixed nodal points using a kernel approximation, which are then used to move the marker points as Lagrangian particles to track phases. To avoid unphysical clustering and dispersing of the marker points, as a common drawback of Lagrangian point tracking methods, a new approach is proposed to smooth the distribution of marker points. The hybrid Eulerian and Lagrangian characteristics of the approach used here provides clear advantages for the proposed method. Since the nodal points are static on the Eulerian step, the time-consuming moving least squares (MLS) approximation is implemented only once making the proposed method more efficient than corresponding fully Lagrangian methods. Furthermore, phases can be simply tracked using the Lagrangian phase tracking procedure. Efficiency of the proposed MDLSM multiphase method is evaluated using several benchmark problems and the results are presented and discussed. The results verify the efficiency and accuracy of the proposed method for solving multiphase flow problems.     

Low noise regimes for ℓ regularization : continuous and discrete settings

We focus on support recovery for signal deconvolution with sparsity assumption. We adopt the continuous setting defined by several recent works and we try to reconstruct a sum of Dirac masses from its low frequencies (possibly perturbed by some noise), by using a total variation prior for Radon measures (i.e. the generalization to measures of the ℓ¹ norm). We show that, under a non degenerate source condition, there exists a small noise regime in which the model recovers exactly the same number of spikes as the original signal, and the spikes converge to those of the original signal as the noise vanishes. This continuous setting, by allowing the spikes to “move”, provides robust support recovery for signals composed of well separated spikes. In a discrete setting, where the spikes are reconstructed on a grid, similar low noise regimes which guarantee the exact recovery of the support also exist (see [3]). Yet, this property only concerns a small class of signals. Considering the asymptotics of the discrete problems as the size of the grid tends to zero, we show that the support of the original signal cannot be stable on thin grids, and that the discrete models actually reconstruct pairs of spikes near each original spike. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A symmetric generalization of Sturm–Liouville problems in discrete spaces

Classical Sturm–Liouville problems of a discrete variable are extended for symmetric functions such that the corresponding solutions preserve the orthogonality property. Some generic illustrative examples are given in this sense.     

On the resolution of certain discrete univariate max–min problems

Graph coloring is a classical NP-hard combinatorial optimization problem with many practical applications. A broad range of heuristic methods exist for tackling the graph coloring problem: from fast greedy algorithms to more time-consuming metaheuristics. Although the latter produce better results in terms of minimizing the number of colors, the former are widely employed due to their simplicity. These heuristic methods are centralized since they operate by using complete knowledge of the graph. However, in real-world environmets where each component only interacts with a limited number of other components, the only option is to apply decentralized methods. This paper explores a novel and simple algorithm for decentralized graph coloring that uses a fixed number of colors and iteratively reduces the edge conflicts in the graph. We experimentally demonstrate that, for most of the tested instances, the new algorithm outperforms a recent and very competitive algorithm for decentralized graph coloring in terms of coloring quality. In our experiments, the fixed number of colors used by the new algorithm is controlled in a centralized manner.     

Local and parallel algorithms for fourth order problems discretized by the Morley–Wang–Xu element method

This paper systematically studies numerical solution of fourth order problems in any dimensions by use of the Morley–Wang–Xu (MWX) element discretization combined with two-grid methods (Xu and Zhou (Math Comp 69:881–909, 1999)). Since the coarse and fine finite element spaces are nonnested, two intergrid transfer operators are first constructed in any dimensions technically, based on which two classes of local and parallel algorithms are then devised for solving such problems. Following some ideas in (Xu and Zhou (Math Comp 69:881–909, 1999)), the intrinsic derivation of error analysis for nonconforming finite element methods of fourth order problems (Huang et al. (Appl Numer Math 37:519–533, 2001); Huang et al. (Sci China Ser A 49:109–120, 2006)), and the error estimates for the intergrid transfer operators, we prove that the discrete energy errors of the two classes of methods are of the sizes O(h + H ²) and O(h + H ²(H/h)^(d−1)/2), respectively. Here, H and h denote respectively the mesh sizes of the coarse and fine finite element triangulations, and d indicates the space dimension of the solution region. Numerical results are performed to support the theory obtained and to compare the numerical performance of several local and parallel algorithms using different intergrid transfer operators.     

Heuristic approaches for n/m/F/ ∑Ci scheduling problems

In this paper, we address the flow shop scheduling problem, with the criterion of minimizing the sum of job completion times. Two heuristic approaches are proposed to deal with this problem. The first approach focuses on reducing machine idle times and the second one puts efforts on reducing both the machine idle times and the job queue times. The computation of a variety of numerical cases demonstrates that the heuristic approaches are quite efficient in finding the desirable solutions.     

Spectral corrections for Sturm–Liouville problems

The numerical solution of the Sturm–Liouville problem can be achieved using shooting to obtain an eigenvalue approximation as a solution of a suitable nonlinear equation and then computing the corresponding eigenfunction. In this paper we use the shooting method both for eigenvalues and eigenfunctions. In integrating the corresponding initial value problems we resort to the boundary value method. The technique proposed seems to be well suited to supplying a general formula for the global discretization error of the eigenfunctions depending on the discretization errors arising from the numerical integration of the initial value problems. A technique to estimate the eigenvalue errors is also suggested, and seems to be particularly effective for the higher-index eigenvalues. Numerical experiments on some classical Sturm–Liouville problems are presented.