A single-machine scheduling problem with maintenance activities to minimize makespan

We study a single-machine scheduling problem with periodic maintenance activity under two maintenance stratagems. Although the scheduling problem with single or periodic maintenance and nonresumable jobs has been well studied, most of past studies considered only one maintenance stratagem. This research deals with a single-machine scheduling problem where the machine should be stopped for maintenance after a fixed periodic interval (T) or after a fixed number of jobs (K) have been processed. The objective is to minimize the makespan for the addressed problem. A two-stage binary integer programming (BIP) model is provided for driving the optimal solution up to 350-job instances. For the large-sized problems, two efficient heuristics are provided for the different combinations of T and K. Computational results show that the proposed algorithm Best-Fit-Butterfly (BBF) performs well because the total average percentage error is below 1%. Once the constraint of the maximum number of jobs (K) processed in the machine’s available time interval (T) is equal or larger than half of jobs, the heuristic Best-Fit-Decreasing (DBF) is strongly recommended.     

Four species CA model for facing pedestrian traffic at rush hour

A model for the facing pedestrian traffic on a passage with a partition line at rush hour is developed. The model is described by a bi-directional cellular automaton (CA) model with four species. The CA model is not stochastic but deterministic. If the passage is congested and the local density is superior to the threshold, walkers to the east and to the west try to move separately changing their lane as the traffic rule is imposed on pedestrians at a high density. Walkers move freely ignoring the partition line at a low density. The traffic-rule effect at rush hour is taken into account in addition to the excluded-volume effect and bi-directionality. The pedestrian behavior under the traffic rule is clarified.     

An integer linear programming approach for a class of bilinear integer programs

We propose an Integer Linear Programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time.     

Binary integer programs with two variables per inequality

Several recent papers have shown that some properties of the maximum weight stable set problem hold true in the more general setting of binary integer programs with two variables per inequality. In this paper, we show that in fact the two problems are equivalent by using the transitive closure of the binary integer program and (possibly) reducing the number of variables by fixing, complementing, or identifying them. We use this equivalence to prove two conjectures made by Johnson and Padberg regarding the perfection of bidirected graphs.     

An efficient algorithm for computing traffic equilibria using TRANSYT model

Computing traffic equilibria with signal settings using TRANSYT model for an area traffic control road system is considered in this paper. Following Wardrop’s first principle, this problem can be formulated as a variational inequality problem. In this paper, we propose a novel algorithm to efficiently solve this equilibrium traffic assignment with global convergence. Numerical calculations are conducted on a grid-size road network. As it shows, the proposed method achieved greater savings in computational overheads than did those conventional methods for solving traffic equilibria when signal settings are particularly taken into account.     

An efficient algorithm for optimal design of area traffic control with network flows

An equilibrium network design (EQND) is a problem of finding the optimal design parameters while taking into account the route choice of users. This problem can be formulated as an optimization by taking the user equilibrium traffic assignment as a constraint. In this paper, the methods solving the EQND problem with signal settings are investigated via numerical calculations on two example road networks. An efficient algorithm is proposed in which improvement on a locally optimal search by combining the technique of parallel tangents with the gradient projection method is presented. As it shows, the method combines the locally optimal search and globally search heuristic achieved substantially better performance than did those other approaches.     

An intelligent decomposition of pairwise comparison matrices for large-scale decisions

A Pairwise Comparison Matrix (PCM) has been used to compute for relative priorities of elements and are integral components in widely applied decision making tools: the Analytic Hierarchy Process (AHP) and its generalized form, the Analytic Network Process (ANP). However, PCMs suffer from several issues limiting their applications to large-scale decision problems. These limitations can be attributed to the curse of dimensionality, that is, a large number of pairwise comparisons need to be elicited from a decision maker. This issue results to inconsistent preferences due to the limited cognitive powers of decision makers. To address these limitations, this research proposes a PCM decomposition methodology that reduces the elicited pairwise comparisons. A binary integer program is proposed to intelligently decompose a PCM into several smaller subsets using interdependence scores among elements. Since the subsets are disjoint, the most independent pivot element is identified to connect all subsets to derive the global weights of the elements from the original PCM. As a result, the number of pairwise comparison is reduced and consistency is of the comparisons is improved. The proposed decomposition methodology is applied to both AHP and ANP to demonstrate its advantages.     

城市道路交通信号实时控制问题的评述

对2008年全国研究生数学建模竞赛B题"城市道路交通信号实时控制问题"的命题背景,问题要求,建模方法,模型算法,结果分析,模型应用、模型评价等相关问题进行了分析和评述.结果表明,该问题的选择具有重要理论和实际应用价值,对研究生创新能力的培养具有重要作用.     

方程xy+yz+zx=n的正整数解

本文用 Ｓｉｅｇｅｌ－Ｔａｔｕｚａｗａ定理证明了：当ｎ＞１．２×１０~１１时,至多有两个正 整数ｎ。使方程ｘｕ＋ｙｚ＋ｚｘ＝ｎ无适合（ｘ,ｙ,ｚ）＝１且０＜ｘ＜ｙ＜ｚ的解（ｘ,ｙ,ｚ）, 并给出类数为２的二次域与多项式表素数的一个结果．     

Distribution center consolidation games

We study a location-inventory model to analyze the impact of consolidation of distribution centers on facility and inventory costs. We introduce a cooperative game and show that when demand processes are i.i.d. the core is non-empty, i.e., consolidation allows for a stable division of the minimal costs.     

Integer-Programming Software Systems

Recent developments in integer-programming software systems have tremendously improved our ability to solve large-scale instances. We review the major algorithmic components of state-of-the-art solvers and discuss the options available to users for adjusting the behavior of these solvers when default settings do not achieve the desired performance level. Furthermore, we highlight advances towards integrated modeling and solution environments. We conclude with a discussion of model characteristics and substructures that pose challenges for integer-programming software systems and a perspective on features we may expect to see in these systems in the near future.     

A heuristic algorithm for the hospital health examination scheduling problem

This study considers the problem of health examination scheduling. Depending on their gender, age, and special requirements, health examinees select one of the health examination packages offered by a health examination center. The health examination center must schedule all the examinees, working to minimize examinee/doctor waiting time and respect time and resource constraints, while also taking other limitations, such as the sequence and continuity of the examination procedures, into consideration. The Binary integer programming (BIP) model is one popular way to solve this health examination scheduling problem. However, as the number of examinees and health examination procedures increase, solving BIP models becomes more and more difficult, if not impossible. This study proposes health examination scheduling algorithm (HESA), a heuristic algorithm designed to solve the health examination scheduling problem efficiently and effectively. HESA has two primary objectives: minimizing examinee waiting time and minimizing doctor waiting time. To minimize examinee waiting time, HESA schedules the various parts of each examinee’s checkup for times when the examinee is available, taking the sequence of the examination procedures and the availability of the resources required into account. To minimize doctor waiting time, HESA focuses on doctors instead of examinees, assigning waiting examinees to a doctor as soon as one becomes available. Both complexity analysis and computational analyses have shown that HESA is very efficient in solving the health examination scheduling problem. In addition to the theoretical results, the results of HESA’s application to the concrete health examination scheduling problems of two large hospitals in Taiwan are also reported.     

A dynamical systems approach based on averaging to model the macroscopic flow of freeway traffic

The flow of traffic exhibits distinct characteristics under different conditions, reflecting the congestion during peak hours and relatively free motion during off-peak hours. This requires one to use different mathematical equations to describe the diverse traffic characteristics. Thus, the flow of traffic is best described by a hybrid system, namely different governing equations for the different regimes of response, and it is such a hybrid approach that is investigated in this paper. Existing models for the flow of traffic treat traffic as a continuum or employ techniques similar to those used in the kinetic theory of gases, neither of these approaches gainfully exploit the hybrid nature of the problem. Spurious two-way propagation of disturbances that are physically unacceptable are predicted by continuum models for the flow of traffic. The number of vehicles in a typical section of the highway does not justify its being modeled as a continuum. It is also important to recognize that the basic premises of kinetic theory are not appropriate for the flow of traffic (see [S. Darbha, K.R. Rajagopal, Limit of a collection of dynamical systems: an application to modeling the flow of traffic, Mathematical Models and Methods in Applied Sciences 12 (10) (2002) 1381–1399] for a rationale for the same). A model for the flow of traffic that does not treat traffic as a continuum or use notions from kinetic theory is developed here and corroborated with real-time data collected on US 183 in Austin, Texas. Predictions based on the hybrid system model seem to agree reasonably well with the data collected on US 183.     

Path planning,modeling and simulation of an autonomous articulated heavy construction machine performing a loading cycle

This research presents path planning and tracking for an articulated large wheel loader during the travel portion of a loading cycle. The study proposes a methodology for path planning, modeling, simulation and control of such vehicles; the analysis focuses on all of these components together and explains the relation among them. The developed methodology for path planning takes into account the dynamics and the performance characteristics of the heavy construction articulated vehicles, it also takes into account the construction working site constraints. The path optimization criterion is based on distance and cusp minimization without neglecting the constraints imposed by the size of the vehicle and its stable turning radius. The proposed path planning methodology is an extension and an improvement for Reeds and Shepp algorithm for a point shortest path calculation. The optimal path is consisted of circular arcs and straight segments, the radius is constant and identical for each arc in the desired path, the radius assumed to be similar to the minimum turning radius of the machine. When optimizing articulated machine path; to best account for machine size and articulation; more than one approach are discussed and compared. The machine is modeled and simulated during tracing the pre-defined planned path. The machine model includes the main frames, tires and a steering controller. The developed PID controller is used to keep machine lateral position within the pre-defined path while traveling with constant speed. The results showed an acceptable optimized path which the machine is able to track closely.     

Cellular Network Design Site Selection and Frequency Planning

Deployment of cellular networks involves substantial capital investment. Competition motivates service providers to minimize these costs while maintaining service quality. We develop a cost-minimizing planning model that simultaneously determines three important variables – base station location, power level and frequency group assignments for the antennas at each selected base station. It can represent different antenna configurations and frequency groups commonly used in practice. The integer-programming problem is solved using a Lagrangian relaxation based heuristic and computational tests indicate good solution quality for reasonably large problems. We also note the appropriate role of such optimization models in the overall planning process.     

Microscopic modeling and control logic for incident-responsive automatic vehicle movements in single-automated-lane highway systems

Automatic response to lane-blocking incidents is a critical issue in the field of automated highway systems (AHS). Accordingly, this paper presents a microscopic vehicular control methodology for automatic-control (AC) vehicular movements in response to lane-blocking incidents in the AHS environment. The embedded traffic control logic is based on the basic safety requirements for automatic-control lane traffic maneuvers responding to lane-blocking incidents in the single-automated-lane AHS environment. Accordingly, respective automated vehicular control models are proposed to deal with AC vehicles moving in three corresponding sequential phases, i.e., (1) AC platoon approaching the incident site from the blocked lane, (2) mandatory lane changing and mixed car following in the adjacent lane, and (3) AC platoon reforming downstream from the incident site in the blocked automated lane. Using a microscopic simulation model which embeds these proposed models, preliminary tests are conducted to investigate the relative performance of the proposed method in various traffic flow and control scenarios. The resulting numerical results, including simplified sensitivity analyses, indicate that the proposed microscopic traffic control logic permits regulating automatic-control vehicular movements in response to the effects of lane-blocking incidents on traffic flows either in control-free lanes or in the automatic-control lanes. Implications of the results and some findings are discussed for further research.     

基于季节ARIMA模型的GSM话务量建模和预报

本文用季节模型对天津移动GSM网的话务量进行了建模分析和预报,研究表明用季节模型对移动话务量进行建模分析和预报是可行的,同时在文中我们还给出了带两个周期季ARIMA模型的一般表达式,并用这种带多个周期的模型对实际的网络业务进行了建模和预报。     

Regulation under partial cooperation: The case of a queueing system

Socially optimal behavior can be achieved through the cooperation of the participating agents with a central planner. What happens when only a fraction of the population cooperates? We investigate this question in a Markovian single server queue. The main result is non-intuitive: the optimal control of cooperative customers is independent of their proportion. We also conclude that the gain from controlling cooperative customers after they join the queue is relatively small.     

On the modeling of pedestrian motion

A model for the simulation of pedestrian flows and crowd dynamics has been developed. The model is based on a series of forces, such as: will forces (the desire to reach a place at a certain time), pedestrian collision avoidance forces, obstacle/wall avoidance forces; pedestrian contact forces, and obstacle/wall contact forces. Except for the will force, it is assumed that for any given pedestrian these forces are the result of only local (nearest neighbour) situations. The near-neighbour search problem is solved by an efficient incremental Delaunay triangulation that is updated at every timestep. In order to allow for general geometries a so-called background triangulation is used to carry all geographic information. At any given time the location of any given pedestrian is updated on this mesh. The results obtained to date show that the model performs well for standard benchmarks, and allows for typical crowd dynamics, such as lane forming, overtaking, avoidance of obstacles and panic behaviour.