Stochastic scheduling to minimize expected maximum lateness

This paper is concerned with the problems in scheduling a set of jobs associated with random due dates on a single machine so as to minimize the expected maximum lateness in stochastic environment. This is a difficult problem and few efforts have been reported on its solution in the literature. In this paper, we first derive a deterministic equivalent to the expected maximum lateness and then propose a dynamic programming algorithm to obtain the optimal solutions. The procedures to compute optimal solutions are initially developed in the case of deterministic processing times, and then extended to stochastic processing times following arbitrary probability distributions. Moreover, several heuristic rules are suggested to compute near-optimal solutions, which are shown to be highly efficient and accurate by computer-based experiments.     

工件具有加工位置上限最小化加权总误工量的单机排序问题

考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中,每个工件J_j都具有一个加工位置上限k_j.也就是说,如果工件J_j是一个可行排序中的第x个工件,那么就需要满足x ≤ k_j.证明了（i）当工件具有相同工期时,该排序问题是二元NP-难的并且是拟多项式时间可解的,（ii）当工件具有单位权重时,该排序问题是一元NP-难的.     

Single machine scheduling with sequence-dependent family setups to minimize maximum lateness

Motivated by a real-life scheduling problem in a steel wire factory in China,this paper considers the single machine scheduling problem with sequence-dependent family setup times to minimize maximum lateness. In view of the NP-hard nature of the problem, structural (dominance and neighbourhood)properties of the problem are described and used in the tabu search algorithms to find optimal or near-optimal schedules. These proposed structural properties quickly exclude unpromising and/or non-improving neighbours from further search.Empirical results on the randomly generated and real-life problem instances from a factory in China show that the proposed heuristic algorithms utilizing the structural properties can obtain optimal or near optimal solutions with a reasonable computational effort.     

Minimizing total completion time for UET tasks with release time and outtree precedence constraints

Brucker et al. (Math Methods Oper Res 56: 407–412, 2003) have given an O(n ²)-time algorithm for the problems , outtree and , outtree . In this note, we show that their algorithm admits an O(n log n)-time implementation.     

目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法

单台机器带一个维修时间段的排序问题,目标是最小化所有工件的运输时间和.在这篇文章里,重新研究了该问题,并给出了一个时间复杂性为O（n³）的近似算法,将性能比从3/2改进到5/4.     

Heuristic constructive algorithms for open shop scheduling to minimize mean flow time

In this paper, we consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is evaluated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimate of mean flow time. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.     

A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times

The two-stage assembly flowshop scheduling problem has been addressed with respect to different criteria in the literature where setup times are ignored. For some applications, setup times are essential to be explicitly considered since they may take considerable amount of time. We address the two-stage assembly flowshop scheduling problem with respect to maximum lateness criterion where setup times are treated as separate from processing times. We formulate the problem and obtain a dominance relation. Moreover, we propose a self-adaptive differential evolution heuristic. To the best of our knowledge, this is the first attempt to use a self-adaptive differential evolution heuristic to a scheduling problem. We conduct extensive computational experiments to compare the performance of the proposed heuristic with those of particle swarm optimization (PSO), tabu search, and EDD heuristics. The computational analysis indicates that PSO performs much better than tabu and EDD. Moreover, the analysis indicates that the proposed self-adaptive differential evolution heuristic performs as good as PSO in terms of the average error while only taking one-third of CPU time of PSO.     

Single machine bicriteria scheduling with equal-length jobs to minimize total weighted completion time and maximum cost

Bicriteria scheduling problems are of significance in both theoretical and applied aspects. It is known that the single machine bicriteria scheduling problem of minimizing total weighted completion time and maximum cost simultaneously is strongly NP-hard. In this paper we consider a special case where the jobs have equal length and present an $O(n^{3}\log n)$ algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.     

The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan

We consider the problem of scheduling family jobs with release dates on a bounded batching machine to minimize the makespan. A polynomial-time approximation scheme for the identical job size model and an approximation algorithm with a worst-case ratio of for the non-identical job size model will be derived.     

Parallel-machine scheduling with simple linear deterioration to minimize total completion time

We consider the parallel-machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the total completion time. We give a fully polynomial-time approximation scheme (FPTAS) for the case with m identical machines, where m is fixed. This study solves an open problem that has been posed in the literature for ten years.     

工件按加工长度不增序到达的最小化最大流程在线分批排序

研究单处理机工件按加工长度不增顺序到达的在线分批排序问题．工件按时在线到达,目标是最小化最大流程．流程时间是指工件的完工时间与到达时间的差值,它体现了工件在系统内的逗留时间．对于批容量有界的情形,给出了一个竞争比为1＋√5/2的最好可能的在线算法;对于批容量无界的情形,给出了一个竞争比为√2的最好可能的在线算法．     

A single-machine scheduling problem with maintenance activities to minimize makespan

We study a single-machine scheduling problem with periodic maintenance activity under two maintenance stratagems. Although the scheduling problem with single or periodic maintenance and nonresumable jobs has been well studied, most of past studies considered only one maintenance stratagem. This research deals with a single-machine scheduling problem where the machine should be stopped for maintenance after a fixed periodic interval (T) or after a fixed number of jobs (K) have been processed. The objective is to minimize the makespan for the addressed problem. A two-stage binary integer programming (BIP) model is provided for driving the optimal solution up to 350-job instances. For the large-sized problems, two efficient heuristics are provided for the different combinations of T and K. Computational results show that the proposed algorithm Best-Fit-Butterfly (BBF) performs well because the total average percentage error is below 1%. Once the constraint of the maximum number of jobs (K) processed in the machine’s available time interval (T) is equal or larger than half of jobs, the heuristic Best-Fit-Decreasing (DBF) is strongly recommended.     

A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs

The problem of scheduling on a single machine is considered in this paper with the objective of minimizing the sum of weighted tardiness of jobs. A new ant-colony optimization (ACO) algorithm, called fast ACO (FACO), is proposed and analysed for solving the single-machine scheduling problem. By considering the benchmark problems available in the literature for analysing the performance of algorithms for scheduling on a single machine with the consideration of weighted tardiness of jobs, we validate the appropriateness of the proposed local-search schemes and parameter settings used in the FACO. We also present a comparison of the requirements of CPU time for solving the single-machine total-weighted tardiness problem by the FACO and the existing algorithms.     

Proactive policies for the stochastic resource-constrained project scheduling problem

The resource-constrained project scheduling problem involves the determination of a schedule of the project activities, satisfying the precedence and resource constraints while minimizing the project duration. In practice, activity durations may be subject to variability. We propose a stochastic methodology for the determination of a project execution policy and a vector of predictive activity starting times with the objective of minimizing a cost function that consists of the weighted expected activity starting time deviations and the penalties or bonuses associated with late or early project completion. In a computational experiment, we show that our procedure greatly outperforms existing algorithms described in the literature.     

Time complexity of single machine scheduling with stochastic precedence constraints

This paper deals with single machine scheduling problems with stochastic precedence relations (so calledGERT networks). Until now most investigations on such problems, dealt with algorithms running in polynomial time. On the other hand, for scheduling problems with deterministic precedence relations exist a lot of results about time complexity. Therefore, the object of this paper is to consider time complexity of scheduling problems with stochastic precedence constraints and to describe the boundary between theNP-hard problems and those which can be solved in polynomial time.     

A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time

For a container terminal system, efficient berth and quay crane (QC) schedules have great impact on the improvement of both operation efficiency and customer satisfaction. In this paper we address berth and quay crane scheduling problems in a simultaneous way, with uncertainties of vessel arrival time and container handling time. The berths are of discrete type and vessels arrive dynamically with different service priorities. QCs are allowed to move to other berths before finishing processing on currently assigned vessels, adding more flexibility to the terminal system. A mixed integer programming model is proposed, and a simulation based Genetic Algorithm (GA) search procedure is applied to generate robust berth and QC schedule proactively. Computational experiment shows the satisfied performance of our developed algorithm under uncertainty.     

工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.     

Scheduling orders for multiple product types to minimize total weighted completion time

We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (?2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space.     

An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations

In this paper we propose an exact algorithm for the Resource Constrained Project Scheduling Problem (RCPSP) with generalized precedence relationships (GPRs) and minimum makespan objective. For the RCPSP with GPRs we give a new mathematical formulation and a branch and bound algorithm exploiting such a formulation. The exact algorithm takes advantage also of a lower bound based on a Lagrangian relaxation of the same mathematical formulation. We provide an extensive experimentation and a comparison with known lower bounds and competing exact algorithms drawn from the state of the art.