Approximation algorithms for multi-agent scheduling to minimize total weighted completion time

We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time Approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio.     

Scheduling parallel jobs to minimize the makespan

We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We prove that the makespan of any nonpreemptive list-schedule is within a factor of 2 of the optimal preemptive makespan. This gives the best-known approximation algorithms for both the preemptive and the nonpreemptive variant of the problem. We also show that no list-scheduling algorithm can achieve a better performance guarantee than 2 for the nonpreemptive problem, no matter which priority list is chosen. List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.     

A multiobjective hybrid ant colony optimization approach applied to the assignment and scheduling problem

The assignment and scheduling problem is inherently multiobjective. It generally involves multiple conflicting objectives and large and highly complex search spaces. The problem allows the determination of an efficient allocation of a set of limited and shared resources to perform tasks, and an efficient arrangement scheme of a set of tasks over time, while fulfilling spatiotemporal constraints. The main objective is to minimize the project makespan as well as the total cost. Finding a good approximation set is the result of trade‐offs between diversity of solutions and convergence toward the Pareto‐optimal front. It is difficult to achieve such a balance with NP‐hard problems. In this respect, and in order to efficiently explore the search space, a hybrid bidirectional ant‐based approach is proposed in this paper, which is an improvement of a bi‐colony ant‐based approach. Its main characteristic is that it combines a solution construction developed for a more complicated problem with a Pareto‐guided local search engine.     

Engineering an efficient two‐phase local search algorithm for the co‐rotating twin‐screw extruder configuration problem

The twin‐screw configuration problem arises during polymer extrusion and compounding. It consists in defining the location of a set of pre‐defined screw elements along the screw axis in order to optimize different, typically conflicting objectives. In this paper, we present a simple yet effective stochastic local search (SLS) algorithm for this problem. Our algorithm is based on efficient single‐objective iterative improvement algorithms, which have been developed by studying different neighborhood structures, neighborhood search strategies, and neighborhood restrictions. These algorithms are embedded into a variation of the two‐phase local search framework to tackle various bi‐objective versions of this problem. An experimental comparison with a previously proposed multi‐objective evolutionary algorithm shows that a main advantage of our SLS algorithm is that it converges faster to a high‐quality approximation to the Pareto front.     

Coordination mechanisms for decentralized parallel systems

On resource sharing platforms, the execution of the jobs submitted by users is usually controlled by a centralized global scheduler. It determines efficient schedules regarding some common objective function that all organizations agree with (for instance, maximizing the utilization of the entire platform). However, in practice, each organization is mostly interested in the performance obtained for its own jobs. We study the price that the collectivity must pay in order to allow independence to selfish, self‐governing organizations, so they can choose the best schedules for their own jobs. In other words, we are interested in analyzing the costs on the global performance inflicted by the decentralization of scheduling policies. We present a game‐theoretic model for the problem and the associated coordination mechanisms developed to reduce the cost of the decentralization of the decision‐making process. The main contribution is to show (in theory and practice) how to devise pure Nash equilibria configurations for every instance of the problem and to prove that the price paid by the collectivity depends on the local scheduling policy and on the characteristics of the workload executed on such platforms. Copyright © 2014 John Wiley & Sons, Ltd.     

On multiprocessor temperature-aware scheduling problems

We study temperature-aware scheduling problems under the model introduced in [Chrobak et al. AAIM 2008], where unit-length jobs of given heat contributions and common release dates are to be scheduled on a set of parallel identical processors. We consider three optimization criteria: makespan, maximum temperature and (weighted) average temperature. On the positive side, we present polynomial time approximation algorithms for the minimization of the makespan and the maximum temperature, as well as, optimal polynomial time algorithms for minimizing the average temperature and the weighted average temperature. On the negative side, we prove that there is no approximation algorithm of absolute ratio $\frac{4}{3}-\epsilon $ for the problem of minimizing the makespan for any $\epsilon > 0$ , unless $\mathcal{P}=\mathcal{NP}$ .     

Refinements on an enumeration scheme for solving a pattern sequencing problem

We introduce some refinements on a branch‐ and bound‐scheme for solving the minimization of open stack problem (MOSP). After representing the MOSP as a graph traversing problem, we attempt to divide the graph into parts aiming to solve the resulting subgraphs independently in order to reduce the search in the branching scheme. Subgraphs with special topologies (such as trees) are solved exactly using polynomial time algorithms. The branching scheme is applied only to the parts that are ‘complex’. The refinements introduced produce substantial savings in computational time when the MOSP graph presents some special structures. Limited computational results are presented.     

Multiobjective model for solving resource‐leveling problem with discounted cash flows

Nowadays, executers are struggling to improve the economic and scheduling situation of projects. Construction scheduling techniques often produce schedules that cause undesirable resource fluctuations that are inefficient and costly to implement on site. The objective of the resource‐leveling problem is to reduce resource fluctuation related costs (hiring and firing costs) without violating the project deadline. In this article, minimizing the discounted costs of resource fluctuations and minimizing the project makespan are considered in a multiobjective model. The problem is formulated as an integer nonlinear programming model, and since the optimization problem is NP‐hard, we propose multiobjective evolutionary algorithms, namely nondominated sorting genetic algorithm‐II (NSGA‐II), strength Pareto evolutionary algorithm‐II (SPEA‐II), and multiobjective particle swarm optimization (MOPSO) to solve our suggested model. To evaluate the performance of the algorithms, experimental performance analysis on various instances is presented. Furthermore, in order to study the performance of these algorithms, three criteria are proposed and compared with each other to demonstrate the strengths of each applied algorithm. To validate the results obtained for the suggested model, we compared the results of the first objective function with a well‐tuned genetic algorithm and differential algorithm, and we also compared the makespan results with one of the popular algorithms for the resource constraints project scheduling problem. Finally, we can observe that the NSGA‐II algorithm presents better solutions than the other two algorithms on average.     

Lower bound algorithms for multiprocessor task scheduling with ready times

In this paper, we deal with multiprocessor task scheduling with ready times and prespecified processor allocation. We consider an on‐line scenario where tasks arrive over time, and, at any point in time, the scheduler only has knowledge of the released tasks. An application of this problem arises in wavelength division multiplexing broadcasting where the main future will be in the so‐called one‐to‐many transmission. We propose algorithms to find lower bounds of the minimum makespan, and present experiments on various scenarios.     

改进布谷鸟搜索算法求解批量流水线调度问题

针对以最大完工时间为目标的批量流水线调度问题,提出一种改进的布谷鸟搜索算法．该算法采用排序规则的编码方式,将连续个体值的布谷鸟搜索算法直接应用于离散的调度问题．其次,在布谷鸟搜索算法的基础上,一个简单而有效的局部搜索用于批量流水线调度问题的探索．仿真实验表明所提出算法的可行性和有效性．     

求解批量流水线调度问题的和声算法

针对以最大完工时间和总流经时间为目标的批量流水线调度问题,提出了改进的和声调度算法。该算法采用基于最大位置值(LPV)规则的编码方式,使具有连续性质的和声算法应用于求解调度问题;提出新的初始化方法,应用了多种群进化的思想更新和声库,并结合和声算法和模拟退火算法各自的特点,给出了两种混合调度算法。仿真实验表明所提算法的可行性和有效性。     

Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem

This paper deals with the joint production and maintenance scheduling problem according to a new bi-objective approach. This method allows the decision maker to find compromise solutions between the production objectives and maintenance ones. Reliability models are used to take into account the maintenance aspect of the problem. The aim is to simultaneously optimize two criteria: the minimization of the makespan for the production part and the minimization of the system unavailability for the maintenance side. Two decisions are taken at the same time: finding the best assignment of n jobs to m machines in order to minimize the makespan and deciding when to carry out the preventive maintenance actions in order to minimize the system unavailability. The maintenance actions numbers as well as the maintenance intervals are not fixed in advance. Two evolutionary genetic algorithms are compared to find an approximation of the Pareto-optimal front in the parallel machine case. On a large number of test instances (more than 5000), the obtained results are promising.     

Multiobjective pseudo‐variable neighborhood descent for a bicriteria parallel machine scheduling problem with setup time

A multiobjective variable neighborhood descent (VND) based heuristic is developed to solve a bicriteria parallel machine scheduling problem. The problem considers two objectives, one related to the makespan and the other to the flow time, where the setup time depends on the sequence, and the machines are identical. The heuristic has a set of neighborhood structures based on swap, remove, and insertion moves. We propose changing the local search inside the VND to a sequential search through the neighborhoods to obtain nondominated points for the Pareto‐front quickly. In the numerical tests, we consider a single‐objective version of the heuristic, comparing the results on 510 benchmark instances to show that it is quite effective. Moreover, new instances are generated in accordance with the literature for the bicriteria problem, showing the ability of the proposed heuristic to return an efficient set of nondominate solutions compared with the well‐known nondominated sorting genetic algorithm II.     

On cluster resource allocation for multiple parallel task graphs

Many scientific applications can be structured as parallel task graphs (PTGs), that is, graphs of data-parallel tasks. Adding data parallelism to a task-parallel application provides opportunities for higher performance and scalability, but poses additional scheduling challenges. In this paper, we study the off-line scheduling of multiple PTGs on a single, homogeneous cluster. The objective is to optimize performance without compromising fairness among the PTGs. We consider the range of previously proposed scheduling algorithms applicable to this problem, from both the applied and the theoretical literature, and we propose minor improvements when possible. Our main contribution is an extensive evaluation of these algorithms in simulation, using both synthetic and real-world application configurations, using two different metrics for performance and one metric for fairness. We identify a handful of algorithms that provide good trade-offs when considering all these metrics. The best algorithm overall is one that structures the schedule as a sequence of phases of increasing duration based on a makespan guarantee produced by an approximation algorithm.     

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.     

Three self-adaptive multi-objective evolutionary algorithms for a triple-objective project scheduling problem

Finding a Pareto-optimal frontier is widely favorable among researchers to model existing conflict objectives in an optimization problem. Project scheduling is a well-known problem in which investigating a combination of goals eventuate in a more real situation. Although there are many different types of objectives based on the situation on hand, three basic objectives are the most common in the literature of the project scheduling problem. These objectives are: (i) the minimization of the makespan, (ii) the minimization of the total cost associated with the resources, and (iii) the minimization of the variability in resources usage. In this paper, three genetic-based algorithms are proposed for approximating the Pareto-optimal frontier in project scheduling problem where the above three objectives are simultaneously considered. For the above problem, three self-adaptive genetic algorithms, namely (i) A two-stage multi-population genetic algorithm (MPGA), (ii) a two-phase subpopulation genetic algorithm (TPSPGA), and (iii) a non-dominated ranked genetic algorithm (NRGA) are developed. The algorithms are tested using a set of instances built from benchmark instances existing in the literature. The performances of the algorithms are evaluated using five performance metrics proposed in the literature. Finally according to the technique for order preference by similarity to ideal solution (TOPSIS) the self-adaptive NRGA gained the highest preference rank, followed by the self-adaptive TPSPGA and MPGA, respectively.     

Market‐based grid resource co‐allocation and reservation for applications with hard deadlines

Grid computing technology enables the creation of large‐scale IT infrastructures that are shared across organizational boundaries. In such shared infrastructures, conflicts between user requirements are common and originate from the selfish actions that users perform when formulating their service requests. The introduction of economic principles in grid resource management offers a promising way of dealing with these conflicts. We develop and analyze both a centralized and a decentralized algorithm for economic grid resource management in the context of compute bound applications with deadline‐based quality of service requirements and non‐migratable workloads. Through the use of reservations, we co‐allocate resources across multiple providers in order to ensure that applications finish within their deadline. An evaluation of both algorithms is presented and their performance in terms of realized user value is compared with an existing market‐based resource management algorithm. We establish that our algorithms, which operate under a more realistic workload model, can closely approximate the performance of this algorithm. We also quantify the effect of allowing local workload preemption and different scheduling heuristics on the realized user value. Copyright © 2009 John Wiley & Sons, Ltd.     

A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times

Motivated by applications in iron and steel industry, we consider a two-stage flow shop scheduling problem where the first machine is a batching machine subject to the blocking constraint and the second machine is a discrete machine with shared setup times. We show that the problem is strongly NP-hard when the objective is to minimize the makespan. When solved with a heuristic priority rule, the worst case ratio with the minimum makespan is 2. For a more general objective, the minimization of a linear combination of the makespan and the total blocking time, a quadratic mixed integer program is presented first. Then we pinpoint two cases with polynomial time algorithms: the case without blocking constraint and the case with a given job sequence. Also for the general objective, we analyze an approximation algorithm. Finally, we evaluate the algorithms, giving experimental results on randomly generated test problems.     

Energy‐efficient scheduling algorithms for batch‐of‐tasks (BoT) applications on heterogeneous computing systems

One of the major design constraints of a heterogeneous computing system is optimal scheduling, that is, mapping of tasks on the processing nodes in order to optimize the QoS parameters. Because of the huge energy consumption by computing resources, negative environmental effects and reduced system reliability, energy has unavoidably been added as a new parameter to the list of QoS parameters. Energy optimization in scheduling strategies along with makespan makes it an even more challenging combinatorial optimization problem. This work proposes two energy‐aware scheduling algorithms G1 and G2 to schedule a batch‐of‐tasks, made of a collection of independent tasks, on heterogeneous processors in order to minimize the makespan and the energy consumption. The proposed algorithms schedule tasks based on weighted aggregation cost function to the appropriate processors followed by task migration phase designed to further minimize the makespan and the energy consumption. The study evaluates the performance of the proposed algorithms with some of the peers, that is, MinMin, MINSuff on account of makespan, energy consumption, flowtime, and utilization. An experimental study reveals that the proposed algorithm (G2) consistently performs better under various test conditions. Copyright © 2015 John Wiley & Sons, Ltd.