Maximum lifetime coverage preserving scheduling algorithms in sensor networks

In wireless sensor networks, when each target is covered by multiple sensors, sensors can take turns to monitor the targets in order to extend the lifetime of the network. In this paper, we address how to improve network lifetime through optimal scheduling of sensor nodes. We present two algorithms to achieve the maximum lifetime while maintaining the required coverage: a linear programming-based exponential-time exact solution, and an approximation algorithm. Numerical simulation results from the approximation algorithm are compared to the exact solution and show a high degree of accuracy and efficiency.     

An FPTAS for scheduling with resource constraints

We study a basic scheduling problem with resource constraints: A number of jobs need to be scheduled on two parallel identical machines with the objective of minimizing the makespan, subject to the constraint that jobs may require a unit of one of the given renewable resources during their execution. For this NP-hard problem, we develop a fully polynomial-time approximation scheme (FPTAS). Our FPTAS makes a novel use of existing algorithms for the subset-sum problem and the open shop scheduling problem.     

Job scheduling with technical constraints

Many scheduling problems that arise in industry have technical constraints unique to the specific industry. Scheduling methodologies must be highly customized to deal with the unique technical constraints. This study proposes a scheduling model that can incorporate technical constraints into standard scheduling constraints already present in classical models. Using this approach, technical constraints from one industry can be interchanged with those from another with little modification to the existing methodologies. The conditions under which this approach can be applied are investigated and frameworks for applying dispatching rules are proposed. Numerical experiments evaluate the performance of these dispatching rules and compare them with two meta-heuristics.     

On-line scheduling with non-crossing constraints

We consider the problem of on-line scheduling with non-crossing constraints. The objective is to minimize the latest completion time. We provide optimal competitive ratio heuristics for the on-line list and on-line time problems with unit processing times, and a 3-competitive heuristic for the general on-line time problem.     

Heuristics for unrelated machine scheduling with precedence constraints

In this paper, we consider the problem of scheduling tasks on unrelated parallel machines. Precedence constraints between the tasks form chains of tasks. We propose a number of heuristics in order to find near optimal solutions to the problem. Empirical results show that the heuristics are able to find very good approximate solutions.     

Two-machine flowshop scheduling with availability constraints

The majority of the scheduling literature carries a common assumption that machines are available all the time. However, this availability assumption may not be true in real industry settings, since a machine may become unavailable during certain periods of time when, for instance, a machine breakdown or a preventive maintenance activity is scheduled. Although the problem is realistic and important, it is relatively new and unstudied. In this paper, we study the two-machine flowshop problem under the assumption that the unavailable time is known in advance. We assume that if a job cannot be finished before the next down period of a machine then the job will have to partially restart when the machine has become available again. We call our model semiresumable. Our model contains two important special cases: resumable where the job can be continued without any penalty and nonresumable where the job needs to totally restart. We study the problem where an availability constraint is imposed only on one machine as well as on both machines. We provide complexity analysis, develop a pseudo-polynomial dynamic programming algorithm to solve the problem optimally and also propose heuristic algorithms with an error bound analysis.     

Crop rotation scheduling with adjacency constraints

In this article we propose a 0-1 optimization model to determine a crop rotation schedule for each plot in a cropping area. The rotations have the same duration in all the plots and the crops are selected to maximize plot occupation. The crops may have different production times and planting dates. The problem includes planting constraints for adjacent plots and also for sequences of crops in the rotations. Moreover, cultivating crops for green manuring and fallow periods are scheduled into each plot. As the model has, in general, a great number of constraints and variables, we propose a heuristics based on column generation. To evaluate the performance of the model and the method, computational experiments using real-world data were performed. The solutions obtained indicate that the method generates good results.     

A priority-rule method for project scheduling with work-content constraints

The activities of a project are in general characterized by a work content in terms of resource–time units, e.g. person-days. Even though most project scheduling models assume a time-invariant resource usage, normally it is possible to vary the resource usage during the execution of an activity. Typically, a lower and an upper bound on this resource usage and a minimum time lag between consecutive changes of this resource usage are prescribed. The project scheduling problem studied in this paper consists in determining a feasible resource-usage profile for each activity such that the project duration is minimized subject to precedence and resource-capacity constraints. While the known solution methods interpret the prescribed work content as a lower bound, we assume that each activity’s work content must be processed exactly.     

An improved heuristic for one-machine scheduling with delays constraints

An improved heuristic is proposed for one-machine scheduling problem with delay constraints, thus an open problem raised by Wikumet al. is solved. The heuristic solves the corresponding unit-execution-time problem optimally.     

A monotone approximation algorithm for scheduling with precedence constraints

We provide a monotone O(m^2/3)-approximation algorithm for scheduling related machines with precedence constraints.     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

Open shop scheduling with some additional constraints

An open shop scheduling problem is presented; preemptions during processing of a job on a processorp is allowed but the job cannot be sent on another processorq before it is finished onp. A graph-theoretical model is described and a characterization is given for problems where schedules with such restricted preemptions useT time units whereT is the maximum of the processing times of the jobs and of the working times of the processors. The general case is shown to be NP-complete. We also consider the case where some constraints of simultaneity are present. Complexity of the problem is discussed and a solvable case is described.     

Uniform machine scheduling with machine available constraints

1.IntroductionIntheclassicalparallelmachineschedulingareaweassumethatmachinesarealwaysavailable.However,aspointedin[1],inrealindustrysettingsthisassumptionmaynotbetrue.Forexample,machinesmaynotalwaysbeavailablebecauseoftheirpreventivemaintenanceduringtheschedulingperiod.Thatistosay,eachmachineiisunavailablefromsibuntilrib(05sib5rib),where0SkSm,withmbeingthenumberofunavailabilityperiodsformachineiduringtheplanninghorizon.Inotherwords,somepapersstatethatmachinesareavailableintimewindows,whichi…     

Makespan minimization for parallel machines scheduling with multiple availability constraints

The problem of makespan minimization for parallel machines scheduling with multiple planned nonavailability periods in the case of resumable jobs is considered. In the current state of the literature, there is a limited number of models and algorithms dealing with this problem and only for very small problem size, and nonavailability limited to some machines. The problem is first formulated as a mixed integer linear programming model and optimally solved using CPLEX for small to moderately large size problems with multiple availability constraints on all machines. An implicit enumeration algorithm using the lexicographic order is then designed to solve large-scale problems. Numerical results are obtained for several experiments and they show the validity and performance improvements procured by both the MILP model and the new enumeration algorithm.     

A Lagrangean heuristic algorithm for disassembly scheduling with capacity constraints

This paper considers the problem of determining the disassembly schedule (quantity and timing) of products in order to satisfy the demand of their parts or components over a finite planning horizon. The objective is to minimize the sum of set-up, disassembly operation, and inventory holding costs. As an extension of the uncapacitated versions of the problem, we consider the resource capacity restrictions over the planning horizon. An integer program is suggested to describe the problem mathematically, and to solve the problem, a heuristic is developed using a Lagrangean relaxation technique together with a method to find a good feasible solution while considering the trade-offs among different costs. The effectiveness of the algorithm is tested on a number of randomly generated problems and the test results show that the heuristic suggested in this paper can give near optimal solutions within a short amount of computation time.     

Adaptive energy efficient sensor scheduling for wireless sensor networks

In this paper, we consider an adaptive energy efficient sensor scheduling mechanism. We consider a wireless sensor network where the sink sends queries form time to time, and sensors are equipped with one or more sensing components. Our goal is to design an adaptive sensor scheduling mechanism to choose sets of active sensors to work alternatively such that different types of queries are served, the global connectivity requirements can be met, and network lifetime is maximized. A connected dominating set (CDS) based localized mechanism is proposed. Initially, a basic backbone is constructed, then when a query is issued, new sensors are activated locally such that to meet the requirements of the query and global connectivity. When a query expires, some sensors return to sleep and the CDS is restored. Our simulation results show that the solution is effective and it improved network lifetime.     

A new smoothing scheme for mathematical programs with complementarity constraints

In this paper, we consider a mathematical program with complementarity constraints (MPCC). We present a new smoothing scheme for this problem, which makes the primal structure of the complementarity part unchanged mostly. For the new smoothing problem, we show that the linear independence constraint qualification (LICQ) holds under some conditions. We also analyze the convergence behavior of the smoothing problem, and get some sufficient conditions such that an accumulation point of stationary points of the smoothing problems is C (M, B)-stationarity respectively. Based on the smoothing problem, we establish an algorithm to solve the primal MPCC problem. Some numerical experiments are given in the paper.