An efficient search method for job-shop scheduling problems

We present an efficient search method for job-shop scheduling problems. Our technique is based on an innovative way of relaxing and subsequently reimposing the capacity constraints on some critical operations. We integrate this technique into a fast tabu search algorithm. Our computational results on benchmark problems show that this approach is very effective. Upper bounds for 11 well-known test problems are thus improved. Through the work presented We hope to move a step closer to the ultimate vision of an automated system for generating optimal or near-optimal production schedules. The peripheral conditions for such a system are ripe with the increasingly widespread adoption of enterprise information systems and plant floor tracking systems based on bar code or wireless technologies. One of the remaining obstacles, however, is the fact that scheduling problems arising from many production environments, including job-shops, are extremely difficult to solve. Motivated by recent success of local search methods in solving the job-shop scheduling problem, we propose a new diversification technique based on relaxing and subsequently reimposing the capacity constraints on some critical operations. We integrate this technique into a fast tabu search algorithm and are able to demonstrate its effectiveness through extensive computational experiments. In future research, we will consider other diversification techniques that are not restricted to critical operations.     

Integrating the lot-sizing and sequencing decisions for scheduling a capacitated flow line

In this paper we consider a general problem of scheduling a single flow line consisting of multiple machines and producing a given set of jobs. The manufacturing environment is characterized by sequence dependent set-up times, limited intermediate buffer space, and capacity constraints. In addition, jobs are assigned with due dates that have to be met. The objectives of the scheduling are: (1) to meet the due dates without violating the capacity constraints, (2) to minimize the makespan, and (3) to minimize the inventory holding costs. While most of the approaches in the literature treat the problem of scheduling in flow lines as two independent sub-problems of lot-sizing and sequencing, our approach integrates the lot-sizing and sequencing heuristics. The integrated approach uses the Silver-Meal heuristic (modified to include lot-splitting) for lot-sizing and an improvement procedure applied to Palmer's heuristic for sequencing, which takes into account the actual sequence dependent set-up times and the limited intermedite buffer capacity. We evaluate the performance of the integrated approach and demonstrate its efficacy for scheduling a real world SMT manufacturing environment.     

A genetic algorithm for integrating lot-sizing and sequencing in scheduling a capacitated flow line

In this paper we present a genetic algorithm for solving an important but difficult scheduling problem: that of integrating the lot-sizing and sequencing decisions in scheduling a flow line involving sequence dependent setup times, capacity constraints, limited buffer capacity between machines, and due dates. The problem is based on a real world manufacturing facility that is also described. Novel crossover and mutation operators are presented for both the lot-sizing and sequencing parts of the scheduling problem and the performance of the genetic algorithm is compared to a heuristic approach of integration previously shown to have been effective.     

Entropic Grid Scheduling

Computational Grids (CGs) are large scale dynamical networks of geographically distributed peer resource clusters. These clusters are independent but cooperating computing systems bound by a management framework for the provision of computing services, called Grid Services. In its basic form, the Grid scheduling problem consists in finding at least one cluster that has the capacity to handle, within the constraints of a specified quality of service, a user service request submitted to the CG. Since CGs span distinct management domains, the scheduling process has to be decentralized. Furthermore, it has to account for the ubiquitous uncertainty on the state of the CG. In this paper, we propose a scalable distributed Entropy-based scheduling approach that utilizes a Markov chain model to capture the dynamics of the service capacity state. An entropy-based quantification of the uncertainty on the service capacity information is developed and explicitly integrated within the proposed Grid scheduling approach. The performance of the proposed scheduling strategy is validated, through simulation, against a random delegation scheme and a load balancing-based scheduling strategy with respect to throughput, exploitation and convergence speed, respectively.     

Energy-efficient deadline scheduling for heterogeneous systems

Energy efficiency is a major concern in modern high performance computing (HPC) systems and a power-aware scheduling approach is a promising way to achieve that. While there are a number of studies in power-aware scheduling by means of dynamic power management (DPM) and/or dynamic voltage and frequency scaling (DVFS) techniques, most of them only consider scheduling at a steady state. However, HPC applications like scientific visualization often need deadline constraints to guarantee timely completion. In this paper we present power-aware scheduling algorithms with deadline constraints for heterogeneous systems. We formulate the problem by extending the traditional multiprocessor scheduling and design approximation algorithms with analysis on the worst-case performance. We also present a pricing scheme for tasks in the way that the price of a task varies as its energy usage as well as largely depending on the tightness of its deadline. Last we extend the proposed algorithm to the control dependence graph and the online case which is more realistic. Through the extensive experiments, we demonstrate that the proposed algorithm achieves near-optimal energy efficiency, on average 16.4% better for synthetic workload and 12.9% better for realistic workload than the EDD (Earliest Due Date)-based algorithm; The extended online algorithm also outperforms the EDF (Earliest Deadline First)-based algorithm with an average up to 26% of energy saving and 22% of deadline satisfaction. It is experimentally shown as well that the pricing scheme provides a flexible trade-off between deadline tightness and price.     

Effective Capacity and QoS for Wireless Scheduling

Multiuser scheduling in a wireless context, where channel state information is exploited at the base station, can result in significant throughput gains to users. However, when QoS constraints are imposed (in the form of overflow probabilities), the benefits of multiuser scheduling are not clear. In this paper, we address this question for independent and identically distributed ON-OFF channel models, and study a ldquomultiuserrdquo formulation of effective capacity with QoS constraints. We consider a channel-aware greedy rule as well as the channel-aware max-queue rule, and showed that these algorithms that yield the same long-term throughput without QoS constraints have very different performance when QoS constraints are imposed. Next, we study the effective capacity for varying channel burstiness. From results on multiuser scheduling, we expect the long-term throughput to grow with increasing channel burstiness. However, we show that the throughput with QoS constraints decreases with increasing channel burstiness. The intuitive justification for this is that with increasing burstiness, even though the the long-term throughput increases, the channel access delay increases as well resulting in poor QoS performance.     

Scheduling on-demand broadcast with timing constraints

In a distributed system, broadcasting is an efficient way to dispense data in certain highly dynamic environments. While there are several well-known on-line broadcast scheduling strategies that minimize wait time, there has been little research that considers on-demand broadcasting with timing constraints. One application which could benefit from a strategy for on-demand broadcast with timing constraints is a real-time database system. Scheduling strategies are needed in real-time databases that identify which data item to broadcast next in order to minimize missed deadlines. The scheduling decisions required in a real-time broadcast system allow the system to be modeled as a Markov Decision Process (MDP). In this paper, we analyze the MDP model and determine that finding an optimal solution is a hard problem in PSPACE. We propose a scheduling approach, called Aggregated Critical Requests (ACR), which is based on the MDP formulation and present two algorithms based on this approach. ACR is designed for timely delivery of data to clients in order to maximize the reward by minimizing the deadlines missed. Results from trace-driven experiments indicate the ACR approach provides a flexible strategy that can outperform existing strategies under a variety of factors.     

Circuit retiming applied to decomposed software pipelining

This paper elaborates on a new view on software pipelining, called decomposed software pipelining. The approach is to decouple the problem into resource constraints and dependence constraints. Resource constraints management amounts to scheduling an acyclic graph subject to resource constraints for which an efficiency bound is known, resulting in a bound for loop scheduling. The acyclic graph is obtained by cutting some particular edges of the (cyclic) dependence graph. In this paper, we cut edges in a different way, using circuit retiming algorithms, so as to minimize both the longest dependence path in the acyclic graph, and the number of edges in the acyclic graph. With this technique, we improve the efficiency bound given for Gasperoni and Schwlegelshohn algorithm, and we reduce the constraints that remain for the acyclic problem. We believe this framework to be of interest because it brings a new insight into the software problem by establishing its deep link with the circuit retiming problem     

Tabu search based resource allocation in radiological examination process execution

Efficient resource scheduling and allocation in radiological examination process (REP) execution is a key requirement to improve patient throughput and radiological resource utilization and to manage unexpected events that occur when resource scheduling and allocation decisions change due to clinical needs. In this paper, a Tabu search based approach is presented to solve the resource scheduling and allocation problems in REP execution. The primary objective of the approach is to minimize a weighted sum of average examination flow time, average idle time of the resources, and delays. Unexpected events, i.e., emergent or absent examinations, are also considered. For certain parameter combinations, the optimal solution of radiological resource scheduling and allocation is found, while considering the limitations such as routing and resource constraints. Simulations in the application case are performed. Results show that the proposed approach makes efficient use of radiological resource capacity and improves the patient throughput in REP execution.     

Personnel scheduling in a complex logistic system: a railway application case

In complex logistic systems, such as transportation systems, dealing with personnel scheduling is a non-trivial task. Duties have to be created and assigned to workers in a way to optimize a certain objective function. In this paper, in particular, we consider the case of scheduling train drivers on a railway subnetwork. Train driver scheduling involves the construction of feasible duties from a set of trips to be carried out by a number of train drivers. Each duty consists of a sequence of trips to be carried out by a single train driver on a single day. The duties should be such that: each trip is covered by at least one duty, each duty satisfies feasibility constraints, additional constraints involving the complete schedule are satisfied, one or several objectives are met. In this paper we focus on minimizing the number of duties and on maximizing the robustness of the obtained schedule for outside disruptions. We present an implicit column generation solution approach. We describe a heuristic procedure to find an initial feasible solution together with a heuristic branch-and-price algorithm based on a dynamic programming algorithm for the pricing-out of columns. We tested our approach on the timetable of the Intercity train series 500, 700, 1600 and 1700 of NS Reizigers, the largest Dutch operator of passengers trains.     

Distributed manufacturing scheduling using intelligent agents

Manufacturing scheduling is an optimization process that allocates limited manufacturing resources over time among parallel and sequential manufacturing activities. This allocation must obey a set of rules or constraints that reflect the temporal relationships between manufacturing activities and the capacity limitations of a set of shared resources. The allocation also affects a schedule's optimality with respect to criteria such as cost, lateness, or throughput. The globalization of manufacturing makes such optimization increasingly important. To survive in this competitive market, manufacturing enterprises must increase their productivity and profitability through greater shop floor agility. Agent-based manufacturing scheduling systems are a promising way to provide this optimization.     

School bus routing and scheduling: An expert system approach

This paper proposes an expert system approach to routing and scheduling school buses for a rural school system. The expert system is programmed in TURBO PROLOG for use on an IBM/XT and is applied to rural county school systems in Alabama.

The busing problem considered here consists of two components: routing and scheduling. The routing problem is concerned with the determination of a stop-to-stop route to be traversed to each school by each bus whereas the scheduling problem, the determination of times at all bus stops for each bus. A bus may be used for multiple runs. Each route is designed in such a way that the bus capacity, student riding time, school time window and road condition constraints are satisfied while attempting to minimize the number of buses required in operation, minimize the fleet travel time and balance the bus loads.

Conventionally, a predetermined algorithm is coded into computer programs for generating efficient routes and schedules. The user or route designer neither has any knowledge about the algorithm nor has any input of personal expertise into the solution process. As a result, a veteran designer is skeptical of the computer-generated routes and schedules. Moreover, non-quantifiable factors such as safety, preference and judgment are not taken into consideration in the traditional approach.

To alleviate these deficiencies, an expert system approach, which enables the expert knowledge to be kept separately from its execution, is utilized. This knowledge base contains factual knowledge such as road map, school locations, but capacities, stop locations, number of students at each stop, and drivers' homes. It also contains procedural knowledge such as heuristics for finding a route and scheduling multiple runs for a bus subject to various constraints. The inference engine or control program chooses the appropriate heuristics used in constructing efficient routes and schedules with respect to various objectives or goals. A user interface includes the graphic display of road maps and determined routes.     

A two-stage heuristic approach for nurse scheduling problem: A case study in an emergency department

Nurse scheduling is a critical issue in the management of emergency department. Under the intense work environment, it is imperative to make quality nurse schedules in a most cost and time effective way. To this end, a spreadsheet-based two-stage heuristic approach is proposed for the nurse scheduling problem (NSP) in a local emergency department. First, an initial schedule satisfying all hard constraints is generated by the simple shift assignment heuristic. Second, the sequential local search algorithm is employed to improve the initial schedules by taking soft constraints (nurse preferences) into account. The proposed approach is benchmarked with the existing approach and 0–1 programming. The contribution of this paper is twofold. First, it is one of a few studies in nurse scheduling literature using heuristic approach to generate nurse schedules based on Excel spreadsheet. Therefore, users with little knowledge on linear programming and computer sciences can operate and change the scheduling algorithms easily. Second, while most studies on nurse scheduling are situated in hospitals, this paper attempts to bridge the research gap by investigating the NSP in the emergency department where the scheduling rules are much more restrictive due to the intense and dynamic work environment. Overall, our approach generates satisfactory schedules with higher level of user-friendliness, efficiency, and flexibility of rescheduling as compared to both the existing approach and 0–1 programming.     

Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Timing Constraints

In some hard real-time systems, relative timing constraints may be imposed on task executions, in addition to the release time and deadline constraints. Relative timing constraints such as separation or relative deadline constraints may be given between start or finish times of tasks (Gerber et al., 1995; Han and Lin, 1989; Han et al., 1992; Han and Lin, 1992; Han et al., 1996).One approach in real-time scheduling is to find a total order on a set of N tasks in a scheduling window, and cyclically use this order at run time to execute tasks. However, in the presence of relative timing constraints, if the task execution times are nondeterministic with defined lower and upper bounds, it is not always possible to statically assign task start times at pre-runtime for a given task ordering (Gerber et al., 1995).We develop a technique called dynamic cyclic dispatching as an extension of a parametric dispatching mechanism in (Gerber et al., 1995). An ordered set of N tasks is assumed to be given in a scheduling window and this schedule(ordering) is cyclically repeated at runtime in consecutive scheduling windows. Relative timing constraints between tasks may be defined across scheduling window boundaries as well as within one scheduling window. A task set is defined to be dispatchable if there exists any way in which the tasks can be dispatched with all their timing constraints satisfied. An off-line algorithm is presented to check the dispatchability of a task set and to obtain parametric lower and upper bound functions for task start times if the task set is dispatchable. These parametric bound functions are evaluated at runtime to obtain a valid time interval during which a task can be started. The complexity of this off-line component is shown to be O(n ² N ³) where n is the number of tasks in a scheduling window that have relative timing constraints with tasks in the next scheduling window. An online algorithm can evaluate these bounds in O(N) time.Unlike static approaches which assign fixed start times to tasks in the scheduling window, our approach allows us to flexibly manage the slack times at runtime without sacrificing the dispatchability of tasks. Also, a wider class of relative timing constraints can be imposed to the task set compared to the traditional approaches.     

Using a sparse promoting method in linear programming approximations to schedule parallel jobs

In this paper, we tackle the well‐known problem of scheduling a collection of parallel jobs on a set of processors either in a cluster or in a multiprocessor computer. For the makespan objective, that is, the completion time of the last job, this problem has been shown to be NP‐hard, and several heuristics have already been proposed to minimize the execution time. In this paper, we consider both rigid and moldable jobs. Our main contribution is the introduction of a new approach to the scheduling problem, based on the recent discoveries in the field of compressed sensing. In the proposed approach, all possible positions and shapes of the jobs are encoded into a matrix, and the scheduling is performed by selecting the best columns under natural constraints. Thus, the solution to the new scheduling formulation is naturally sparse, and we may use appropriate relaxations to achieve the optimization task in the quickest possible way. Among many possible relaxation strategies, we choose to minimize the ℓ_p‐quasi‐norm for p∈(0,1). Minimization of the ℓ_p‐quasi‐norm is implemented via a successive linear programming approximation heuristic. We propose several new algorithms based on this approach, and we assess their efficiency through simulations. The experiments show that the scheme outperforms the classic Largest Task First list based algorithm for scheduling small to medium instances but needs improvements to compete on larger numbers of jobs. Copyright © 2014 John Wiley & Sons, Ltd.     

基于深度强化学习的微电网在线优化调度

提出一种基于深度强化学习的微电网在线优化调度策略.针对可再生能源的随机性及复杂的潮流约束对微电网经济安全运行带来的挑战,以成本最小为目标,考虑微电网运行状态及调度动作的约束,将微电网在线调度问题建模为一个约束马尔可夫决策过程.为避免求解复杂的非线性潮流优化、降低对高精度预测信息及系统模型的依赖,设计一个卷积神经网络结构学习最优的调度策略.所提出的神经网络结构可以从微电网原始观测数据中提取高质量的特征,并基于提取到的特征直接产生调度决策.为了确保该神经网络产生的调度决策能够满足复杂的网络潮流约束,结合拉格朗日乘子法与soft actor-critic,提出一种新的深度强化学习算法来训练该神经网络.最后,为验证所提出方法的有效性,利用真实的电力系统数据进行仿真.仿真结果表明,所提出的在线优化调度方法可以有效地从数据中学习到满足潮流约束且具有成本效益的调度策略,降低随机性对微电网运行的影响.     

Fast scheduling of human-robot teams collaboration on synchronised production-logistics tasks in aircraft assembly

The deployment of human-robot teams (HRTs) promises to realise the potential of each team member regarding their distinct abilities and combines efficiency and flexibility in manufacturing operations. However, enabling effective coordination amongst collaborative tasks performed by humans and robots while ensuring safety and satisfying specific constraints is challenging. Motivated by real-world applications that Boeing and Airbus adopt HRTs in manufacturing operations, this paper investigates the allocating and coordinating of HRTs to support safe and efficient human-robot collaboration on synchronised production-logistics tasks in aircraft assembly. We connect the operations research and robotics communities by formulating the problem with precedence constraints, spatial constraints, temporal constraints, and synchronisation constraints that fits within the classic multi-robot task allocation (MRTA) category into a flexible job shop scheduling problem. Two exact approaches, including mixed-integer linear programming (MILP) and constraint programming (CP), are proposed to formulate and solve this problem. A benchmark set with 80 instances (e.g., small/medium-scale and large-scale instances) that corresponds to real dimensions of industrial problems with production tasks, subtasks, locations, deadlines, human worker eligibility and capacity, robot eligibility and capacity, material handling system capacity, and travel times is developed. Experimental evaluation with a total of 1200 independent tests on the benchmark set shows the superiority of the CP approach comparing the MILP approach for efficiently solving real-life scheduling problems of HRTs collaboration on synchronised production-logistics tasks in aircraft assembly.     

The capacitated multi-AGV scheduling problem with conflicting products: Model and a decentralized multi-agent approach

Automated guided vehicles (AGVs) are a key technology to facilitate flexible production systems in the context of Industry 4.0. This paper investigates an optimization model and a solution using a decentralized multi-agent approach for a new capacitated multi-AGV scheduling problem with conflicting products (CMASPCP) to take full advantage of AGVs. The novelty of the problem and our model lies in the introduction of AGV capacity constraints and constraints arising from conflicting products, i.e. products that cannot be transported together. As the new I4.0 paradigm tends towards decentralized control, we also present a decentralized multi-agent approach in which AGVs autonomously coordinate to solve the task. The performance of the proposed decentralized approach is compared to a mixed-integer linear programming model on a set of 110 problem instances with different sizes and degrees of complexity. The obtained results show that the proposed decentralized multi-agent approach is effective and competitive in terms of the solution quality and computational time.     

Capacitated lot sizing and sequence dependent setup scheduling: an iterative approach for integration

We consider here the lot sizing and scheduling problem in single-level manufacturing systems. The shop floor is composed of unrelated parallel machines with sequence dependent setup times. We propose an integer programming model embedding precise capacity information due to scheduling constraints in a classical lot-sizing model. We also propose an iterative approach to generate a production plan taking into account scheduling constraints due to changeover setup times. The procedure executes two decision modules per iteration: a lot-sizing module and a scheduling module. The capacitated lot-sizing problem is solved to optimality considering estimated data and aggregate information, and the scheduling problem is solved by a GRASP heuristic. In the proposed scheme the information flow connecting the two levels is managed in each iteration. We report a set of computational experiments and discuss future work.     

考虑运输能力限制的跨单元调度方法

工件在生产单元之间频繁转移产生了跨单元调度问题.本文结合我国装备制造业的生产实际,提出考虑运输能力的跨单元调度方法,设计了一种基于离散蜂群与决策块结构的超启发式算法.针对传统超启发式算法的局限性提出动态决策块策略, 同时改进传统蜂群算法的侦查蜂策略,使之具有更好的优化性能.实验表明,动态决策块具有比静态决策块更好的性能,算法在优化能力和计算效率的综合性能上优势显著,并且问题的规模越大,优势越明显.