Abstract:
This paper presents an approach for solving the bus crew scheduling problem which considers early, day, and late duty modes with time shift and work intensity constraints. Furthermore, the constraint with the least crew number of a certain duty (e.g., day duty) has also been considered. An optimization model is formulated as a 0-1 integer programming problem to improve the efficiency of crew scheduling at the minimum expense of total idle time of crew for a circle bus line. Correspondingly, a heuristic algorithm utilizing the tabu search algorithm has been proposed to solve the model. Finally, the proposed model and algorithm are successfully tested by a case study.

Abstract:
The "reconfiguration problem" for circular colourings asks, given two $(p,q)$-colourings $f$ and $g$ of a graph $G$, is it possible to transform $f$ into $g$ by changing the colour of one vertex at a time such that every intermediate mapping is a $(p,q)$-colouring? We show that this problem can be solved in polynomial time for $2\leq p/q <4$ and is PSPACE-complete for $p/q\geq 4$. This generalizes a known dichotomy theorem for reconfiguring classical graph colourings.

Abstract:
We present an algorithm for controlling and scheduling multiple linear time-invariant processes on a shared bandwidth limited communication network using adaptive sampling intervals. The controller is centralized and computes at every sampling instant not only the new control command for a process, but also decides the time interval to wait until taking the next sample. The approach relies on model predictive control ideas, where the cost function penalizes the state and control effort as well as the time interval until the next sample is taken. The latter is introduced in order to generate an adaptive sampling scheme for the overall system such that the sampling time increases as the norm of the system state goes to zero. The paper presents a method for synthesizing such a predictive controller and gives explicit sufficient conditions for when it is stabilizing. Further explicit conditions are given which guarantee conflict free transmissions on the network. It is shown that the optimization problem may be solved off-line and that the controller can be implemented as a lookup table of state feedback gains. Simulation studies which compare the proposed algorithm to periodic sampling illustrate potential performance gains.

Abstract:
The fast developing services in Internet pose challenges to the efficient transmission of various types of data, so an effective packet scheduling scheme is needed to meet the QoS constraints of heterogeneous services. In this article, the priority-queuing model was used to study the performances of various strategics based on delay sensitivity and par kets length. And the non-preemptive short packet first strategy was proved to result in the minimal overall delay. With different strategies for delay-sensitive and non-delay-sensitive services, an optimal priority-queuing model for the schedtr ling of multiple Internet services was designed based on above conclusions. The results from simulation experiments in NS-2 verified the superiority of the model. The results also demonstrated the features of packets queuing under different traffic scenarios and the law of variation for such performance indices as packet delivery ratio, throughput and average delay, which can be used to design effective measures for performance optimization.

Abstract:
The authors deal with the topic of the final assembly scheduling realized by the use of genetic algorithms (GAs). The objective of the research was to study in depth the use of GA for scheduling mixed-model assembly lines and to propose a model able to produce feasible solutions also according to the particular requirements of an important Italian motorbike company, as well as to capture the results of this change in terms of better operational performances. The “chessboard shifting” of work teams among the mixed-model assembly lines of the selected company makes the scheduling problem more complex. Therefore, a complex model for scheduling is required. We propose an application of the GAs in order to test their effectiveness to real scheduling problems. The high quality of the final assembly plans with high adherence to the delivery date, obtained in a short elaboration time, confirms that the choice was right and suggests the use of GAs in other complex manufacturing systems. 1. Introduction Simulating the natural evolutionary process of human beings results in stochastic optimization techniques, called evolutionary algorithms, which can often outperform conventional methods when applied to complex real-world problems. Scheduling problems of manufacturing planning are a common example of complex problems where the interest in these groundbreaking techniques is growing among both scholars and practitioners. The paper examines a case study of a scheduling system for a mixed-model assembly lines [1], also referred to as the permutation flowshop scheduling problem. In such a production system, the managers want to sequence different products, thus obtaining a high service level (product mix) without delays in products delivery while respecting the constraints of capacity. The focus of the present work is the application of the genetic algorithms (GAs) as a technique for the resolution of such a complex problem. The paper is structured as follows. Section 2 depicts the principles and the successful characteristics of these techniques, providing an applicative model for their use in combinatory problems, in particular in the scheduling of final assembly phase of mixed-model assembly lines. We use the case study of an important Italian motorbike company as the outset of the study. Section 3 describes the company’s production system and the demand management logics. Afterwards, in Section 4, we propose a scheduling approach consisting of two stages, a macrostep and a microstep. The two steps, respectively, carry out a “macroscheduling” and a “microscheduling”

Abstract:
高效的调度方法是提高中继卫星系统应用效能的关键。中继卫星调度主要是要根据用户提交的任务申请信息，科学合理地分配中继卫星系统资源，最大程度满足各项任务需求，为中继卫星系统编制最优工作计划。考虑中继业务中的多滑动时间窗口需求，构建了中继卫星调度问题的数学规划模型，以最大化任务完成率和用户期望满足度为目标，以任务需求约束、资源使用约束作为约束条件。设计了基于时间自由度的启发式算法，该算法包括了任务时间自由度评价、任务资源匹配、任务插空和资源更新4个算子。最后，通过大规模仿真实验验证了算法的有效性。 Efficient scheduling algorithm plays a key role in improving the efficacy of tracking and data relay satellite system (TDRS). Scheduling of TDRS aims to scientifically allocate TDRS resources according to the task application information from the users, such that maximal task requirements are met and the optimal activity schedule is made for the TDRS system. The mathematical model is constructed for the TDRS scheduling problem with the consideration of multiple slide windows in real-world requirements. The objective of the model is to maximize the task completion rate and the expectation satisfaction degree of users. The involved constraints include task requirement constraints and resource using constraints. A heuristic algorithm based on time freedom degree is proposed to solve the model, which includes four operators, i.e., evaluation of the time freedom degree of each task, matching between tasks and resources, task insertion and resource update. At last, extensive experimental simulation demonstrates the effectiveness of the proposed algorithm.

Abstract:
A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. The instances of the Weighted Maximum H-Colourable Subgraph problem (MAX H-COL) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H=K_k this problem is equivalent to MAX k-CUT. Farnqvist et al. have introduced a parameter on the space of graphs that allows close study of the approximability properties of MAX H-COL. Specifically, it can be used to extend previously known (in)approximability results to larger classes of graphs. Here, we investigate the properties of this parameter on circular complete graphs K_{p/q}, where 2 <= p/q <= 3. The results are extended to K_4-minor-free graphs and graphs with bounded maximum average degree. We also consider connections with Samal's work on fractional covering by cuts: we address, and decide, two conjectures concerning cubical chromatic numbers.

Abstract:
We present results referring to the Hadwiger-Nelson problem which asks for the minimum number of colours needed to colour the plane with no two points at distance $1$ having the same colour. Exoo considered a more general problem concerning graphs $G_{[a,b]}$ with $\mathbb{R}^2$ as the vertex set and two vertices adjacent if their distance is in the interval $[a,b]$. Exoo conjectured $\chi(G_{[a,b]}) = 7$ for sufficiently small but positive difference between $a$ and $b$. We partially answer this conjecture by proving that $\chi(G_{[a,b]}) \geq 5$ for $b > a$. A $j$-fold colouring of graph $G = (V,E)$ is an assignment of $j$-elemental sets of colours to the vertices of $G$, in such a way that the sets assigned to any two adjacent vertices are disjoint. The fractional chromatic number $\chi_f(G)$ is the infimum of fractions $k/j$ for $j$-fold colouring of $G$ using $k$ colours. We generalize a method by Hochberg and O'Donnel (who proved that $G_{[1,1]} \leq 4.36$) for fractional colouring of graphs $G_{[a,b]}$, obtaining a bound dependant on $\frac{a}{b}$. We also present few specific and two general methods for $j$-fold coloring of $G_{[a,b]}$ for small $j$, in particular for $G_{[1,1]}$ and $G_{[1,2]}$. The $j$-fold colouring for small $j$ has strong practical motivation especially in scheduling theory, while graph $G_{[1,2]}$ is often used to model hidden conflicts in radio networks.

Abstract:
As emergency happens, the scheduling of rescue resources to multiple emergency locations is a realistic and intricate problem, especially when the available resources are limited. After analyzing the competition requirements of multiple emergency locations, a non-cooperative games model and algorithm for scheduling of rescue resources was presented. In the model, the players corresponded to various emergency locations, strategies to all resources scheduling and the payoff of each emergency location to the reciprocal of its scheduling cost. Thus, the optimal scheduling results were determined by the Nash equilibrium point of this game. Then the iterative algorithm was introduced to seek out the Nash equilibrium point. A numerical case test was given to demonstrate the feasibility and availability of the model.

Abstract:
We consider the problem of Joint Routing, Scheduling and Power-control (JRSP) problem for multihop wireless networks (MHWN) with multiple antennas. We extend the problem and a (sub-optimal) heuristic solution method for JRSP in MHWN with single antennas. We present an iterative scheme to calculate link capacities(achievable rates) in the interference environment of the network using SINR model. We then present the algorithm for solving the JRSP problem. This completes a feasible system model for MHWN when nodes have multiple antennas. We show that the gain we achieve by using multiple antennas in the network is linear both in optimal performance as well as heuristic algorithmic performance.