Genetic Algorithm Based Scheduling of Meta-Tasks with Stochastic Execution Times in Heterogeneous Computing Systemst1

In this study, we address the meta-task scheduling problem in heterogeneous computing (HC) systems, which is to find a task assignment that minimizes the schedule length of a meta-task composed of several independent tasks with no data dependencies. The fact that the meta-task scheduling problem in HC systems is NP-hard has motivated the development of many heuristic scheduling algorithms. These heuristic algorithms, however, neglect the stochastic nature of task execution times in an attempt to minimize a deterministic objective function, which is the maximum of the expected values of machine loads. Contrary to existing heuristics, we account for this stochastic nature by modeling task execution times as random variables. We, then, formulate a stochastic scheduling problem where the objective is to minimize the expected value of the maximum of machine loads. We prove that this new objective is underestimated by the deterministic objective function and that an optimal task assignment obtained with respect to the deterministic objective function could be inefficient in a real computing platform. In order to solve the stochastic scheduling problem posed, we develop a genetic algorithm based scheduling heuristic. Our extensive simulation studies show that the proposed genetic algorithm can produce better task assignments as compared to existing heuristics. Specifically, we observe a performance improvement on the relative cost heuristic (M.-Y. Wu and W. Shu, A high-performance mapping algorithm for heterogeneous computing systems, in: Int. Parallel and Distributed Processing Symposium, San Francisco, CA, April 2001) by up to 61%.     

Interactive computer aided shift scheduling

This paper starts with a discussion of computer aided shift scheduling. After a brief review of earlier approaches, two conceptualizations of this field are introduced: First, shift scheduling as a field that ranges from extremely stable rosters at one pole to rather market-like approaches on the other pole. Unfortunately, already small alterations of a scheduling problem (e.g., the number of groups, the number of shifts) may call for rather different approaches and tools. Second, their environment shapes scheduling problems and scheduling has to be done within idiosyncratic organizational settings. This calls for the amalgamation of scheduling with other tasks (e.g., accounting) and for reflections whether better solutions might become possible by changes in the problem definition (e.g., other service levels, organizational changes). Therefore shift scheduling should be understood as a highly connected problem. Building upon these two conceptualizations, a few examples of software that ease scheduling in some areas of this field are given and future research questions are outlined.     

A Classification for Hoist Scheduling Problems

Electroplating lines are totally automated manufacturing systems that are used to cover parts with a coat of metal. They consist of a set of tanks between which the parts to be treated are transported by one or several hoists. Scheduling the movements of these hoists is commonly called a hoist scheduling problem (HSP) in the literature. But the assumptions and constraints that must be taken into account greatly depend on the production environment (physical system, manufacturing specifications, and management policies). Consequently, there exist several classes of HSPs. The systematic frameworks usually used to classify deterministic scheduling problems do not allow distinguishing between these various kinds of HSPs. Therefore, identifying the scope of each published work and comparing the various proposed scheduling methods turn out to be difficult. Thus, this article presents notation for scheduling problems in electroplating systems, to make the specification of problem types and the identification of studied problem instances easier. An associated typology gives a survey of the literature and demonstrates the usefulness of the proposed classification scheme.     

Intelligent scheduling of FMSs with inductive learning capability using neural networks

With the growing uncertainty and complexity in the manufacturing environment, most scheduling problems have been proven to be NP-complete and this can degrade the performance of conventional operations research (OR) techniques. This article presents a system-attribute-oriented knowledge-based scheduling system (SAOSS) with inductive learning capability. With the rich heritage from artificial intelligence (AI), SAOSS takes a multialgorithm paradigm which makes it more intelligent, flexible, and suitable than others for tackling complicated, dynamic scheduling problems. SAOSS employs an efficient and effective inductive learning method, a continuous iterative dichotomister 3 (CID3) algorithm, to induce decision rules for scheduling by converting corresponding decision trees into hidden layers of a self-generated neural network. Connection weights between hidden units imply the scheduling heuristics, which are then formulated into scheduling rules. An FMS scheduling problem is also given for illustration. The scheduling results show that the system-attribute-oriented knowledge-based approach is capable of addressing dynamic scheduling problems.     

Two game-based solution concepts for a two-agent scheduling problem

In the current research papers on multi-agent (multi-person) scheduling, a person’s objective function is always considered as a cost function on scheduling, whereas a cooperative profit function is defined to serve as his objective one in this paper. In the two-person scheduling problem addressed in this paper, the two persons jointly order a common operational time interval of a single machine. Each person needs to process a set of his own jobs in that time window. The same objective function of each person still relies on the sequence of all the jobs of both persons since each part of the function is determined by some given parameters except one part assumed to be a given multiple of the total completion time of his own jobs. The two persons have to negotiate a job sequence and determine the (related) final solution on cooperative profit allocation. Such a two-person scheduling problem is essentially a cooperative game. An algorithm is designed to yield the cooperative-profit-based Pareto efficient solution set acting as the first game-based solution concept in this paper. The parallelized version of the algorithm is also developed. The second game-based solution concept is the Shapley value appropriate for the above cooperative-game situation on two-person scheduling. Several instances are presented and analyzed to reveal the necessity to employ the two solution concepts together.     

An approach to real-time flexible scheduling

Two types of flexibility are important in manufacturing scheduling in general and in real-time scheduling in particular. The first is flexibility with respect to the criteria that can be considered in the scheduling decisions. The second is flexibility with respect to the trade-off between decision quality and computational burden: that is, the ability to arrive at a solution that makes maximum use of theavailable computational capacity and computation time. This paper describes a procedure which meets the above requirements. The procedure is justified using a theoretical analysis based on probability. Experimental results of the procedure's performance are also presented. The results show that random selection (which is used in the procedure) can play a useful role in the real-time scheduling problem.     

A study of nurse scheduling in Japan

Scheduling nurses to staff shifts is a major problem in hospitals. The necessity of maintaining a certain level of service and skill in the makeup of every shift, while balancing the workload among the nurses involved, is incredibly difficult. It is often impossible to develop a schedule which satisfies all the requirements despite the time and resources spent in the effort. This paper summarizes all our published research on nurse scheduling to date. The difficulties realized by our two investigations in Japan are shown first, together with a resulting scheduling problem. The nurse scheduling model based on the results is then described. In this model, all constraints are divided into two essentially different types; that which maintains a certain level of skill for each shift ('shift constraints') and that which concerns the workload for each nurse ('nurse constraints'). By classifying the constraints in this manner, we can determine what is affected by a specific constraint when the constraint is not satisfied. We developed efficient algorithms while taking advantage of the structure of this model. Finally, it is shown that our algorithm can solve this problem for a 2-shift system efficiently.     

An integrated scheduling and control model for multi-mode projects

In today’s highly competitive uncertain project environments, it is of crucial importance to develop analytical models and algorithms to schedule and control project activities so that the deviations from the project objectives are minimized. This paper addresses the integrated scheduling and control in multi-mode project environments. We propose an optimization model that models the dynamic behavior of projects and integrates optimal control into a practically relevant project scheduling problem. From the scheduling perspective, we address the discrete time/cost trade-off problem, whereas an optimal control formulation is used to capture the effect of project control. Moreover, we develop a solution algorithm for two particular instances of the optimal project control. This algorithm combines a tabu search strategy and nonlinear programming. It is applied to a large scale test bed and its efficiency is tested by means of computational experiments. To the best of our knowledge, this research is the first application of optimal control theory to multi-mode project networks. The models and algorithms developed in this research are targeted as a support tool for project managers in both scheduling and deciding on the timing and quantity of control activities.     

Failure-aware workflow scheduling in cluster environments

The goal of workflow application scheduling is to achieve minimal makespan for each workflow. Scheduling workflow applications in high performance cluster environments is an NP-Complete problem, and becomes more complicated when potential resource failures are considered. While more research on failure prediction has been witnessed in recent years to improve system availability and reliability, very few of them attack the problem in the context of workflow application scheduling. In this paper, we study how a workflow scheduler benefits from failure prediction and propose FLAW, a failure-aware workflow scheduling algorithm. We propose two important definitions on accuracy, Application Oblivious Accuracy (AOA) and Application Aware Accuracy (AAA), from the perspectives of system and scheduling respectively, as we observe that the prediction accuracy defined conventionally imposes different performance implications on different applications and fails to measure how that improves scheduling effectiveness. The comprehensive evaluation results using real failure traces show that FLAW performs well with practically achievable prediction accuracy by reducing the average makespan, the loss time and the number of job rescheduling.     

A New Cyclic Scheduling Algorithm for Flexible Manufacturing Systems

Flexible manufacturing system control is an NP-hard problem. A cyclic approach has been demonstrated to be adequate for an infinite scheduling problem because of maximal throughput reachability. However, it is not the only optimization criterion in general. In this article we consider the minimization of the work in process (WIP) as an economical and productivity factor. We propose a new cyclic scheduling algorithm giving the maximal throughput (a hard constraint) while minimizing WIP. This algorithm is based on progressive operations placing. A controlled beam search approach has been developed to determine at each step the schedule of the next operations. After presenting the main principles of the algorithm, we compare our approach to several most known cyclic scheduling algorithms using a significant existing example from the literature.     

Efficient push-based packet scheduling for Peer-to-Peer live streaming

Content scheduling is a key component of Peer-to-Peer (P2P) networks. The problem is how to schedule the content delivery to the children peers with multiple parents to improve the overall performance of the systems. The challenge is to design a scheme with low delay and low bandwidth utilization. Most of recent works propose pull-based schemes, whose processes for periodically advertising and requesting on per-packet basic lead to long delay. However, long playback delay is undesirable for live streaming and TV shows. In this paper, we formulate the scheduling problems as to minimize the playback delay due to scheduling. To solve the problem and address the packet redundancy and disorder packet arrival issues, we propose a novel push-based scheme. In our scheme, parents push packets to their children in a given interval pattern as soon as the packets are received, and children feed back network condition changes with an interval pattern when necessary. The scheme eliminates the processes of buffer advertising and packet requesting, and reduces control traffic, delivery delay and playback delay much more than the pull-based schemes. We provide an efficient scheduling algorithm and its implementation for simulation. The simulation results show that our scheme outperforms other pull-based schemes significantly.     

Hybrid FMS control architectures based on holonic principles

The escalation in processor technologies and the corresponding reduction in costs have enabled alternative FMS control architectures to be developed without the restrictions of “fixed machine controller boundaries”. These new architectures can be based upon the use of intelligent servo axes, which are desccribed in this article, as flexible numerical control (FNC). In current parlance, the FNC is a “part movement holon” within a manufacturing cell. The control architectures that can be derived from the FNC concept are referred to as hybrid architectures and share the emerging attributes of holonics. This article details the problems that arise in the scheduling and control of FMSs in the light of hybrid control architectures. A number of traditional scheduling approaches have been devised to cope with the scheduling of parts to discrete machines, but the problem here is to ascribe the processing (machining) of part features to axis groups. This article documents how two research programs, undertaken at the CIM Centre at Swinburne University of Technology in Hawthorn, Victoria, Australia, have endeavored to address the problem of hybrid architectures and their associated scheduling.     

A job-shop scheduling approach for optimising sugarcane rail operations

The sugarcane transport system is very complex and uses a daily schedule, consisting of a set of locomotives runs, to satisfy the requirements of the mill and harvesters. The total cost of sugarcane transport operations is very high; over 35% of the total cost of sugarcane production in Australia is incurred in cane transport. Producing efficient schedules for sugarcane transport can reduce the cost and limit the negative effects that this system can have on the raw sugar production system. In this paper, the sugarcane rail operations are formulated as a blocking job shop scheduling problem. A mixed integer programming approach is used to formulate the shop job scheduling problem. Mixed integer programming and constraint programming search techniques are integrated for solving the problem. A case study is solved to test the approach.     

More reliable protein NMR peak assignment via improved 2-interval scheduling.

Protein NMR peak assignment refers to the process of assigning a group of "spin systems" obtained experimentally to a protein sequence of amino acids. The automation of this process is still an unsolved and challenging problem in NMR protein structure determination. Recently, protein NMR peak assignment has been formulated as an interval scheduling problem (ISP), where a protein sequence P of amino acids is viewed as a discrete time interval I (the amino acids on P one-to-one correspond to the time units of I), each subset S of spin systems that are known to originate from consecutive amino acids from P is viewed as a "job" j(s), the preference of assigning S to a subsequence P of consecutive amino acids on P is viewed as the profit of executing job j(s) in the subinterval of I corresponding to P, and the goal is to maximize the total profit of executing the jobs (on a single machine) during I. The interval scheduling problem is max SNP-hard in general; but in the real practice of protein NMR peak assignment, each job j(s) usually requires at most 10 consecutive time units, and typically the jobs that require one or two consecutive time units are the most difficult to assign/schedule. In order to solve these most difficult assignments, we present an efficient 13/7-approximation algorithm for the special case of the interval scheduling problem where each job takes one or two consecutive time units. Combining this algorithm with a greedy filtering strategy for handling long jobs (i.e., jobs that need more than two consecutive time units), we obtain a new efficient heuristic for protein NMR peak assignment. Our experimental study shows that the new heuristic produces the best peak assignment in most of the cases, compared with the NMR peak assignment algorithms in the recent literature. The above algorithm is also the first approximation algorithm for a nontrivial case of the well-known interval scheduling problem that breaks the ratio 2 barrier.     

Medium term planning of biopharmaceutical manufacture using mathematical programming

Regulatory pressures and capacity constraints are forcing the biopharmaceutical industry to consider employing multiproduct manufacturing facilities running on a campaign basis. The need for such flexible and cost-effective manufacture poses a significant challenge for planning and scheduling. This paper reviews the problem of planning and scheduling of biopharmaceutical manufacture and presents a methodology for the planning of multiproduct biopharmaceutical manufacturing facilities. The problem is formulated as a mixed integer linear program (MILP) to represent the relevant decisions required within the planning process and is tested on two typical biopharmaceutical industry planning problems. The proposed formulation is compared with an industrial rule based approach, which it outperforms in terms of profitability. The results indicate that the developed formulation offers an effective representation of the planning problem and would be a useful decision tool for manufacturers in the biopharmaceutical industry particularly at times of limited manufacturing capacity.     

MIP formulations for an application of project scheduling in human resource management

In the literature, various discrete-time and continuous-time mixed-integer linear programming (MIP) formulations for project scheduling problems have been proposed. The performance of these formulations has been analyzed based on generic test instances. The objective of this study is to analyze the performance of discrete-time and continuous-time MIP formulations for a real-life application of project scheduling in human resource management. We consider the problem of scheduling assessment centers. In an assessment center, candidates for job positions perform different tasks while being observed and evaluated by assessors. Because these assessors are highly qualified and expensive personnel, the duration of the assessment center should be minimized. Complex rules for assigning assessors to candidates distinguish this problem from other scheduling problems discussed in the literature. We develop two discrete-time and three continuous-time MIP formulations, and we present problem-specific lower bounds. In a comparative study, we analyze the performance of the five MIP formulations on four real-life instances and a set of 240 instances derived from real-life data. The results indicate that good or optimal solutions are obtained for all instances within short computational time. In particular, one of the real-life instances is solved to optimality. Surprisingly, the continuous-time formulations outperform the discrete-time formulations in terms of solution quality.     

Enriching the tactical network design of express service carriers with fleet scheduling characteristics

Express service carriers provide time-guaranteed deliveries of parcels via a network consisting of nodes and hubs. In this, nodes take care of the collection and delivery of parcels, and hubs have the function to consolidate parcels in between the nodes. The tactical network design problem assigns nodes to hubs, determines arcs between hubs, and routes parcels through the network. Afterwards, fleet scheduling creates a schedule for vehicles operated in the network. The strong relation between flow routing and fleet scheduling makes it difficult to optimise the network cost. Due to this complexity, fleet scheduling and network design are usually decoupled. We propose a new tactical network design model that is able to include fleet scheduling characteristics (like vehicle capacities, vehicle balancing, and drivers’ legislations) in the network design. The model is tested on benchmark data based on instances from an express provider, resulting in significant cost reductions.     

Job scheduling and management of wearing tools with stochastic tool lifetimes

The problem of scheduling jobs using wearing tools is studied. Tool wearing is assumed to be stochastic and the jobs are processed in one machining centre provided with a limited capacity tool magazine. The aim is to minimize the expected average completion time of the jobs by choosing their processing order and tool management decisions wisely. All jobs are available at the beginning of the planning period. This kind of situation is met in production planning of CNC-machines. Previous studies concerning this problem have either assumed deterministic wearing for the tools or omitted the wearing completely. In our formulation of the problem, tool wearing is stochastic and the problem becomes very hard to solve analytically. A heuristic based on genetic algorithms is therefore given for the joint problem of job scheduling and tool management. The algorithm searches the most beneficial job sequence when the tool management decisions are made by a removal rule taking into account the future planned usage of the tools. The cost of each job sequence is evaluated by simulating the job processing. Empirical tests with heuristics indicate that by taking the stochastic information into account, one can reduce the average job processing time considerably.     

Scheduling parallel machines with major and minor setup times

This article discusses the problem of scheduling a large set of parts on an FMS so as to minimize the total completion time. Here, the FMS consists of a set of parallel identical machines. Setup time is incurred whenever a machine switches from one type of part to another. The setup time may be large or small depending on whether or not the two part types belong to the same family. This article describes a fast heuristic for this scheduling problem and derives a lower bound on the optimal solution. In computational tests using random data and data from an IBM card test line, the heuristic archieves nearly optimal schedules.     

Integrated production and distribution planning for perishable food products

Certain types of food, such as catering foods, decay very rapidly. This paper investigates how the quality of such foods can be improved by shortening the time interval between production and delivery. To this end, we develop an approach that integrates short-term production and distribution planning in an iterative scheme. Further, an aggregation scheme is developed as the interface between the production scheduling and distribution problem. The production scheduling problem is solved through an MILP modeling approach which is based on a block planning formulation. Our implementation shows promising results, elaborated in a numerical investigation, which recollects the real settings of a catering company located in Denmark.