Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines

This paper investigates two preemptive semi-online scheduling problems to minimize makespan on two uniform machines. In the first semi-online problem, we know in advance that all jobs have their processing times in between p and rp . In the second semi-online problem, we know the size of the largest job in advance. We design an optimal semi-online algorithm which is optimal for every combination of machine speed ratio and job processing time ratio for the first problem, and an optimal semi-online algorithm for every machine speed ratio for the second problem.Received: 2 December 2003, Published online: 16 January 2004This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and National Natural Science Foundation of China (10271110).     

Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines

In this paper, we consider semi-online minimum makespan scheduling problem with reassignment on two identical machines. Two versions are discussed. In the first version, one can reassign the last job of one machine that is based on the problem proposed by Tan and Yu (2008) [1], in which case the last job of each machine is allowed to be reassigned. An optimal algorithm which has the same competitive ratio is presented. In the second version we consider the combination of the next two conditions: the total size of all jobs is known in advance and one can reassign the last job of one machine. For this problem an optimal algorithm with competitive ratio is also given.     

Optimal preemptive semi-online scheduling on two uniform processors

We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1,r] (r?1) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s?1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms.     

Mathematical models for preemptive shop scheduling problems

More than half a century has passed since Bowman and Dantzig (1959) [13] and [14] introduced their models for preemptive shop scheduling problems. A more efficient model seems to be needed to address all the aspects involved in the problem. We introduce a new Integer Linear Programming (ILP) formulation as a new method for solving the preemptive Job Shop Scheduling Problem (pJSSP). The dimension of the new model, unlike those of the existing ones, depends solely on the number of jobs and machines irrespective of processing times. The proposed model is used as an optimal, two-phase approach. In phase one, the model is solved to obtain the start and completion times of each operation on each machine. In phase two, a simple algorithm in O(mn log n) steps is used to turn these times into a complete and optimal schedule. Different preemptive flow shop problems are studied as special cases of the pJSSP while some related properties are also discussed. Finally, the higher efficiency of the proposed model is verified both theoretically and computationally through its comparison with conventional methods commonly in use.     

Genetic algorithms for flowshop scheduling problems

In this paper, we apply a genetic algorithm to flowshop scheduling problems and examine two hybridizations of the genetic algorithm with other search algorithms. First we examine various genetic operators to design a genetic algorithm for the flowshop scheduling problem with an objective of minimizing the makespan. By computer simulations, we show that the two-point crossover and the shift change mutation are effective for this problem. Next we compare the genetic algorithm with other search algorithms such as local search, taboo search and simulated annealing. Computer simulations show that the genetic algorithm is a bit inferior to the others. In order to improve the performance of the genetic algorithm, we examine the hybridization of the genetic algorithms. We show two hybrid genetic algorithms: genetic local search and genetic simulated annealing. Their high performance is demonstrated by computer simulations.     

Preemptive semi-online scheduling with tightly-grouped processing times

This paper investigates a preemptive semi-online scheduling problem on m identical parallel machines where m = 2,3. It is assumed that all jobs have their processing times in between p and rp (p > 0, r≥1). The goal is to minimize the makespan. Best possible algorithms are designed for any r≥1 when m = 2,3.     

Optimal consensus algorithms for cooperative team of agents subject to partial information

The objectives of this work are the development and design of controllers for a team of agents that accomplish consensus for agents’ output in both leaderless (LL) and modified leader-follower (MLF) architectures. Towards this end, a semi-decentralized optimal control strategy is designed based on minimization of individual cost functions over a finite horizon using local information. Interactions among agents due to information flows are represented through the control channels in characterization of the dynamical model of each agent. It is shown that minimization of the proposed cost functions results in a modified consensus algorithm for LL and MLF architectures. In the latter case, the desired output is assumed to be available for only the leader while the followers should follow the leader using information exchanges existing among themselves and the leader through a predefined topology. Furthermore, the performance of the cooperative team under a member’s fault is formally analyzed and investigated. The robustness of the team to uncertainties and faults in the leader or followers and adaptability of the team members to these unanticipated situations are also shown rigorously. Finally, simulation results are presented to demonstrate the effectiveness of our proposed methodologies in achieving prespecified requirements.     

Bicriteria approximation algorithms for scheduling problems with communications delays

We study the problem of simultaneously minimizing the makespan and the average weighted completion time for the precedence multiprocessor constrained scheduling problem with unit execution times and unit communication delays, known as the UET–UCT problem (Munier and König, Operations Research, 45(1), 145–148 (1997)). We propose a simple (16/9, 16/9)-approximation algorithm for the problem with an unrestricted number of machines. We improve our algorithm by adapting a technique first introduced by Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999) and provide a (1.745, 1.745)-approximate solution. For the considered scheduling problem, we prove the existence of a (1.445, 1.445)-approximate solution, improving the generic existence result of Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999). Also notice that our results for the case of an unrestricted number of processors hold for the more general scheduling problem with small communication delays (SCT problem), and for two other classical optimality criteria: maximum lateness and weighted lateness. Finally, we propose an approximation algorithm for the UET–UCT problem with a restricted number of processors.Research partially supported by the thematic network APPOL II (IST 2001-32007) of the European Union, the ACI-GRID2 project of the French government, and the MULT-APPROX project of the France-Berkeley Fund.     

Subexponential algorithms for partial cover problems

Partial Cover problems are optimization versions of fundamental and well-studied problems like Vertex Cover and Dominating Set. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number k of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by k. It was recently shown by Amini et al. (2008) [1] that Partial Vertex Cover and Partial Dominating Set are fixed parameter tractable on large classes of sparse graphs, namely H-minor-free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time ²O(k)nO(1).During the last decade there has been an extensive study on parameterized subexponential algorithms. In particular, it was shown that the classical Vertex Cover and Dominating Set problems can be solved in subexponential time on H-minor-free graphs. The techniques developed to obtain subexponential algorithms for classical problems do not apply to partial cover problems. It was left as an open problem by Amini et al. (2008) [1] whether there is a subexponential algorithm for Partial Vertex Cover and Partial Dominating Set. In this paper, we answer the question affirmatively by solving both problems in time not only on planar graphs but also on much larger classes of graphs, namely, apex-minor-free graphs. Compared to previously known algorithms for these problems our algorithms are significantly faster and simpler.     

Genetic algorithm with fuzzy logic controller for preemptive and non-preemptive job-shop scheduling problems

In this paper, we propose a new genetic algorithm (GA) with fuzzy logic controller (FLC) for dealing with preemptive job-shop scheduling problems (p-JSP) and non-preemptive job-shop scheduling problems (np-JSP). The proposed algorithm considers the preemptive cases of activities among jobs under single machine scheduling problems. For these preemptive cases, we first use constraint programming and secondly develop a new gene representation method, a new crossover and mutation operators in the proposed algorithm.However, the proposed algorithm, as conventional GA, also has a weakness that takes so much time for the fine-tuning of genetic parameters. FLC can be used for regulating these parameters.In this paper, FLC is used to adaptively regulate the crossover ratio and the mutation ratio of the proposed algorithm. To prove the performance of the proposed FLC, we divide the proposed algorithm into two cases: the GA with the FLC (pro-fGA) and the GA without the FLC (pro-GA).In numerical examples, we apply the proposed algorithms to several job-shop scheduling problems and the results applied are analyzed and compared. Various experiments show that the results of pro-fGA outperform those of pro-GA.     

Optimal scheduling of contract algorithms with soft deadlines

A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time, and may not return useful results if interrupted prior to that time. In contrast, an interruptible algorithm will always output some meaningful (albeit suboptimal) solution, even if interrupted during its execution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a well-studied problem with significant applications in AI. In the standard model, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper, we study the more general setting of scheduling contract algorithms in the presence of soft deadlines. In particular, we address the setting in which if an interruption occurs at time t, then the system is given an additional window of time \(w(t)\le c \cdot t\), for constant c, within which the simulation must be completed. We formulate extensions to performance measures of schedules under this setting and derive schedules of optimal performance for all concave functions w.     

Heuristic algorithms for solving earliness-tardiness scheduling problems with machine vacations

The earliness and tardiness (E/T) penalty problem in scheduling gained more importance in part due to its application in Just-In-Time (JIT) production system. Inorder to meet JIT production schedules preventive maintenance plan must be in place. During the maintenance periods machine is not available for processing. The time duration planned for preventive maintenance or meal breaks is called machine vacation. Incorporating E/T penalty and machine vacation a single machine scheduling model is developed. Heuristic methods for solving this problem and computational results are also presented.     

Optimal sub-tree scheduling for wireless sensor networks with partial coverage

In this paper, we consider the problem of scheduling optimal sub-trees at different time intervals for wireless sensor network (WSN) communications with partial coverage. More precisely, we minimize the total power consumption of the network while taking into account time dimension and multichannel diversity where different disjoint subsets of nodes are required to be active and connected under a tree topology configuration. Optimization problems of these types may arise when designing new wireless communication protocols in order to increase network lifetime. We propose mixed integer quadratic and linear programming (resp. MIQP and MILP) models to compute optimal solutions for the problem. Subsequently, we propose Kruskal-based variable neighborhood search (VNS) and simulated annealing (SA) meta-heuristic procedures. In particular, we introduce a new embedded guided local search strategy in our VNS algorithm to further strengthen the solutions obtained. Our numerical results indicate that some of the proposed models allow to obtain optimal solutions with CPLEX in significantly less CPU time. Similarly, VNS and SA algorithms proved to be highly efficient when compared to the optimal solutions and allow to obtain near optimal solutions for large instances. In particular, VNS and guided VNS strategies allow to obtain solutions in less CPU time whilst SA methods can reach better solutions at higher CPU times. Finally, optimizing over time dimension allows one to obtain important reductions in power savings which has never been reported before in the literature.