主次指标为最小化总完工时间和存储费用的带有准备时间的单机分批排序问题

In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O(n2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.     

Single-machine scheduling with positional due indices and positional deadlines

In this paper, we study single-machine scheduling problems with due dates, positional due indices, deadlines and positional deadlines. The scheduling criteria studied in this paper include the number of position-violated tasks, the weighted number of position-violated tasks, and the maximum positional lateness of tasks, by also combining with other traditional scheduling criteria. For each problem, we either provide a polynomial-time algorithm or present an NP-hardness proof.     

Scheduling with a minimum number of machines

We investigate the scheduling problem with release dates and deadlines on a minimum number of machines. In the case of equal release dates, we present a 2-approximation algorithm. We also show that Greedy Best-Fit (GBF) is a 6-approximation algorithm for the case of equal processing times.     

Scheduling with controllable release dates and processing times: Makespan minimization

The paper deals with the single-machine scheduling problem in which job processing times as well as release dates are controllable parameters and they may vary within given intervals. While all release dates have the same boundary values, the processing time intervals are arbitrary. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amount. The objective is to minimize the makespan together with the total compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(n²) algorithm for the case of equal release date compression costs and equal processing time compression costs. For the bicriteria version of the latter problem with agreeable processing times, we suggest an O(n²) algorithm that constructs the breakpoints of the efficient frontier.     

Scheduling with controllable release dates and processing times: Total completion time minimization

The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(n²) time. The solution algorithm can be considered as a generalization of the algorithm that minimizes the makespan and total compression cost. The generalized version of the algorithm is also applicable to the problem with parallel machines and to a range of due-date scheduling problems with controllable processing times.     

Scheduling real-time tasks for dependability

Real-time systems are increasingly used in applications whose failure may result in large economic and human costs. Since many such systems operate in environments that are non-deterministic, and possibly hazardous, it is extremely important that the systems be dependable, namely the deadlines of tasks must be met even in the presence of particular failures. In order to enhance the dependability of a real-time system, we study the problem of scheduling a set of real-time tasks to meet their deadlines in the presence of processor failures. We first prove that the problem of scheduling a set of non-preemptive tasks on more than two processors to tolerate one arbitrary processor failure is NP-complete even when the tasks share a common deadline. Heuristic algorithms are then proposed to solve this problem. The schedules generated by the heuristic algorithms can tolerate one arbitrary processor failure in the worst case. The analysis and experimental data show that the performance of the algorithms is near-optimal.     

Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows (MDVSPTW) consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem (UBSP) and freight transport scheduling problem (FTSP). The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.     

Single Machine Scheduling of Unit-time Jobs with Controllable Release Dates

The paper presents a bicriterion approach to solve the single-machine scheduling problem in which the job release dates can be compressed while incurring additional costs. The two criteria are the makespan and the compression cost. For the case of equal job processing times, an O(n⁴) algorithm is developed to construct integer Pareto optimal points. We discuss how the algorithm developed can be modified to construct an -approximation of noninteger Pareto optimal points. The complexity status of the problem with total weighted completion time criterion is also established.     

Single machine scheduling problem with controllable processing times and resource dependent release times

We consider two single machine scheduling problems with resource dependent release times and processing times, in which the release times and processing times are linearly decreasing functions of the amount of resources consumed. The objective is to minimize the total cost of makespan and resource consumption function that is composed of release time reduction and processing time reduction. In the first problem, the cost of reducing a unit release time for each job is common. We show that the problem can be solved in polynomial time. The second problem assumes different reduction costs of job release times. We show that the problem can be reduced polynomially from the partition problem and thus, is NP-complete.     

Audit scheduling with overlapping activities and sequence-dependent setup costs

Audit firms are faced with the complex job of scheduling auditors to audit tasks. The scheduling becomes more complex as the firm needs to consider real life issues in determining an optimal schedule. Among these issues are the setup times and costs emanating from changing the assignments of the auditors and the lead and lag relationships between the audit tasks.Audit scheduling with overlapping activities and sequence-dependent setup cost has not been treated in literature. This paper presents a formulation and a solution approach for this audit scheduling problem. First, the problem is represented by an activity network with lead/lag relationships. Then the network is analyzed to determine the early and late finish times of activities. An integer linear program (ILP), which uses the early and late finish times of activities to reduce the number of decision variables, is formulated. A four-auditor two-engagement example is used to illustrate the ILP model and its solution. The results indicate that incorporating the setup cost and the overlapping of activities yields lower cost schedules leading to sizable savings in the cost of audits. The proposed treatment is of merit in providing realistic schedules that can be easily implemented     

Bicriteria scheduling for contiguous and non contiguous parallel tasks

We study the problem of scheduling on k identical machines a set of parallel tasks with release dates and deadlines in order to maximize simultaneously two criteria, namely the Size (number of scheduled tasks) and the Weight (sum of the weights of scheduled tasks). If no task requires more than half of the machines, we construct schedules that are simultaneously approximations for the Size and the Weight by combining two approximate schedules, one for each parameter. We obtain existence results and polynomial time bicriteria approximation algorithms in contiguous and non contiguous models.     

工时依赖于开工时间的单台机排序问题

此文考察工时依赖于开工时间的排序问题．文章证明：(1)即使准奋时间完全相同，判断工时与开工时间相关的单台机排序问题是否有可行解也是NP完全的．(2)即使只存在两个不同的截止期，判断工时与开工时间相关的单台机排序问题是否有可行解仍然是NP完全的．(3)当所有工件有相同截止期时，问题是否有可行解可在多项式时间内判定．     

Single machine total tardiness maximization problems: complexity and algorithms

In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the total weighted tardiness maximization problem, we present an NP-hardness proof and a pseudo-polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP-hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well.     

Scheduling jobs with release dates on parallel batch processing machines

In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint.     

A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints

We address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem of optimal scheduling of sparse tree-like instances can be solved in polynomial time. However, if we admit dense instances then the problem becomes NP-hard, even if there are only two machines.     

Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints

In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-and-price approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem.     

Cane Railway Scheduling via Constraint Logic Programming: Labelling Order and Constraints in a Real-Life Application

In Australia, cane transport is the largest unit cost in the manufacturing of raw sugar, making up around 35% of the total manufacturing costs. Producing efficient schedules for the cane railways can result in significant cost savings. This paper presents a study using Constraint Logic Programming (CLP) to solve the cane transport scheduling problem. Tailored heuristic labelling order and constraints strategies are proposed and encouraging results of application to several test problems and one real-life case are presented. The preliminary results demonstrate that CLP can be used as an effective tool for solving the cane transport scheduling problem, with a potential decrease in development costs of the scheduling system. It can also be used as an efficient tool for rescheduling tasks which the existing cane transport scheduling system cannot perform well.     

Maximization of solution flexibility for robust shop scheduling

We consider the problem of introducing flexibility in the schedule determination phase, for shop scheduling problems with release dates and deadlines. The flexibility is provided by generating a family of schedules, instead of a unique one. We represent a family of schedules by an ordered group assignment defining for each machine a sequence of groups where the operations within a group are totally permutable. We propose a polynomial time algorithm to evaluate the worst case completion time of operations in an ordered group assignment. We then consider the single machine problem with heads and deadlines associated to operations, as a sub-problem of the job shop problem. We propose polynomial time dynamic programming algorithms for minimizing the number of groups and for maximizing the number of characterized sequences, under specific constraints. Finally, computational experiences on job shop benchmarks, show the impact of grouping operations on the solution makespan value.     

A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times

We consider the problem of scheduling n independent jobs on m unrelated parallel machines with sequence-dependent setup times and availability dates for the machines and release dates for the jobs to minimize a regular additive cost function. In this work, we develop a new branch-and-price optimization algorithm for the solution of this general class of parallel machines scheduling problems. A new column generation accelerating method, termed “primal box”, and a specific branching variable selection rule that significantly reduces the number of explored nodes are proposed. The computational results show that the approach solves problems of large size to optimality within reasonable computational time.     

单机主次指标排序问题1|(rj, dj) agreeable, pj = p, pmtn|∑Uj|Tmax

本文研究了单机主次指标排序问题1|rj,pmtn|∑Uj|Tmax．在同工期且准备时间和工期具有一致性的情形下，给出了该问题的允许中断抢先的多项式时间算法．