### Article

## Solving a supply chain scheduling problem with non-identical job sizes and release times by applying a novel effective heuristic algorithm

Motivated by applications in manufacturing industry, we consider a supply chain scheduling problem, where each job is characterised by non-identical sizes, different release times and unequal processing times. The objective is to minimise the makespan by making batching and sequencing decisions. The problem is formalised as a mixed integer programming model and proved to be strongly NP-hard. Some structural properties are presented for both the general case and a special case. Based on these properties, a lower bound is derived, and a novel two-phase heuristic (TP-H) is developed to solve the problem, which guarantees to obtain a worst case performance ratio of

This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.

The Travelling Salesman Problem (TSP) is a fundamental task in combinatorial optimization. A special case of the TSP is Metric TSP, where the triangle inequality holds. Solutions of the TSP are generally used for costs minimization, such as finding the best tour for round-the-world trip or construction of very large-scale integration schemes. Since the TSP is NP-hard, heuristic algorithms providing near optimal solutions will be considered. The objective of this article is to find a group of Pareto optimal heuristic algorithms for Metric TSP under criteria of run time efficiency and qualitative performance as a part of the experimental study. Classification of algorithms for Metric TSP is presented. Feasible heuristic algorithms and their prior estimates are described. The data structure and the details of the research methodology are provided. Finally, results and prospective research are discussed.

This paper deals with the problem of preemptive scheduling in a two-stage supply chain framework. The supply chain environment contains two stages: production and transportation. In the production stage jobs are processed on a manufacturer's bounded serial batching machine, preemptions are allowed, and set-up time is required before a new batch is processed. In the transportation stage each batch is delivered to a customer by a single vehicle. The objective is to minimize the makespan by making decisions for both mutually coordinated stages. Specifically, two versions are studied. The first one is that all jobs are available to be processed at time zero, and the second one is that jobs have different release times. An time algorithm is developed for the first version, and we show that it can produce the optimal schedule for the entire problem. For the second version, based on some useful properties we have designed an time heuristic and a novel lower bound. The worst-case performance ratio of our algorithm is bounded by 2. Our computational study with random instances of different scales shows high-quality solutions for either small-scale or large-scale instances returned in a reasonable PC times.

The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which defined on mixed multigraph) using the reduction of the original problem into General Travelling Salesman Problem (GTSP). The variants of CPP are pointed out. The mathematical formulations of some problems are presented. The algorithm for reduction the MCPP in multigraph into GTSP is shown. The experimental results of solving MCPP in multigraph through the reduction into GTSP are presented.

The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which defined on mixed multigraph) using the reduction of the original problem into General Travelling Salesman Problem (GTSP). The variants of CPP are pointed out. The mathematical formulations of some problems are presented. The algorithm for reduction the MCPP in multigraph into GTSP is shown. The experimental results of solving MCPP in multigraph through the reduction into GTSP are presented.

The objective of this research is to develop a software algorithm for evaluating the effectiveness of using the Financial Message Transfer System for Remote Banking Systems. The study considers hardware system that provide two types of interactions between the legal entity and the bank: ≪Direct Banking≫ and ≪Internet Banking≫. During the work were identified and analyzed the main features of remote banking systems and determined the efficiency criteria of the systems. Based on the analysis output, were developed and proposed a mathematical model for evaluating the effectiveness of considered systems thought using the cost and quantity coefficients of system ensuring, as well as the financial and economic business performance indicators. In accordance with the proposed mathematical model, was constructed an algorithm that makes it possible to obtain quantitative estimates of Remote Banking Systems effectiveness. The developed algorithm belongs to the heuristic class and is based on the analysis of both the open statistical and the modeled by simulation tools data. The conducted computational experiments reflects the efficiency of the proposed mathematical model, as well as an algorithm based on the developed model.

A form for an unbiased estimate of the coefficient of determination of a linear regression model is obtained. It is calculated by using a sample from a multivariate normal distribution. This estimate is proposed as an alternative criterion for a choice of regression factors.