A cyclic scheduling problem with an undetermined number of parallel identical processors

This paper presents two integer linear programming (ILP) models for cyclic scheduling of tasks with unit/general processing time. Our work is motivated by digital signal processing (DSP) applications on FPGAs (Field-Programmable Gate Arrays)—hardware architectures hosting several sets of identical arithmetic units. These hardware units can be formalized as dedicated sets of parallel identical processors. We propose a method to find an optimal periodic schedule of DSP algorithms on such architectures where the number of available arithmetic units must be determined by the scheduling algorithm with respect to the capacity of the FPGA circuit. The emphasis is put on the efficiency of the ILP models. We show the advantages of our models in comparison with common ILP models on benchmarks and randomly generated instances.     

Stochastic cyclic scheduling problem in synchronous assembly and production lines

In this paper we address the stochastic cyclic scheduling problem in synchronous assembly and production lines. Synchronous lines are widely used in the production and assembly of various goods such as automobiles or household appliances. We consider cycle time minimisation (or throughput rate maximisation) as the objective of the scheduling problem with the assumption that the processing times are independent random variables. We first discuss the two-station case and present a lower bounding scheme and an approximate solution procedure for the scheduling problem. For the general case of the problem, two heuristic solution procedures are presented. An extension of the two-station lower bound to the general case of the problem is also discussed. The performance of the proposed heuristics on randomly generated problems is documented, and the impact of scheduling decisions on problems with different levels of variability in processing times are analysed. We also analyse the problem of sequence determination when the available information is limited to the expected values of individual processing times.     

A doubly cyclic channel assignment problem

A standard model for radio channel assignment involves a set V of sites, the set {0,1,2,…} of channels, and a constraint matrix (w(u, v)) specifying minimum channel separations. An assignment f:V→{0,1,2,…} is feasible if the distance f(u) − f(v)w(u, v) for each pair of sites u and v. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, …, k − 1, and to find a corresponding optimal assignment.

We consider here a related problem involving also two cycles. There is a given cyclic order τ on the sites, and feasible assignments f must also satisfy f(τv) f(v) for all except one site v. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, …, k − 1 are available then the distance between channels i and j is the minimum of ¦i − j¦ and k − ¦i − j¦. We show how to find a corresponding optimal channel assignment in O(¦V¦³) steps.     

Bootstrapping to solve the limited data problem in production control: an application in batch process industries

Batch process industries are characterized by complex precedence relationships among operations, which makes the estimation of an acceptable workload very difficult. Previous research indicated that a regression-based model that uses aggregate job set characteristics may be used to support order acceptance decisions. Applications of such models in real-life assume that sufficient historical data on job sets and the corresponding makespans are available. In practice, however, historical data maybe very limited and may not be sufficient to produce accurate regression estimates. This paper shows that such a lack of data significantly impacts the performance of regression-based order acceptance procedures. To resolve this problem, we devised a method that uses the bootstrap principle. A simulation study shows that performance improvements are obtained when using the parameters estimated from the bootstrapped data set, demonstrating that this bootstrapping procedure can indeed solve the limited data problem in production control.     

Colos: A collection optimization system as an application of the vehicle scheduling problem

This article deals with an example of the real problem of the Vehicle Collection optimization, which enables the plants to carry on their production. The problem has been solved in Poland in the delivery of milk to dairy plants. The milk collection optimization, however, is not a simple inversion of dairy product deliveries in town. Therefore we have the Vehicle Collection Problem (VCP) as an extension of the Vehicle Scheduling Problem (VSP). Next we present the idea of the Multicolmilk procedure, which satisfied several technical and organizational constraints of the milk collection process. To solve the VCP we have developed a modular Collection Optimization System (Colos). The basic component of the Colos is an optimization module based on the Multicolmilk procedure. The last part of the article contains implementation results in the dairy plants of Konin, Gniezno, Zielona Góra, and Cz¸estochowa, together with the presentation of difficulties which have cropped up in the course of preparation and implementation processes.     

A discontinuous Steklov problem with an application to water waves

A discontinuous Steklov problem associated with second order selfadjoint elliptic equations which arise in water wave problems is discussed. Here it is assumed that the eigenvalue equation is satisfied only on a part of the boundary. Eigenfunction expansions are derived in an elementary way using a suitable Green's functions. Also a minimax characterization of the eigenvalues is given.     

A perturbation study of a jet-like annular free boundary problem and an application to an optimal control problem

The NASH-MOSER Generalized Implicit Function Theorem is applied to an annular Free Boundary Problem related to jet or wave phenomena : local existence, uniqueness, and data dependence results are derived, together with an application to an Optimal Control Problem.     

Properties of tangential and cyclic polygons: an application of circulant matrices

In this paper, the properties of tangential and cyclic polygons proposed by Lopez-Real are proved rigorously using the theory of circulant matrices. In particular, the concepts of slippable tangential polygons and conformable cyclic polygons are defined. It is shown that an n-sided tangential (or cyclic) polygon P _n with n even is slippable (or conformable) and the sum of a set of non-adjacent sides (or interior angles) of P _n satisfies certain equalities. On the other hand, for a tangential (or cyclic) polygon P _n with n odd, it is rigid and the sum of a set of non-adjacent sides (or interior angles) of P _n satisfies certain inequalities. These inequalities give a definite answer to the question raised by Lopez-Real concerning the alternating sum of interior angles of a cyclic polygon.     

A remark on max-cut problem with an application to digital-analogue convertors

We introduce notions of a distance-decreasing weight function and of an alternating cut. For a class of distance-decreasing weights we solve the max-cut problem. In general, we prove that alternating cuts are near optimal. This has application to digital-analogue convertors.     

A strongly polynomial algorithm for solving two-sided linear systems in max-algebra

An algorithm for solving m×n systems of (max,+)-linear equations is presented. The systems have variables on both sides of the equations. After O(m⁴n⁴) iterations the algorithm either finds a solution of the system or finds out that no solution exists. Each iteration needs O(mn) operations so that the complexity of the presented algorithm is O(m⁵n⁵).     

A new heuristic and an exact approach for a production planning problem

Central European Journal of Operations Research - We deal with a very complex and hard scheduling problem. Two types of products are processed by a heterogeneous resource set, where resources have...     

A heuristic algorithm for a production planning problem in an assembly system

This paper focuses on a production planning problem in an assembly system operating on a make-to-order basis. Due dates are considered as constraints in the problem, that is, tardiness is not allowed. The objective of the problem is to minimise holding costs for final product inventory as well as work-in-process inventory. A non-linear mathematical model is presented and a heuristic algorithm is developed using a solution property and a network model for defining solutions of the problem. A series of computational tests were done to compare the algorithm with a commercial planning/scheduling software and backward finite-loading methods that employ various priority rules. The results showed that the suggested algorithm outperformed the others.     

A production planning problem in FMS

We present in this work a hierarchical approach for generating alternatives for production planning in a generic floor shop problem within the environment of Flexible Manufacturing Systems (hereafter, FMS). Briefly, the problem can be stated as follows: Given the resources of a FMS and the characteristics of the parts to be produced along a planning horizon, obtain the loading ordering of the parts in the FMS, the execution ordering of the operations and the processing route of each part (i.e., the working stations where each operation is to be executed), such that the production and transport costs are minimized and the modules workload is levelized. The problem is decomposed into three subproblems which are arranged in a hierarchy; a variety of models is presented, as well as the input/output relations that allow to integrate them; we also propose some algorithmic ideas to exploit the special structure of the problem. Computational experience is reported.     

A new self-adaptive CQ algorithm with an application to the LASSO problem

In this paper, we introduce a new self-adaptive CQ algorithm for solving split feasibility problems in real Hilbert spaces. The algorithm is designed, such that the stepsizes are directly computed at each iteration. We also consider the corresponding relaxed CQ algorithm for the proposed method. Under certain mild conditions, we establish weak convergence of the proposed algorithm as well as strong convergence of its hybrid-type variant. Finally, numerical examples illustrating the efficiency of our algorithm in solving the LASSO problem are presented.     

A robust optimization model for multi-site production planning problem in an uncertain environment

This paper addresses the multi-site production planning problem for a multinational lingerie company in Hong Kong subject to production import/export quotas imposed by regulatory requirements of different nations, the use of manufacturing factories/locations with regard to customers’ preferences, as well as production capacity, workforce level, storage space and resource conditions at the factories. In this paper, a robust optimization model is developed to solve multi-site production planning problem with uncertainty data, in which the total costs consisting of production cost, labor cost, inventory cost, and workforce changing cost are minimized. By adjusting penalty parameters, production management can determine an optimal medium-term production strategy including the production loading plan and workforce level while considering different economic growth scenarios. The robustness and effectiveness of the developed model are demonstrated by numerical results. The trade-off between solution robustness and model robustness is also analyzed.     

A tree labeling problem with an application to optimal approximation of continuous functions

We state a tree labeling problem, give an algorithm for solving it, and discuss some complexity characteristics of the algorithm. Furthermore, we discuss applications of these results to the approximation of a continuous function with given accuracy by linear combinations of characteristic functions of dyadic intervals with as few summands as possible. We also touch upon issues concerning tree-aided signal discretization.     

The cyclic minimum correlation problem

For variables (x,y,z) in [0, 1]³, three functionsA(y,z),B(z,x),C(x,y), with values in [0, 1], are to be chosen to minimize the integral, over (x,y,z) in the unit cube, ofAB+BC+CA, subject to prescribed values for the integral of each function. It is shown that a minimum can be achieved by dividing each of thex,y,z intervals into three or fewer subintervals and taking each ofA,B,C as indicator function of the union of some of the nine (or fewer) rectangles into which this divides its domain. Several specializations and generalizations of this problem are given consideration. It can be considered as a decision problem with distributed information.     

A practical solution approach for the cyclic inventory routing problem

Vendor managed inventory (VMI) is an example of effective cooperation and partnering practices between up- and downstream stages in a supply chain. In VMI, the supplier takes the responsibility for replenishing his customers’ inventories based on their consumption data, with the aim of optimizing the over all distribution and inventory costs throughout the supply chain. This paper discusses the challenging optimization problem that arises in this context, known as the inventory routing problem (IRP). The objective of this IRP problem is to determine a distribution plan that minimizes average distribution and inventory costs without causing any stock-out at the customers. Deterministic constant customer demand rates are assumed and therefore, a long-term cyclical approach is adopted, integrating fleet sizing, vehicle routing, and inventory management. Further, realistic side-constraints such as limited storage capacities, driving time restrictions and constant replenishment intervals are taken into account. A heuristic solution approach is proposed, analyzed and evaluated against a comparable state-of-the-art heuristic.     

Parametric shortest path algorithms with an application to cyclic staffing

Let G=(V, E) be a digraph with n vertices including a special vertex s. Let E′ ? E be a designated subset of edges. For each e?E there is an associated real number $\text{?}{}_1\text{(e)}$. Furthermore, let $\text{?}{}_2\text{(e)=1}$ if e?E′ and $\text{?}{}_2\text{(e)=0}$ if e?E ? E′. The length of edge e is $\text{?}{}_1\text{(e)? λ?}{}_2\text{(e)}$, where λ is a parameter that takes on real values. Thus the length varies additively in λ for each edge of E′.We shall present two algorithms for computing the shortest path from s to each vertex υ?V parametrically in the parameter λ, with respective running times O(n³) and O(n|E|log n). For dense digraphs the running time of the former algorithm is comparable to the fastest (non-parametric) shortest path algorithm known.This work generalizes the results of Karp [2] concerning the minimum cycle mean of a digraph, which reduces to the case that E′=E. Furthermore, the second parametric algorithm may be used in conjunction with a transformation given by Bartholdi, Orlin, and Ratliff [1] to give an O(n² log n) algorithm for the cyclic staffing problem.