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.     

基于退化效应的两台机器流水作业可拒绝排序

考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法.     

A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times

This paper deals with hybrid flow-shop scheduling problem with rework. In this problem, jobs are inspected at the last stage, and poorly processed jobs were returned and processed again. Thus, a job may visit a stage more than once, and we have a hybrid flow-shop with re-entrant flow. This kind of a shop may occur in many industries, such as final inspection system in automotive manufacturing. The criterion is to minimize the makespan of the system. We developed a 0–1 mixed-integer program of the problem. Since the hybrid flow-shop scheduling problem is NP-hard, an algorithm for finding an optimal solution in polynomial time does not exist. So we generalized some heuristic methods based on several basic dispatching rules and proposed a variable neighbourhood search (VNS) for the problem with sequence-dependent set-up times and unrelated parallel machines. The computational experiments show that VNS provides better solutions than heuristic methods.     

On the minimization of total weighted flow time with identical and uniform parallel machines

We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances.     

极小化总完工时间的同时加工排序

讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.     

Reduction of job-shop problems to flow-shop problems with precedence constraints

We study the problem of scheduling N independent jobs in a job-shop environment. Each job must be processed on M machines according to individual routes. The objective is to minimize the maximum completion time of the jobs. First, the job-shop problem is reduced to a flow-shop problem with job precedence constraints. Then, a set of flow-shop algorithms are modified to solve it. To evaluate the quality of these heuristics, several lower bounds on the optimal solution have been computed and compared with the heuristic solutions for 3040 problems. The heuristics appear especially promising for job-shop problems with ‘flow-like’ properties.     

Scheduling with unexpected machine breakdowns

We investigate an online version of a basic scheduling problem where a set of jobs has to be scheduled on a number of identical machines so as to minimize the makespan. The job processing times are known in advance and preemption of jobs is allowed. Machines are non-continuously available, i.e., they can break down and recover at arbitrary time instances not known in advance. New machines may be added as well. Thus machine availabilities change online. We first show that no online algorithm can construct optimal schedules. We also show that no online algorithm can achieve a bounded competitive ratio if there may be time intervals where no machine is available. Then we present an online algorithm that constructs schedules with an optimal makespan of C_max^OPT if a lookahead of one is given, i.e., the algorithm always knows the next point in time when the set of available machines changes. Finally, we give an online algorithm without lookahead that constructs schedules with a nearly optimal makespan of C_max^OPT+, for any >0, if at any time at least one machine is available. Our results demonstrate that not knowing machine availabilities in advance is of little harm.     

The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: lower and upper bounds for the random processing time are given before scheduling, but its probability distribution between these bounds is unknown. For such a problem, there often does not exist a dominant schedule that remains optimal for all possible realizations of the job processing times, and we look for a minimal set of schedules that is dominant. Such a minimal dominant set of schedules may be represented by a dominance digraph. We investigate useful properties of such a digraph.     

Integrated machine scheduling and vehicle routing with time windows

This paper integrates production and outbound distribution scheduling in order to minimize total tardiness. The overall problem consists of two subproblems. The first addresses scheduling a set of jobs on parallel machines with machine-dependent ready times. The second focusses on the delivery of completed jobs with a fleet of vehicles which may differ in their loading capacities and ready times. Job-dependent processing times, delivery time windows, service times, and destinations are taken into account. A genetic algorithm approach is introduced to solve the integrated problem as a whole. Two main questions are examined. Are the results of integrating machine scheduling and vehicle routing significantly better than those of classic decomposition approaches which break down the overall problem, solve the two subproblems successively, and merge the subsolutions to form a solution to the overall problem? And if so, is it possible to capitalize on these potentials despite the complexity of the integrated problem? Both questions are tackled by means of a numerical study. The genetic algorithm outperforms the classic decomposition approaches in case of small-size instances and is able to generate relatively good solutions for instances with up to 50 jobs, 5 machines, and 10 vehicles.     

Flow-shop scheduling with a learning effect

The paper is devoted to some flow-shop scheduling problems with a learning effect. The objective is to minimize one of the two regular performance criteria, namely, makespan and total flowtime. A heuristic algorithm with worst-case bound m for each criteria is given, where m is the number of machines. Furthermore, a polynomial algorithm is proposed for both of the special cases: identical processing time on each machine and an increasing series of dominating machines. An example is also constructed to show that the classical Johnson's rule is not the optimal solution for the two-machine flow-shop scheduling to minimize makespan with a learning effect. Some extensions of the problem are also shown.     

Optimal on-line flow time with resource augmentation

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has ? machines. We design an algorithm of competitive ratio , where Δ is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant ?. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only Δ and n are known. This gives a trade-off between the resource augmentation and the competitive ratio.We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has ?m machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time.     

异时排序问题的算法复杂性

我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题．本文我们讨论工件加工时间相同、目标为总完工时间最小的异时排序问题．我们证明了当机器台数为2时,该问题等价于图上的最大匹配问题,因此存在组合强多项式时间算法;但量当机器台数为3或者多于3时,该问题是强NP困难的．     

Two-machine flow-shop scheduling with equal processing time on the second machine for minimizing total weighted completion time

We consider the classical two-machine flow-shop scheduling for minimizing the total weighted completion time. For this problem, the computational complexity of a version in which the jobs have a common processing time on the second machine, has not been addressed. We show that the problem is unary NP-hard, answering an open problem posed in Zhu et al. (2016). Then we present an approximation algorithm for the problem with worst-case performance ratio at most 2.     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.     

Scheduling interfering job sets on parallel machines

We consider bicriteria scheduling on identical parallel machines in a nontraditional context: jobs belong to two disjoint sets, and each set has a different criterion to be minimized. The jobs are all available at time zero and have to be scheduled (non-preemptively) on m parallel machines. The goal is to generate the set of all non-dominated solutions, so the decision maker can evaluate the tradeoffs and choose the schedule to be implemented. We consider the case where, for one of the two sets, the criterion to be minimized is makespan while for the other the total completion time needs to be minimized. Given that the problem is NP-hard, we propose an iterative SPT–LPT–SPT heuristic and a bicriteria genetic algorithm for the problem. Both approaches are designed to exploit the problem structure and generate a set of non-dominated solutions. In the genetic algorithm we use a special encoding scheme and also a unique strategy – based on the properties of a non-dominated solution – to ensure that all parts of the non-dominated front are explored. The heuristic and the genetic algorithm are compared with a time-indexed integer programming formulation for small and large instances. Results indicate that the both the heuristic and the genetic algorithm provide high solution quality and are computationally efficient. The heuristics proposed also have the potential to be generalized for the problem of interfering job sets involving other bicriteria pairs.     

Scheduling open shops with parallel machines to minimize total completion time

This paper explores scheduling a realistic variant of open shops with parallel machines per working stage. Since real production floors seldom employ a single machine for each operation, the regular open shop problem is very often in practice extended with a set of parallel machines at each stage. The purpose of duplicating machines in parallel is to either eliminate or to reduce the impact of bottleneck stages on the overall shop efficiency. The objective is to find the sequence which minimizes total completion times of jobs. We first formulate the problem as an effective mixed integer linear programming model, and then we employ memetic algorithms to solve the problem. We employ Taguchi method to evaluate the effects of different operators and parameters on the performance of memetic algorithm. To further enhance the memetic algorithm, we hybridize it with a simple form of simulated annealing as its local search engine. To assess the performance of the model and algorithms, we establish two computational experiments. The first one is small-sized instances by which the model and general performance of the algorithms are evaluated. The second one consists of large-sized instances by which we further evaluate the algorithms.     

Due-date assignment and parallel-machine scheduling with deteriorating jobs

In this paper we study the problem of scheduling n deteriorating jobs on m identical parallel machines. Each job's processing time is a nondecreasing function of its start time. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of the due-date, earliness and tardiness penalties. We show that this problem is NP-hard, and we present a heuristic algorithm to find near-optimal solutions for the problem. When the due-date penalty is 0, we present a polynomial time algorithm to solve it.     

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.     

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.     

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.