SPT is optimally competitive for uniprocessor flow

We show that the Shortest Processing Time (SPT) algorithm is (Δ+1)/2-competitive for nonpreemptive uniprocessor total flow time with release dates, where Δ is the ratio between the longest and shortest job lengths. This is best possible for a deterministic algorithm and improves on the (Δ+1)-competitive ratio shown by Epstein and van Stee using different methods.     

Programming support and scheduling for communicating parallel tasks

Task-based programming models are beneficial for the development of parallel programs for several reasons. They provide a decoupling of the specification of parallelism from the scheduling and mapping to execution resources of a specific hardware platform, thus allowing a flexible and individual mapping. For platforms with a distributed address space, the use of parallel tasks, instead of sequential tasks, adds the additional advantage of a structuring of the program into communication domains that can help to reduce the overall communication overhead.     

Assigning real-time tasks to heterogeneous processors by applying ant colony optimization

The problem of determining whether a set of periodic tasks can be assigned to a set of heterogeneous processors without deadline violations has been shown, in general, to be NP-hard. This paper presents a new algorithm based on ant colony optimization (ACO) metaheuristic for solving this problem. A local search heuristic that can be used by various metaheuristics to improve the assignment solution is proposed and its time and space complexity is analyzed. In addition to being able to search for a feasible assignment solution, our extended ACO algorithm can optimize the solution by lowering its energy consumption. Experimental results show that both the prototype and the extended version of our ACO algorithm outperform major existing methods; furthermore, the extended version achieves an average of 15.8% energy saving over its prototype.     

Scheduling tasks of a parallel program in two-processor systems with use of cellular automata

In this paper, a cellular automaton (CA) is proposed as a tool for designing distributed scheduling algorithms for allocating parallel program tasks in multiprocessor systems. For this purpose, a program graph is considered as a CA containing elementary automata interacting locally according to some rules. In the first phase of the algorithm, effective rules for the CA are discovered by a genetic algorithm. In the second phase, the CA works as a distributed scheduler. In this phase, for any initial allocation of tasks in a multiprocessor system, the CA-based scheduler finds an allocation minimizing the total execution time of the program in a given system topology. The effectiveness of the proposed scheduling algorithm is shown for a number of program graphs scheduled in a two-processor system.     

Scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm in heterogeneous multiprocessors system

The scheduling problem for real-time tasks on multiprocessor is one of the NP-hard problems. This paper proposes a new scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm (mohGA) on heterogeneous multiprocessor environment. In solution algorithms, the genetic algorithm (GA) and the simulated annealing (SA) are cooperatively used. In this method, the convergence of GA is improved by introducing the probability of SA as the criterion for acceptance of new trial solution.     

Resource augmentation for uniprocessor and multiprocessor partitioned scheduling of sporadic real-time tasks

Although the earliest-deadline-first (EDF) policy is known to be optimal for preemptive real-time task scheduling in uniprocessor systems, the schedulability analysis problem has recently been shown to be $\mathit{co}\mathcal{NP}$ -hard. Therefore, approximation algorithms, and in particular, approximations based on resource augmentation have attracted a lot of attention for both uniprocessor and multiprocessor systems. Resource augmentation based approximations assume a certain speedup of the processor(s). Using the notion of approximate demand bound function (dbf), in this paper we show that for uniprocessor systems the resource augmentation factor is at most $\frac{2e-1}{e} \approx1.6322$ , where e is the Euler number. We approximate the dbf using a linear approximation when the analysis interval length of interest is larger than the relative deadline of the task. For identical multiprocessor systems with M processors and constrained-deadline task sets, we show that the deadline-monotonic partitioning (that has been proposed by Baruah and Fisher) with the approximate dbf leads to an approximation factor of $\frac{3e-1}{e}-\frac{1}{M} \approx 2.6322-\frac{1}{M}$ with respect to resource augmentation. We also show that the corresponding factor is $3-\frac{1}{M}$ for arbitrary-deadline task sets. The best known results so far were $3-\frac{1}{M}$ for constrained-deadline tasks and $4-\frac {2}{M}$ for arbitrary-deadline ones. Our tighter analysis exploits the structure of the approximate dbf directly and uses the processor utilization violations (which were ignored in all previous analysis) for analyzing resource augmentation factors. We also provide concrete input instances to show that the lower bound on the resource augmentation factor for uniprocessor systems—using the above approximate dbf—is 1.5, and the corresponding bound is 2.5 for identical multiprocessor systems with an arbitrary order of fitting and a large number of processors. Further, we also provide a polynomial-time approximation scheme (PTAS) to derive near-optimal solutions under the assumption that the ratio of the maximum relative deadline to the minimum relative deadline of tasks is a constant, which is a more relaxed assumption compared to the assumptions required for deriving such a PTAS in the past.     

大型工程项目任务多目标优化调度方法

提出了一种大型工程项目任务多目标优化调度方法。构建了一种以项目工期最小化、费用最小化及质量最大化为目标函数的多目标优化模型;针对模型的多变量、多约束、大组合量特点,提出了一种基于自适应变异和模拟退火思想的改进蚁群算法。将模型和算法在某大型工程项目任务调度中加以应用,验证了所提出的优化调度方法的正确性和有效性。     

基于Logistic回归模型的Hadoop本地任务调度优化算法*

当一个工作节点有多个本地任务可执行时,默认情况下,调度器都是按照任务被发现的先后顺序来进行执行,效率低下。针对于此,为了优化对本地任务的调度,提出了基于Logistic回归模型的Hadoop本地任务调度优化算法。首先,选取定义与任务相关的特征向量,然后基于Logistic回归的机器学习方式得到各向量的作用权值,将任务进行优先级排序,并通过过载规则不断更新模型。通过实验证明,提出的算法在改善map 任务的数据本地性的同时,降低了作业运行时间。     

Verification and optimization of a PLC control schedule

We report on the use of model checking techniques for both the verification of a process control program and the derivation of optimal control schedules. Most of this work has been carried out as part of a case study for the EU VHS project (Verification of Hybrid Systems), in which the program for a Programmable Logic Controller (PLC) of an experimental chemical plant had to be designed and verified. The original intention of our approach was to see how much could be achieved here using the standard model checking environment of SPIN/Promela. As the symbolic calculations of real-time model checkers can be quite expensive it is interesting to try and exploit the efficiency of established non-real-time model checkers like SPIN in those cases where promising work-arounds seem to exist. In our case we handled the relevant real-time properties of the PLC controller using a time-abstraction technique; for the scheduling we implemented in Promela a so-called variable time advance procedure . To compare and interpret the results we carried out the same case study with the aid of the real-time model checker Uppaal, enhanced with facilities for cost-guided state space exploration. Both approaches proved sufficiently powerful to verify the design of the controller and/or derive (time-)optimal schedules within reasonable time and space requirements. Published online: 2 October 2002 The work reported here was carried out while the second and third authors were employed by the Computer Science Department of the University of Nijmegen, Netherlands. The second author was supported by an NWO postdoc grant, the third author by an NWO PhD grant, and both were supported by the EU LTR project VHS (Project No. 26270).     

Scheduling dependent tasks on identical machines using a novel heuristic criterion: A robotic computation example

The problem of schedulingn dependent tasks, with arbitrary processing times, onm identical machines so as to minimize the makespan criterion is considered. Since this problem is NP-hard in the strong sense, it can be solved only suboptimally using heuristic approaches. Two new heuristic algorithms (dispatching rules), namely MVT/MISF and DMVT/MISF algorithms, for this problem are proposed. These algorithms are then used, together with the existing ones CP/MISF and DHLF/MISF, as a dispatching rule base of a new adaptively weighted combinatorial dispatching (AWCD) rule. This combinatorial dispatching rule has a superior behaviour compared to simple dispatching rules. Extended experimentation with these algorithms supports this argument. Here a representative robotic dynamics computation example is included. In addition, some empirical rules are derived and proposed for the selection of a simple dispatching rule (heuristic) if such a selection is required, for each particular input data set. These methods, as well as the existing optimal algorithms for special solvable cases of the considered problem, have been integrated in a decision support system (DSS).     

Nonlinear inverse optimization approach for determining the weights of objective function in standing reach tasks

This paper presents a nonlinear inverse optimization approach to determine the weights for the joint displacement function in standing reach tasks. This inverse optimization problem can be formulated as a bi-level highly nonlinear optimization problem. The design variables are the weights of a cost function. The cost function is the weighted summation of the differences between two sets of joint angles (predicted posture and the actual standing reach posture). Constraints include the normalized weights within limits and an inner optimization problem to solve for joint angles (predicted standing reach posture). The weight linear equality constraints, obtained through observations, are also implemented in the formulation to test the method. A 52 degree-of-freedom (DOF) human whole body model is used to study the formulation and visualize the prediction. An in-house motion capture system is used to obtain the actual standing reach posture. A total of 12 subjects (three subjects for each percentile in stature of 5th percentile female, 50th percentile female, 50th percentile male and 95th percentile male) are selected to run the experiment for 30 tasks. Among these subjects one is Turkish, two are Chinese, and the rest subjects are Americans. Three sets of weights for the general standing reach tasks are obtained for the three zones by averaging all weights in each zone for all subjects and all tasks. Based on the obtained sets of weights, the predicted standing reach postures found using the direct optimization-based approach have good correlation with the experimental results. Sensitivity of the formulation has also been investigated in this study. The presented formulation can be used to determine the weights of cost function within any multi-objective optimization (MOO) problems such as any types of posture prediction and motion prediction.     

具有模糊多目标的网格任务调度算法

在异构的网格计算平台上,网格中有用户、资源管理员、组织管理者等实体,这些实体对网格的管理、使用、维护、安全性、可靠性等目标都提出了要求,并且这些目标有时是不可量化的。针对具有模糊多目标网格计算的任务调度问题,提出模糊多目标网格任务调度模型,使用模糊化等式对多目标进行模糊处理,给出求解该模型的模糊化定理,并对该定理进行证明。利用差分优化算法无需目标函数连续可微的特点,提出使用模糊差分优化算法完成模糊多目标的网格任务调度。实验结果表明,模糊差分优化算法较现有算法在执行时间上处于劣势,但在可靠性、安全性和丢失任务数三个指标上要优于现有算法。     

A formal mapping-based approach for distributed schedule coordination on projects

Construction projects involve a large number of participants with overlapping scope of work. Coordination of their activities is usually an iterative manual task undertaken by a general contractor that is often unaware of the detailed constraints of other participants. Project schedules play a key role in this coordination and form the backbone of almost all current approaches to process coordination. However, no single schedule represents the perspective of all participants involved in a project. Rather, each participant keeps in some manner a schedule for its own activities, resulting in multiple schedules that need to be coordinated. The current literature does not support simultaneous reasoning across multiple distributed, overlapping schedules. This paper introduces constructs to formalize the integration of participants’ overlapping schedules that represent the same project tasks, but use a different set breakdown structures and level of detail. Implementation of these constructs allows linking of the master schedule to the other participants’ schedules thereby representing the perspectives of all project participants. This integrated perspective facilitates initial schedule coordination and allows rapid identification of schedule conflicts in response to any schedule changes.     

Heuristics for scheduling file-sharing tasks on heterogeneous systems with distributed repositories

We consider the problem of scheduling an application on a computing system consisting of heterogeneous processors and data repositories. The application consists of a large number of file-sharing otherwise independent tasks. The files initially reside on the repositories. The processors and the repositories are connected through a heterogeneous interconnection network. Our aim is to assign the tasks to the processors, to schedule the file transfers from the repositories, and to schedule the executions of tasks on each processor in such a way that the turnaround time is minimized. We propose a heuristic composed of three phases: initial task assignment, task assignment refinement, and execution ordering. We experimentally compare the proposed heuristics with three well-known heuristics on a large number of problem instances. The proposed heuristic runs considerably faster than the existing heuristics and obtains 10–14% better turnaround times than the best of the three existing heuristics.     

A 10-year assessment of information and communication technology tasks required in undergraduate agriculture courses

This study sought to assess required information and communication technology (ICT) tasks in selected undergraduate agriculture courses in a land-grant university during a 10-year period. Selected agriculture faculty members in the fall 1999 (n = 63), 2004 (n = 55), and 2009 (n = 64) semesters were surveyed to determine the ICT tasks they required of students. There were significant (p < .05) increases in the number of required Internet and electronic mail tasks between 1999 and 2009; but no significant changes in the number of word processing, computer graphics, spreadsheet, database, or miscellaneous ICT tasks required over the period. In 1999, three specific tasks (receive electronic mail, search the Internet, and type a lab or project report) were required in more than 50% of courses; in 2009, these three tasks plus three additional tasks (send electronic mail, submit assignments as attached electronic mail files, and use Blackboard^© to acquire course information) were required in a majority of courses. Faculty with higher levels of self-perceived ICT skills and those teaching higher-level courses tended to require larger and more diverse sets of ICT tasks than other faculty. Course level explained the largest proportion of unique variance in the number of required spreadsheet, word processing, computer graphics, and miscellaneous ICT tasks. Self-perceived ICT skills and course level explained approximately equal amounts of the unique variance in total ICT tasks required. Both the quantity and complexity of ICT in undergraduate agriculture courses should be increased.     

A simulation-based scheduling system for real-time optimization and decision making support

This paper presents an industrial application of simulation-based optimization (SBO) in the scheduling and real-time rescheduling of a complex machining line in an automotive manufacturer in Sweden. Apart from generating schedules that are robust and adaptive, the scheduler must be able to carry out rescheduling in real time in order to cope with the system uncertainty effectively. A real-time scheduling system is therefore needed to support not only the work of the production planner but also the operators on the shop floor by re-generating feasible schedules when required. This paper describes such a real-time scheduling system, which is in essence a SBO system integrated with the shop floor database system. The scheduling system, called OPTIMISE scheduling system (OSS), uses real-time data from the production line and sends back expert suggestions directly to the operators through Personal Digital Assistants (PDAs). The user interface helps in generating new schedules and enables the users to easily monitor the production progress through visualization of production status and allows them to forecast and display target performance measures. Initial results from this industrial application have shown that such a novel scheduling system can help both in improving the line throughput efficiently and simultaneously supporting real-time decision making.     

Quantitative postural load assessment for whole body manual tasks based on perceived discomfort

Many Korean workers are exposed to repetitive manual tasks or prolonged poor working postures that are closely related to back pain or symptoms of musculoskeletal disorders. Workers engage in tasks that require not only handling of heavy materials, but also assuming prolonged or repetitive non-neutral work postures. Poor work postures that have been frequently observed in the workplaces of shipbuilding shops, manufacturing plants, automobile assembly lines and farms often require prolonged squatting, repetitive arm raising and wrist flexion and simultaneous trunk flexion and lateral bending. In most manufacturing industries, workers have to assume improper work postures repetitively, several hundreds of times per day depending on daily production rate. A series of psychophysical laboratory experiments were conducted to evaluate the postural load at various joints. A postural load assessment system was then developed based on a macro-postural classification scheme. The classification scheme was constructed based on perceived discomfort for various joint motions as well as previous research outcomes. On the basis of the perceived discomfort, postural stress levels for the postures at individual joints were also defined by a ratio scale to the standing neutral posture. Laboratory experiments simulating automobile assembly tasks were carried out to investigate the relationship between body-joint and whole-body discomfort. Results showed a linear relationship between the two types of discomfort, with the shoulder and low back postures being the dominant factor in determining the whole body postural stresses. The proposed method was implemented into a computer software program in order to automate the procedure of analysing postural load and to enhance usability and practical applicability.     

Intermediate-level vision tasks on a memory array architecture

With the fast advances in the area of computer vision and robotics there is a growing need for machines that can understand images at very high speed. A conventional von Neumann computer is not suitable for this purpose, because it takes a tremendous amount of time to solve most typical image analysis problems. Thus, it is now imperative to study computer vision in a parallel processing framework in order to reduce the processing time. In this paper we demonstrate the applicability of a simple memory array architecture to some intermediate-level computer vision tasks. This architecture, called theAccess Constrained Memory Array Architecture (ACMAA) has a linear array of processors which concurrently access distinct rows or columns of an array of memory modules. Because of its efficient local and global communication capabilities ACMAA is well suited for low-level as well as intermediate-level vision tasks. This paper presents algorithms for connected component labeling, determination of area, perimeter and moments of a labeled region, convex hull of a region, and Hough transform of an image. ACMAA is well suited to an efficient hardware implementation because it has a modular structure, simple interconnect and limited global control.