Coverage by directional sensors in randomly deployed wireless sensor networks

We study a novel “coverage by directional sensors” problem with tunable orientations on a set of discrete targets. We propose a Maximum Coverage with Minimum Sensors (MCMS) problem in which coverage in terms of the number of targets to be covered is maximized whereas the number of sensors to be activated is minimized. We present its exact Integer Linear Programming (ILP) formulation and an approximate (but computationally efficient) centralized greedy algorithm (CGA) solution. These centralized solutions are used as baselines for comparison. Then we provide a distributed greedy algorithm (DGA) solution. By incorporating a measure of the sensors residual energy into DGA, we further develop a Sensing Neighborhood Cooperative Sleeping (SNCS) protocol which performs adaptive scheduling on a larger time scale. Finally, we evaluate the properties of the proposed solutions and protocols in terms of providing coverage and maximizing network lifetime through extensive simulations. Moreover, for the case of circular coverage, we compare against the best known existing coverage algorithm.     

Minimizing the Number of Late Jobs under the Group Technology Assumption

We consider the one-machine scheduling problem to minimize the number of late jobs under the group technology assumption, where jobs are classified into groups and all jobs from the same group must be processed contiguously. This problem is shown to be strongly NP-hard, even for the case of unit processing time and zero set-up time. A polynomial time algorithm is developed for the restricted version in which the jobs in each group have the same due date. However, the problem is proved to be ordinarily NP-hard if the jobs in a group have the same processing time as well as the same due date.     

A note on the complexity of the problem of two-agent scheduling on a single machine

We consider a two-agent scheduling problem on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the number of tardy jobs of the second agent cannot exceed a given number. It is reported in the literature that the complexity of this problem is still open. We show in this paper that this problem is NP-hard under high multiplicity encoding and can be solved in pseudo-polynomial time under binary encoding. When the first agent's objective is to minimize the total weighted completion time, we show that the problem is strongly NP-hard even when the number of tardy jobs of the second agent is restricted to be zero.     

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081.

     

Just-in-time scheduling with controllable processing times on parallel machines

We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider four different models for treating the two criteria. We prove that three of these problems are NP\mathcal{NP} -hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three NP\mathcal{NP} -hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial time optimization algorithm, which is converted to a fully polynomial time approximation scheme.     

Staying safe and visible via message sharing in online social networks

As an imperative channel for fast information propagation, online social networks (OSNs) also have their defects. One of them is the information leakage, i.e., information could be spread via OSNs to the users whom we are not willing to share with. Thus the problem of constructing a circle of trust to share information with as many friends as possible without further spreading it to unwanted targets has become a challenging research topic but still remained open. Our work is the first attempt to study the Maximum Circle of Trust problem seeking to share the information with the maximum expected number of poster’s friends such that the information spread to the unwanted targets is brought to its knees. First, we consider a special and more practical case with the two-hop information propagation and a single unwanted target. In this case, we show that this problem is NP-hard, which denies the existence of an exact polynomial-time algorithm. We thus propose a Fully Polynomial-Time Approximation Scheme (FPTAS), which can not only adjust any allowable performance error bound but also run in polynomial time with both the input size and allowed error. FPTAS is the best approximation solution one can ever wish for an NP-hard problem. We next consider the number of unwanted targets is bounded and prove that there does not exist an FPTAS in this case. Instead, we design a Polynomial-Time Approximation Scheme (PTAS) in which the allowable error can also be controlled. When the number of unwanted targets are not bounded, we provide a randomized algorithm, along with the analytical theoretical bound and inapproximaibility result. Finally, we consider a general case with many hops information propagation and further show its #P-hardness and propose an effective Iterative Circle of Trust Detection (ICTD) algorithm based on a novel greedy function. An extensive experiment on various real-world OSNs has validated the effectiveness of our proposed approximation and ICTD algorithms. Such an extensive experiment also highlights several important observations on information leakage which help to sharpen the security of OSNs in the future.     

不确定条件下不同交货期窗口的Job Shop 调度

研究了具有不同交货期窗口的Job Shop 的提前/ 拖期调度问题,并考虑了处理时间的不确定 性,采用三角模糊数表示处理时间的不确定性,提出了基于遗传算法的求解算法. 仿真实验验证了 算法的有效性.     

Combinatorial Optimization in Real-Time Scheduling: Theory and Algorithms

Real-time computer systems are essential for many applications, such as robot control, avionics, medical instrumentation, manufacturing, etc. The correctness of the system depends on the temporal correctness as well as the functional correctness of the task executions. In order to assure temporal correctness it is necessary that the resources be scheduled to meet the temporal requirements of applications. When we consider the problem of nonpreemptive scheduling of a set of tasks in a processor for which no feasible solution exists, some tasks may have to be rejected so that a schedule can be generated for the rest. In this paper, we consider the problem of generating an optimal schedule such that the number of rejected tasks is minimized, and then the finish time is minimized for the accepted tasks. We propose to use an analytic approach to solve this problem. We first discuss the super sequence based technique which was originally proposed for reducing the search space in testing the feasibility of a task set. Then we show by the Conformation theorem that the super sequence constructed from the task set also provides a valid and reduced search space for the optimization problem. While the complexity of our scheduling algorithm in the worst case remains exponential, our simulation results show that the cost is reasonable for the average case.     

Preemptive scheduling on two identical parallel machines with a single transporter

We consider a scheduling problem on two identical parallel machines, in which the jobs are moved between the machines by an uncapacitated transporter. In the processing preemption is allowed. The objective is to minimize the time by which all completed jobs are collected together on board the transporter. We identify the structural patterns of an optimal schedule and design an algorithm that either solves the problem to optimality or in the worst case behaves as a fully polynomial-time approximation scheme.     

Two new robust genetic algorithms for the flowshop scheduling problem

The flowshop scheduling problem (FSP) has been widely studied in the literature and many techniques for its solution have been proposed. Some authors have concluded that genetic algorithms are not suitable for this hard, combinatorial problem unless hybridization is used. This work proposes new genetic algorithms for solving the permutation FSP that prove to be competitive when compared to many other well known algorithms. The optimization criterion considered is the minimization of the total completion time or makespan (_Cmax$C_{\max }$). We show a robust genetic algorithm and a fast hybrid implementation. These algorithms use new genetic operators, advanced techniques like hybridization with local search and an efficient population initialization as well as a new generational scheme. A complete evaluation of the different parameters and operators of the algorithms by means of a Design of Experiments approach is also given. The algorithm's effectiveness is compared against 11 other methods, including genetic algorithms, tabu search, simulated annealing and other advanced and recent techniques. For the evaluations we use Taillard's well known standard benchmark. The results show that the proposed algorithms are very effective and at the same time are easy to implement.     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.     

Bundling and Scheduling Service Packages with Customer Behavior: Model and Heuristic

Past researchers have found evidence that customers consider the sequence of event utility when evaluating past and future service experiences. Specifically, the evidence confirms that the placement of a peak event, the utility of the last event, and the slope of event utility over time all affect customer behavior and perception. We formulate an optimization problem with a focus on optimizing schedule sequence characteristics in order to maximize customer experiences. We discuss possible contexts in which this type of scheduling might be considered and, as an example, present a particularly complex model of a world‐renowned performing arts venue. We solve the problem with a simulated annealing algorithm and further discuss the complexity and opportunities associated with this type of scheduling effort.     

Economic Lot Scheduling Problem with Returns

Motivated by a case study of a company that produces car parts, we study the multi‐product economic lot scheduling problem for a hybrid production line with manufacturing of new products and remanufacturing of returned products. For this economic lot scheduling problem with returns (ELSPR), we consider policies with a common cycle time for all products, and with one manufacturing lot and one remanufacturing lot for each product during a cycle. For a given cycle time, the problem is formulated as a mixed integer linear programming (MIP) problem, which provides the basis for an exact solution. The application of this model for one of the core products of the case study company indicates a 16% reduction in cost compared to the current lot scheduling policy.     

Online scheduling to minimize the total weighted completion time plus the rejection cost

We consider the online scheduling on a single machine, in which jobs are released over time and each job can be either accepted and scheduled on the machine or rejected under a certain rejection cost. The goal is to minimize the total weighted completion time of the accepted jobs plus the total rejection cost of the rejected jobs. For this problem, we provide an online algorithm with a best possible competitive ratio of 2.     

Minimizing the number of tardy jobs in two-machine settings with common due date

We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm is derived for the job selection problem on two unrelated parallel machines. We also show that an exact approach can be derived for both problems with complexity \(O(p(n) \times \sqrt{2}^n)\), p being a polynomial function of n.     

Computer network scheduling

This paper presents a method for solving the scheduling problem of a computer-network. There are three possible criteria for optimality: (1) Maximum number of jobs to be processed per given period. (2) Minimum idle time for each of the computers in the network, or in other words, maximum utilization. (3) Optimizing an objective function which combines 1 and 2 and which may consider additional factors.     

Container Scheduling: Complexity and Algorithms

We consider the transport of containers through a fleet of ships. Each ship has a capacity constraint limiting the total number of containers it can carry and each ship visits a given set of ports following a predetermined route. Each container has a release date at its origination port, and a due date at its destination port. A container has a size 1 or size 2; size 1 represents a 1 TEU (20‐foot equivalent unit) and size 2 represents 2 TEUs. The delivery time of a container is defined as the time when the ship that carries the container arrives at its destination port. We consider the problem of minimizing the maximum tardiness over all containers. We consider three scenarios with regard to the routes of the ships, namely, the ships having (i) identical, (ii) nested, and (iii) arbitrary routes. For each scenario, we consider different settings for origination ports, release dates, sizes of containers, and number of ports; we determine the computational complexity of various cases. We also provide a simple heuristic for some cases, with its worst case analysis. Finally, we discuss the relationship of our problems with other scheduling problems that are known to be open.     

Lot-sizing and scheduling in flat-panel display manufacturing process

In this paper, we consider a lot-sizing and scheduling problem arising in the real-world flat-panel display industry. This problem is formulated as a variant of the discrete lot-sizing and scheduling problem with a sequence-dependent setup. After describing the characteristics of the problem and analyzing its computational complexity, we propose an extended formulation based on a network structure. Even though the problem is NP-hard in general, we show that there exist special cases solvable in polynomial time. For the general cases, we demonstrate the tightness of the extended formulation by means of both polyhedral analysis and computational experiments with artificially generated data and real-world industry data. We also propose a relax-and-fix heuristic algorithm based on the extended formulation, which has been deployed in practice, with the corresponding computational results.     

具有时间转换约束的离散时间-费用权衡问题研究

离散时间-费用权衡问题(DTCTP)是项目进度中研究最多的双目标优化问题,它通常以三种形式出现:(1)P1:截止日期问题,在项目截止日期约束下使完成项目的总费用最小;(2)P2:预算问题,在费用预算约束下使项目工期最短;(3)P3:工期-费用曲线问题,找出全部有效的工期-费用模式集合。然而,考虑时间转换约束(TSC)的DTCTP却很少被关注。本文首先介绍时间转换约束的问题描述,在此基础上,建立具有活动类型时间转换约束的DTCTPTSC-P2模型;从实用角度出发,设计求解模型的遗传算法;最后,用一个真实项目实例说明模型的合理性和算法的有效性,对算例分析结果表明,该模型对承包商更准确地进行项目工期-费用权衡决策具有借鉴意义。     

Batch-Processing Scheduling with Setup Times

The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.