Bicriteria scheduling problems involving job rejection,controllable processing times and rate-modifying activity

This paper addresses the bicriteria scheduling problems with simultaneous consideration of job rejection, controllable processing times and rate-modifying activity on a single machine. A job is either rejected, in which case a rejection penalty will be incurred, or accepted and processed on the machine. The rate-modifying activity is an activity on the machine that changes the processing times of the jobs scheduled after the activity. The processing time of a job scheduled after the rate-modifying activity decreases with a job-dependent factor. The processing time of each job can also be controlled by allocating extra resource which is either a linear or a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the rejected job set, the accepted job sequence, the time (location) of the rate-modifying activity and the resource allocation that jointly find the trade-off between two criteria, where the first criterion is measured as the sum of total completion time and resource consumption cost while the second criterion is the total rejection cost. We consider four different models for treating the two criteria. The computational complexity status and solution procedures are provided for the problems under consideration.     

Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint

This study considers a single machine group scheduling problem with deteriorating jobs and resource allocation (controllable processing times). The objective is to have the resource availability limited within a given range, and to minimize the maximum completion time (i.e. the makespan). For two special cases, it is proved that the problem can be solved in polynomial time. For the general case, an heuristic algorithm and a branch-and-bound algorithm are proposed. Computational results show that the proposed heuristic algorithm is generally effective.     

Due-date assignment scheduling involving job-dependent learning effects and convex resource allocation

ABSTRACT

This article addresses single machine resource allocation scheduling problems with learning effects, where learning effects mean job-dependent position-based learning effects. For the common due-date assignment (CON) and slack due-date assignment (SLK) methods, a bi-cost analysis of the scheduling cost and the total weighted resource consumption cost is provided. The objective is to determine the optimal job sequence and the resource allocation simultaneously, such that the scheduling cost (the total weighted resource consumption cost) is minimized subject to the total weighted resource consumption cost (the scheduling cost) being limited. Solution procedures are provided for the problems under consideration.     

SINGLE-MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND EARLINESS,TARDINESS AND COMPLETION TIME PENALTIES

The paper considers the problem of scheduling nindependent and simultaneously available jobs on a single machine, where the job processing times are compressible as a linear cost function. The objective is to find an optimal permutation of the jobs, an optimal due date and the optimal processing times which jointly minimize a cost function consisting of the earliness, tardiness, completion time and compressing costs. It shows that the problem can be solved as an assignment problem.     

Research on scheduling with job-dependent learning effect and convex resource-dependent processing times

We study resource allocation scheduling with job-dependent learning effect on a single machine with or without due date assignment considerations. For a convex resource processing time function, we provide a polynomial time algorithm to find the optimal job sequence, and resource allocations that minimise the schedule criterion (the total compression cost) subject to the constraint that the total compression cost (the schedule criterion) is less than or equal to a fixed amount.     

Strongly asymptotically optimal design and control of production and service systems

In this paper we consider production and service systems that can be modeled as single or multiple stage queueing networks. We provide a formal definition of strong asymptotic optimality in the context of design and control of such queueing systems. We describe a simple approach to obtain strongly asymptotically optimal design and control policies for these systems. We illustrate our approach through some examples. In particular we obtain a strongly asymptotically optimal workload allocation for a multiple center service system modeled by the open Jackson network. The objective here is to minimize the expected total holding cost. A simple counter example shows that the much celebrated balanced workload allocation is not even asymptotically optimal for minimizing the expected number of jobs in the system. We show that an index policy is strongly asymptotically optimal for the scheduling control problem in a single stage (G/GI/1) service system. We also obtain a strongly asymptotically optimal allocation of classes of customers to a multiple center service system. This allocation agrees with the traditional wisdom of forming service stations to process similar tasks that reduce fluctuations in processing times. Suggestions for further work on this topic are summarized as well.     

Bicriteria scheduling in a two-machine permutation flowshop

In this paper we consider a production scheduling problem in a two-machine flowshop. The bicriteria objective is a linear combination or weighted sum of the makespan and total completion time. This problem is computationally hard because the special case concerning the minimization of the total completion time is already known to be strongly NP-hard. To find an optimal schedule, we deploy the Johnson algorithm and a lower bound scheme that was previously developed for total completion time scheduling. Computational experiments are presented to study the relative performance of different lower bounds. While the best known bound for the bicriteria problem can successfully solve test cases of 10 jobs within a time limit of 30?min, under the same setting our branch-and-bound algorithm solely equipped with the new scheme can produce optimal schedules for most instances with 30 or less jobs. The results demonstrate the convincing capability of the lower bound scheme in curtailing unnecessary branching during problem-solving sessions. The computational experience also suggests the practical significance and potential implications of this scheme.     

Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect

This article addresses the no-wait flowshop scheduling problem with simultaneous consideration of common due date assignment, convex resource allocation and learning effect in a two machine setting. The processing time of each job can be controlled by its position in a sequence and also by allocating extra resource, which is a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the optimal common due date, the resource allocation and the schedule of jobs such that the total earliness, tardiness and common due date cost (the total resource consumption cost) are minimized under the constraint condition that the total resource consumption cost (the total earliness, tardiness and common due date cost) is limited. Polynomial time algorithms are developed for two versions of the problem.     

Sequencing n Products Involving m Independent Jobs on m Machines

This article considers the problem of scheduling n products over m distinct machines. Every product consists of a set of jobs, each requiring a known processing time on a designated machine. There are no precedence constraints, and simultaneous processing of jobs requiring different machines within a product is allowed. The object of scheduling is to minimize a regular measure of performance associated with the products. It is shown that there exists an optimal schedule with the “no passing property.” Branch and bound routines are developed for finding the optimal solution for the two measures of performance: (1) total penalty cost; and (2) sum of product completion times. Comparisons between the optimal solution and solutions obtained using dispatching rules are given in the penalty cost case.     

Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions

In this paper, we consider unrelated parallel-machine scheduling involving controllable processing times and rate-modifying activities simultaneously. We assume that the actual processing time of a job can be compressed by allocating a greater amount of a common resource to process the job. We further assume that each machine may require a rate-modifying activity during the scheduling horizon. The objective is to determine the optimal job compressions, the optimal positions of the rate-modifying activities and the optimal schedule to minimise a total cost function that depends on the total completion time and total job compressions. If the number of machines is a given constant, we propose an efficient polynomial time algorithm to solve the problem.     

单台机器排序问题关于加工时间的反问题

本文研究单台机器总完工时间排序问题关于加工时间的反问题,研究尽量"小"地调整工件的加工时间使给定工件的加工次序成为最优的排序。我们考虑尽量"小"地调整是分别使最大带权相对离差的绝对值为最小、使总的带权相对离差的绝对值为最小或者使总的带权相对离差的平方为最小等三种情况。通过把问题转化成数学规划,我们分别指出这三种情况下的三个反问题都可以在多项式时间内求解。     

A ROLLING HORIZON HEURISTIC FOR REACTIVE SCHEDULING OF BATCH PROCESS OPERATIONS

Batch chemical plants are dynamic processing facilities where static production schedules can rarely be adhered to due to market and operating uncertainties. On-line schedule modification of a prior; timing assignments and resource allocations in response to unantipicated disruptions is done through a decomposition heuristic that uses a rolling horizon implementation policy. An attempt is made to minimize the impact of the disruptions on the original schedule near the point of each deviation while exploiting the combinatorial flexibility of task and resource reassignments in future scheduling time windows. The problem is addressed as a multiobjective optimization problem involving completion time criteria, relative customer importance, and production cost considerations.

A rigorous analysis of problem sensitive parameters, including penalty weights and subhorizon length, is conducted. A model plant case study is performed. Variations on storage availability and task flexibility are investigated in an attempt to characterize dominant effects of the weighting parameters. Results indicate that user preference can serve as a strong guide for obtaining near optimal reactive scheduling solutions. It is shown that the combinatories can be controlled and that costly and inefficient full scale rescheduling of multipurpose production facilities can be avoided.     

Convex resource allocation scheduling in the no-wait flowshop with common flow allowance and learning effect

We study the problem of two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times. Under the condition of the due-date assignment with common flow allowance (i.e. slack (SLK) due-date assignment), we provide a bi-criteria analysis where the first criterion is to minimise the scheduling criteria (i.e. the weighted sum of earliness, tardiness and flow allowance costs), and the second criterion is to minimise the resource consumption cost (i.e. the weighted sum of resource consumption cost). The objective is to determine the optimal job sequence, resource allocations and common (flow allowance) slack time that minimise the three different versions of the two criteria. We prove that these problems can be solved in polynomial time.     

An application of genetic algorithms to lot-streaming flow shop scheduling

A Hybrid Genetic Algorithm (HGA) approach is proposed for a lot-streaming flow shop scheduling problem, in which a job (lot) is split into a number of smaller sublots so that successive operations can be overlapped. The objective is the minimization of the mean weighted absolute deviation of job completion times from due dates. This performance criterion has been shown to be non-regular and requires a search among schedules with intermittent idle times to find an optimal solution. For a given job sequence, a Linear Programming (LP) formulation is presented to obtain optimal sublot completion times. Objective function values of LP solutions are used to guide the HGA's search toward the best sequence. The performance of the HGA approach is compared with that of a pairwise interchange method.     

关于工期分配与加权误工数的双指标排序问题

排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡,由此提出工期分配的双目标排序问题。关于工期分配与加权误工数的单机双指标排序问题,文献中只研究了其线性组合形式。针对该问题,本文针对约束形式及Pareto优化形式进一步研究了更多的模型。主要结果包括NP-困难性、多项式可解情形以及多项式时间近似方案等结果。通过这些结果,一个多目标优化问题的特征得以完整地刻画。     

Scheduling a batch processing machine with non-identical job sizes

The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with arbitrary job processing times, job weights and job sizes. The scheduling objective is to minimize total weighted completion time. We find that the procedure returns optimal solutions to problems of up to 25 jobs in reasonable CPU time, and can be adapted for use as a heuristic for larger problems.     

Minimizing makespan subject to minimum total absolute deviation of completion time on identical parallel machines

This study addresses the identical parallel machine scheduling problem with the objective of minimizing makespan subject to minimum total absolute deviation of job completion time (TADC). An optimization algorithm is first proposed to solve TADC on an identical parallel machine and an iterative procedure based on a polynomial binary integer programming model is then proposed to minimize makespan. Computational experiments show that the proposed algorithm is efficient. The worst case performance, which refers to the largest average execution for each scenario of the experiments, is 229.10 seconds for the problem with n=200, m=30 and p _j from a uniform [1, 100].     

Minimizing the Weighted Sum of Late and Early Completion Penalties in a Single Machine

We consider the problem of scheduling n jobs on a single machine so as to minimize weighted absolute deviation of completion times from their due dates. The general problem is NP-complete, but we show how to solve a special case.     

Single machine batch scheduling with sequential job processing

The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both the bounded and unbounded problems in which all due dates and/or processing times are equal. Several special cases of the bounded problem are shown to be NP-hard. Thus, a comprehensive classification of the computational complexities of the special cases is provided.     

The no-wait two-machine flow shop scheduling problem with convex resource-dependent processing times

We extend the classical no-wait two-machine flow shop scheduling problem to the case where job-processing times are controllable through the allocation of a common, limited and nonrenewable resource. Our objective is to simultaneously determine the sequence of the jobs and the resource allocation for each job on both machines in order to minimize the makespan. By using the equivalent load method to obtain the optimal resource allocation on a series-parallel graph, we reduce the problem to a sequencing one and show that it is equivalent to a new special case of the Traveling Salesman Problem (TSP). We prove that although the reduced problem forms a subclass of the TSP on permuted Monge matrices, it is still strongly NP-hard. We provide an approximation result and present three special cases which are polynomially solvable. We have also tested two different subtour-patching heuristics in large-scale computational experiments on randomly generated instances of the problem. Both heuristics produced close-to-optimal solutions in most cases.