Optimal methods for batch processing problem with makespan and maximum lateness objectives

In this paper we consider the problem of scheduling n jobs on a single batch processing machine in which jobs are ordered by two customers. Jobs belonging to different customers are processed based on their individual criteria. The considered criteria are minimizing makespan and maximum lateness. A batching machine is able to process up to b jobs simultaneously. The processing time of each batch is equal to the longest processing time of jobs in the batch. This kind of batch processing is called parallel batch processing. Optimal methods for three cases are developed: unbounded batch capacity, b > n, with compatible job groups and bounded batch capacity, b  n, with compatible and non compatible job groups. Each job group represents a different class of customers and the concept of being compatible means that jobs which are ordered by different customers are allowed to be processed in a same batch. We propose an optimal method for the problem with incompatible groups and unbounded batches. About the case when groups are incompatible and bounded batches, our proposed method is considered as optimal when the group with maximum lateness objective has identical processing times. We regard this method, however, as a heuristic when these processing times are different. When groups are compatible and batches are bounded we consider another problem by assuming the same processing times for the group which has the maximum lateness objective and propose an optimal method for this problem.     

Single machine batch scheduling to minimize the weighted number of late jobs

The single machine batch scheduling problem to minimize the weighted number of late jobs is studied. In this problem,n jobs have to be processed on a single machine. Each job has a processing time, a due date and a weight. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of this batch is processed. The completion time of each job in the batch coincides with the completion time of the last job in this batch. A job is late if it is completed after its due date. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find a schedule which minimizes the weighted number of late jobs. This problem isNP-hard even if all due dates are equal. For the general case, we present a dynamic programming algorithm which solves the problem with equal weights inO(n ³) time. We formulate a certain scaled problem and show that our dynamic programming algorithm applied to this scaled problem provides a fully polynomial approximation scheme for the original problem. Each algorithm of this scheme has a time requirement ofO(n ³/ +n ³ logn). A side result is anO(n logn) algorithm for the problem of minimizing the maximum weight of late jobs.Supported by INTAS Project 93-257.     

Batch scheduling with controllable setup and processing times to minimize total completion time

We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n³ log n) and O(n⁵) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.     

Asymmetric Earliness and Tardiness Scheduling with Exponential Processing Times on an Unreliable Machine

We address the problem of processing a set of jobs on a single machine under random due dates with a common distribution. The processing times of the jobs are exponentially distributed random variables with means _i , and the machine is subject to stochastic breakdowns governed by a Poisson process. Each job i is associated with a job-dependent weight w _i . The objective is to schedule the jobs so as to minimize the expected sum of the weighted earliness and tardiness costs of all jobs, which are quadratic functions of the deviations of job completion times from the due dates. We show that the problem is NP-complete. Nevertheless, important optimality properties exist, which can be utilized to develop effective algorithms to solve the problem. Specifically, we prove that, in the case where the weights assigned to both the earliness and tardiness are symmetric, an optimal sequence for the problem must be V-shaped with respect to { _i /w _i }, in the sense that the sequence will first process jobs in a nonincreasing order of { _i /w _i } and then in a nondecreasing order of { _i /w _i }. In the case where asymmetric weights are assigned to the earliness and tardiness costs, the optimal sequence must also be V-shaped with respect to { _i /w _i }, if the due dates are exponentially distributed. Dynamic programming algorithms are proposed which can find the best V-shaped sequences.     

工件可转包加工的排序问题研究

研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS).     

Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date

We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems.     

New steps in the amazing world of sequences and schedules

In this paper we consider classical shop problems:n jobs have to be processed onm machines. The processing timep _i,j of jobi on machinej is given for all operations (i, j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). We have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. We introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. We will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, we investigate the problemO∥C _max on an operation set with spanning tree structure. Supported by Deutsche Forschungsgemeinschaft, Project ScheMA     

Minimizing Completion Time Variance with Compressible Processing Times

We introduce a new formulation of the standard completion time variance (CTV) problem with n jobs and one machine, in which the job sequence and the processing times of the jobs are all decision variables. The processing time of job i (i=1, ,n) can be compressed by an amount within [l_i, u_i], which however will incur a compression cost. The compression cost is a general convex non-decreasing function of the amount of the job processing time compressed. The objective is to minimize a weighted combination of the completion time variance and the total compression cost. We show that, under an agreeable condition on the bounds of the processing time compressions, a pseudo-polynomial algorithm can be derived to find an optimal solution for the problem. Based on the pseudo-polynomial time algorithm, two heuristic algorithms H1 and H2 are proposed for the general problem. The relative errors of both heuristic algorithms are guaranteed to be no more than , where is a measure of deviation from the agreeable condition. While H1 can find an optimal solution for the agreeable problem, H2 is dominant for solving the general problem. We also derive a tight lower bound for the optimal solution of the general problem. The performance of H2 is evaluated by complete enumeration for small n, and by comparison with this tight lower bound for large n. Computational results (with n up to 80) are reported, which show that the heuristic algorithm H2 in general can efficiently yield near optimal solutions, when n is large.     

Scheduling uniform machines on-line requires nondecreasing speed ratios

We consider the following on-line scheduling problem. We have to schedulen independent jobs, wheren is unknown, onm uniform parallel machines so as to minimize the makespan; preemption is allowed. Each job becomes available at its release date, and this release date is not known beforehand; its processing requirement becomes known at its arrival. We show that if only a finite number of preemptions is allowed, there exists an algorithm that solves the problem if and only ifs _i–1/s_i s_i/s_i+1 for alli = 2,,m – 1, wheres _i denotes theith largest machine speed. We also show that if this condition is satisfied, then O(mn) preemptions are necessary, and we provide an example to show that this bound is tight. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Asymptotic optimality of statistical multiplexing in pipelined processing

The throughput of pipelined processing ofheterogeneous multitasked jobs is computed and optimized in this study. There areK job classes. Each job hasM tasks which have to be processed in a given order (same for all tasks) on a pipeline ofM processors. Tasks have random processing times. The jobs of each class form a stationary and ergodic sequence (with respect to their task processing times). Classes are differentiated by distinct statistics and may not be jointly stationary or ergodic. Thus, the jobs are overall statistically heterogeneous. We are interested in the average execution time per job , when the job populations of the various classes become very large (asymptotically). This is shown to depend on the order in which jobs enter the pipeline. Under the natural class-based ordering, where all jobs of the first class enter first, followed by those of the second, third, and so on, the quantity is computed, but is shownnot to attain its minimal value in general. On the contrary, appropriate statistical multiplexing of jobs of different classes on the pipeline is shown to minimize the average execution time per job on every sample path (with probability one). The procedure, calledbalanced statistical multiplexing, is constructed and the minimal is computed in terms of the average execution times of the job tasks.     

带交货期的工件族生产与配送的排序问题

本文考虑了多个客户订购不同种类的工件,工件生产完后需要运输到客户的单机供应链排序问题.由于工件属于不同的种类,在加工不同种类工件前要有一个准备时间.每个客户分布在不同位置,客户的每个工件都有一个交货期,工件是分批配送的,每一批配送需要花费一定的时间及费用.考虑了两个与交货期有关的目标函数,分别给出了它们的最优算法.     

Integrated production and delivery scheduling with disjoint windows

Consider a company that manufactures perishable goods. The company relies on a third party to deliver goods, which picks up delivery products at regular or irregular times. At each delivery time, there is a time window that products can be produced to be delivered at that delivery time. The time windows are disjoint. Suppose we have a set of jobs with each job specifying its delivery time, processing time and profit. The company can earn the profit if the job is produced and delivered at its specified delivery time. From the company point of view, we are interested in picking a subset of jobs to produce and deliver so as to maximize the total profit. The unpicked jobs will be discarded without penalty. We consider both the single machine case and the parallel and identical machine case.In this article we consider three kinds of profits: (1) arbitrary profit, (2) equal profit, and (3) profit proportional to its processing time. In the first case, we give a fully polynomial time approximation scheme (FPTAS) for a single machine with running time . Using the bound improvement technique of Kovalyov, the running time can be further reduced to . In the second case, we give an O(nlogn)-time optimal algorithm for a single machine. In the third case, we give an FPTAS for a single machine with running time . All of our algorithms can be extended to parallel and identical machines with a degradation of performance ratios.     

The coordination of transportation and batching scheduling

We study a coordinated scheduling problem of production and transportation in which each job is transported to a single batching machine for further processing. There are m vehicles that transport jobs from the holding area to the batching machine. Each vehicle can transport only one job at a time. The batching machine can process a batch of jobs simultaneously where there is an upper limit on the batch size. Each batch to be processed occurs a processing cost. The problem is to find a joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized. For a special case of the problem where the job assignment to the vehicles is predetermined, we provide a polynomial time algorithm. For the general problem, we prove that it is NP-hard (in the ordinary sense) and present a pseudo-polynomial time algorithm. A fully polynomial time approximation scheme for the general problem is obtained by converting an especially designed pseudo-polynomial dynamic programming algorithm.     

Two-agent scheduling on uniform parallel machines with min-max criteria

We consider the problem of scheduling two agents A and B on a set of m uniform parallel machines. Each agent is assumed to be independent from the other: agent A and agent B are made up of n _A and n _B jobs, respectively. Each job is defined by its processing time and possibly additional data such as a due date, a weight, etc., and must be processed on a single machine. All machines are uniform, i.e. each machine has its own processing speed. Notice that we consider the special case of equal-size jobs, i.e. all jobs share the same processing time. Our goal is to minimize two maximum functions associated with agents A and B and referred to as $F_{max}^{A}=\max_{i\in A} f^{A}_{i}(C_{i})$ and $F_{max}^{B}=\max_{i\in B}f^{B}_{i}(C_{i})$ , respectively, with C _i the completion time of job i and $f_{i}^{X}$ a non-decreasing function. These kinds of problems are called multi-agent scheduling problems. As we are dealing with two conflicting criteria, we focus on the calculation of the strict Pareto optima for the $(F_{max}^{A}, F_{max}^{B} )$ criteria vector. In this paper we develop a minimal complete Pareto set enumeration algorithm with time complexity and memory requirements.     

Balancing Workloads and Minimizing Set-up Costs in the Parallel Processing Shop

This paper presents an optimal scheduling algorithm for minimizing set-up costs in the parallel processing shop while meeting workload balancing restrictions.There are M independent batch type jobs which have sequence dependent set-up costs and N parallel processing machines. Each of the M jobs must be processed on exactly one of the N available machines. It is desirable to minimize total changeover costs with the restriction that each machine workload assignment T _n be within P units of the average machine assignment. The paper describes a static problem in which all jobs are available at time zero. The sequence dependent change over costs are identical for each machine. An extension of the algorithm handles nonidentical processor problems.A combinatorial programming approach to the problem is used. For the special case of identical processors, the problem can be treated as a multi-salesman travelling salesman problem. A general branch and bound algorithm and numerical results are given.     

Outsourcing and scheduling for two-machine ordered flow shop scheduling problems

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement p_j, and machine i a characteristic q_i. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, p_j/q_i. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{p_j, q_i} (min{p_j, q_i}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.     

The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates

Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. According to WSPR, whenever a machine completes a job, the next job assigned to it is the one with the least ratio of processing requirement to weight among all jobs available for processing at this point in time. We analyze the performance of this heuristic and prove that its asymptotic competitive ratio is one for all instances with bounded job processing requirements and weights. This implies that the WSPR algorithm generates a solution whose relative error approaches zero as the number of jobs increases. Our proof does not require any probabilistic assumption on the job parameters and relies extensively on properties of optimal solutions to a single machine relaxation of the problem. Research supported in part by ONR Contracts N00014-90-J-1649 and N00014-95-1-0232, NSF Contracts DDM-9322828, DMI-9732795, DMI-0085683 and DMI-0245352, NUS Academic Research Grant R314-000-046-112, and a research grant from the Natural Sciences and Research Council of Canada (NSERC).     

Updating an optimal structured scheme

An optimal structured schedule at time t is considered for a set of jobs Z with given start and due date [d _i ,D _i ] volumes V_i (volume is defined as the number of homogeneous independent elementary operations of unit length that comprise the job), and penalty functions. The penalty for selecting an element of jobiZ at timet is _i (t). The schedule penalty is the total penalty of all the elements of all the jobs. An optimal schedule is a minimum-penalty schedule. We investigate the impact of changing the volume of a job from the setZ on the structure of the optimal schedule. Algorithms are proposed for handling the modified job set with both reduced and enlarged job volumes. These algorithms require ck computer operations, where k is the number of jobs in the original set, is the change in job volume (expressed by the number of units), andC is a constant.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 151–161, 1981.In conclusion, I would like to acknowledge the valuable attention of K. V. Shakhbazyan.     

On the optimality of static policy in stochastic open shop

Consider n jobs and two machines. Each job has to be processed on both machines. The order in which it is dome is immaterial. However, the decision maker has to decide in advance which jobs will be processes first on machine 1 (2). We assume that processing times on each machine are identically exponentially distributed random variables. We prove that assigning equal number of jobs to be first processed by machine 1 (2) stochastically minimizes the makespan.