Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.     

Optimal preemptive scheduling on uniform machines with discounted flowtime objectives

We consider the problem of scheduling n jobs on m parallel machines. Each job has a deterministic processing time and a weight associated with it. For uniform machines we show that discounted flowtime is minimized by serving jobs preemptively in increasing order of their remaining processing times, assigning the job with the shortest remaining processing time to the fastest available machine.     

Two-Stage Production Scheduling with Separated Set-up Times and Stochastic Breakdowns

The problem of scheduling a two-machine flowshop, where set-up times are considered as separate from processing times and machines suffer random breakdowns, is addressed with respect to the makespan objective. A dominance relation for minimizing makespan with probability 1 is established. Furthermore, it is shown that Yoshida and Hitomi's algorithm for the deterministic problem stochastically minimizes makespan when random breakdowns are present.     

A class of on-line scheduling algorithms to minimize total completion time

We consider the problem of scheduling jobs on-line on a single machine and on identical machines with the objective to minimize total completion time. We assume that the jobs arrive over time. We give a general 2-competitive algorithm for the single machine problem. The algorithm is based on delaying the release time of the jobs, i.e., making the jobs artificially later available to the on-line scheduler than the actual release times. Our algorithm includes two known algorithms for this problem that apply delay of release times. The proposed algorithm is interesting since it gives the on-line scheduler a whole range of choices for the delays, each of which leading to 2-competitiveness.We also show that the algorithm is 2α competitive for the problem on identical machines where α is the performance ratio of the Shortest Remaining Processing Time first rule for the preemptive relaxation of the problem.     

A bicriteria parallel machine scheduling with a learning effect of setup and removal times

In studies on scheduling problems, generally setup times and removal times of jobs have been neglected or by including those into processing times. However, in some production systems, setup times and removal times are very important such that they should be considered independent from processing times. Since, in general jobs are done according to automatic machine processes in production systems processing times do not differ according to process sequence. But, since human factor becomes influential when setup times and removal times are taken into consideration, setup times will be decreasing by repeating setup processes frequently. This fact is defined with learning effect in scheduling literature. In this study, a bicriteria m-identical parallel machines scheduling problem with a learning effect of setup times and removal times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. A mathematical programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 15 jobs and five machines. We also proposed three heuristic approaches for solving large jobs problems. According to the best of our knowledge, no work exists on the minimization of the weighted sum of total completion time and total tardiness with a learning effect of setup times and removal times.     

Two machine preemptive scheduling problem with release dates,equal processing times and precedence constraints

We consider a scheduling problem with two identical parallel machines and n jobs. For each job we are given its release date when job becomes available for processing. All jobs have equal processing times. Preemptions are allowed. There are precedence constraints between jobs which are given by a (di)graph consisting of a set of outtrees and a number of isolated vertices. The objective is to find a schedule minimizing mean flow time. We suggest an O(n²) algorithm to solve this problem.The suggested algorithm also can be used to solve the related two-machine open shop problem with integer release dates, unit processing times and analogous precedence constraints.     

Scheduling parallel machines with inclusive processing set restrictions and job release times

We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed.     

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.     

A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem

An O(n²) algorithm is presented for the n jobs m parallel machines problem with identical processing times. Due dates for each job are given and the objective is the minimization of the number of late jobs. Preemption is permitted. The problem can be formulated as a maximum flow network model. The optimality proof as well as other properties and a complete example are given.     

需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

Scheduling jobs with release dates on parallel batch processing machines to minimize the makespan

Batch processing happens in many different industries, in which a number of jobs are processed simultaneously as a batch. In this paper we develop two heuristics for the problem of scheduling jobs with release dates on parallel batch processing machines to minimize the makespan and analyze their worst-case performance ratios. We also present a polynomial-time optimal algorithm for a special case of the problem where the jobs have equal processing times.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

Parallel machine scheduling with a convex resource consumption function

We consider some problems of scheduling jobs on identical parallel machines where job-processing times are controllable through the allocation of a nonrenewable common limited resource. The objective is to assign the jobs to the machines, to sequence the jobs on each machine and to allocate the resource so that the makespan or the sum of completion times is minimized. The optimization is done for both preemptive and nonpreemptive jobs. For the makespan problem with nonpreemptive jobs we apply the equivalent load method in order to allocate the resources, and thereby reduce the problem to a combinatorial one. The reduced problem is shown to be NP-hard. If preemptive jobs are allowed, the makespan problem is shown to be solvable in O(n²) time. Some special cases of this problem with precedence constraints are presented and the problem of minimizing the sum of completion times is shown to be solvable in O(n log n) time.     

The routing open-shop problem on a network: Complexity and approximation

In the routing open-shop problem, jobs are located at nodes of an undirected transportation network, and the machines travel on the network to execute jobs in the open-shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a nonpreemptive schedule that minimizes the makespan. We prove that the problem is NP-hard even on a two-node network with two machines, and even on a two-node network with two jobs and m machines. We develop polynomial-time approximation heuristics and obtain bounds on their approximation performance.     

Mixed integer formulation to minimize makespan in a flow shop with batch processing machines

Batch processing machines are commonly used in wafer fabrication, kilns, and chambers used for environmental stress screening (ESS). This paper proposes two models to schedule batches of jobs on two machines in a flow shop. A set of jobs with known processing times and sizes has to be grouped, to form batches, in order to be processed on the batch processing machines. The jobs are nonidentical in size. The processing time of a batch is the longest processing time of all the jobs in that batch. Mixed integer formulations are proposed for the flow shop problem when the buffer capacity is unlimited or zero. Numerical examples are presented to demonstrate the application of our model.     

Bounds for naive multiple machine scheduling with release times and deadlines

We examine an on-line polynomial time heuristic for the NP-complete problem of scheduling m identical machines to minimize the maximum lateness of jobs with release times and due dates. The main result is that for any set of jobs, the difference between the lateness given by the heuristic and the minimum possible lateness is bounded by $\text{[}\text{(2m ? 1)}\text{m}\text{]P}{}_{\mathrm{<mtext>max</mtext>}}$, where P_max is the largest processing time of any of the jobs. The conclusion is that for many applications, optimization is not necessary. We also prove that when all jobs have a common processing time P, the difference between the heuristic and the minimum lateness is bounded by P. This gives a fast estimate of the minimum possible lateness, and is useful in accelerating the practical performance of algorithms for the exact solution.     

具有优先约束的单机随机排序问题

讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

An approximation algorithm for parallel machine scheduling with a common server

In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.