Bicriteria scheduling problem for unrelated parallel machines with release dates

This research proposes a heuristic and a tabu search algorithm (TSA) to find non-dominated solutions to bicriteria unrelated parallel machine scheduling problems with release dates. The two objective functions considered in this problem are to minimize both makespan and total weighted tardiness. The computational results show that the proposed heuristic is computationally efficient and provides solutions of reasonable quality. The proposed TSA outperforms other algorithms in terms of the number of non-dominated solutions and the quality of its solutions.     

A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates

In this paper, we consider an identical parallel machine scheduling problem with release dates. The objective is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose some dominance properties and two lower bounds. We also present an efficient heuristic. A branch-and-bound algorithm, in which the heuristic, the lower bounds and the dominance properties are incorporated, is proposed and tested on a large set of randomly generated instances.     

An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem

In this work, we tackle the problem of scheduling a set of jobs on a set of unrelated parallel machines with minimising the total weighted completion times as performance criteria. The iterated greedy metaheuristic generates a sequence of solutions by iterating over a constructive heuristic using destruction and construction phases. In the last few years, iterated greedy has been employed to solve a considerable number of problems. This is because it is based on a very simple principle, it is easy to implement, and it often exhibits an excellent performance. Moreover, scalability for high-dimensional problems becomes an essential requirement for modern optimisation algorithms. This paper proposes an iterated greedy model for the above-mentioned scheduling problem to tackle large-size instances. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown.     

Two branch-and-bound algorithms for the robust parallel machine scheduling problem

Uncertainty is an inevitable element in many practical production planning and scheduling environments. When a due date is predetermined for performing a set of jobs for a customer, production managers are often concerned with establishing a schedule with the highest possible confidence of meeting the due date. In this paper, we study the problem of scheduling a given number of jobs on a specified number of identical parallel machines when the processing time of each job is stochastic. Our goal is to find a robust schedule that maximizes the customer service level, which is the probability of the makespan not exceeding the due date. We develop two branch-and-bound algorithms for finding an optimal solution; the two algorithms differ mainly in their branching scheme. We generate a set of benchmark instances and compare the performance of the algorithms based on this dataset.     

A branch-and-price algorithm for the general case of scheduling parallel machines with a single server

We consider the strongly NP-hard problem of scheduling two-operation non-preemptable jobs on two identical parallel machines. A single server, that can handle at most one job at a time, is available to carry out the first (or setup) operation. The second operation, to be carried out on the same machine but without the server, must be executed immediately after the setup. The objective is to minimize the makespan. We apply a column generation method to a population of partial schedules, in turn generated by some well known heuristics, to achieve effective and efficient solutions. We compare the performance of this method with those proposed earlier and also suggest future work.     

An improved heuristic for parallel machine weighted flowtime scheduling with family set-up times

This paper studies the identical parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted completion time (weighted flowtime). The family set-up time is incurred whenever there is a switch of processing from a job in one family to a job in another family. A heuristic is proposed in this paper for the problem. Computational results show that the proposed heuristic outperforms an existing heuristic, especially for large-sized problems, in terms of both solution quality and computation times. The improvement of solution quality is as high as 4.753% for six-machine problem and 7.822% for nine-machine problem, while the proposed heuristic runs three times faster than the existing one.     

Tabu search for scheduling on identical parallel machines to minimize mean tardiness

This paper presents a tabu search approach for scheduling jobs on identical parallel machines with the objective of minimizing the mean tardiness. Initially, we consider a basic tabu search that uses short term memory only. Local search is performed on a neighborhood defined by two types of moves. Insert moves consist of transferring each job from one machine to another and swap moves are those obtained by exchanging each pair of jobs between two machines. Next, we analyze the incorporation of two diversification strategies with the aim of exploring unvisited regions of the solution space. The first strategy uses long term memory to store the frequency of the moves executed throughout the search and the second makes use of influential moves. Computational tests are performed on problems with up to 10 machines and 150 jobs. The heuristic performance is evaluated through a lower bound given by Lagrangean relaxation. A comparison is also made with respect to the best constructive heuristic reported in the literature.     

Minimum deviation algorithm for two-stageno-wait flowshops with parallel machines

The scheduling problems studied in this paper concern the two-stage no-wait flowshops with parallel machines under the objective function of the minimization of the maximum completion time. A new heuristic algorithm, i.e., the minimum deviation algorithm, is developed to solve the problems. In order to evaluate the average case performance of the algorithm, we design numerical experiments to compare the effectiveness of the algorithm with that of the other approximation algorithms. Extensive simulations are conducted under different shop conditions, and the results statistically show that the minimum deviation algorithm performs well under most of the situations.     

Online batch scheduling on parallel machines with delivery times

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1).     

Makespan minimization for two parallel machines scheduling with a periodic availability constraint

A two parallel machines scheduling problem where one machine is periodically unavailable with the objective of minimizing makespan is considered. It is showed that the worst-case ratio of the classical LPT algorithm and the competitive ratio of the LS algorithm are 3/2 and 2, respectively, for the offline version and the online version of the problem.     

Soft computing for scheduling with batch setup times and earliness-tardiness penalties on parallel machines

A model for scheduling grouped jobs on identical parallel machines is addressed in this paper. The model assumes that a set-up time is incurred when a machine changes from processing one type of component to a different type of component, and the objective is to minimize the total earliness-tardiness penalties. In this paper, the algorithm of soft computing, which is a fuzzy logic embedded Genetic Algorithm is developed to solve the problem. The efficiency of this approach is tested on several groups of random problems and shows that the soft computing algorithm has potential for practical applications in larger scale production systems.     

MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server

This paper considers the identical parallel machines scheduling problem (PMSP) with a single server in charge of job setups. A job can be processed with a precedent setup by a server on one of the machines. The setup can be processed at only one machine at any time. In this paper, the problem P, S1|s_j|C_max with a general job set is formulated using mixed integer programming in two ways. The first one is developed by taking into account the characteristics of the single server problem, and the second one is developed by adding the concept of the server waiting time suggested by Abdekhodaee and Wirth (2002) [3]. Abdekhodaee and Wirth (2002) [3] define the equation of the server waiting time applied to only the special case with two machines and a regular job set. The general model for several machines is studied in this paper by developing the properties on the server waiting time. The hybrid heuristic algorithm is developed for the practical use, which can yield a near-optimal schedule in a reasonable computational time. The performance of algorithm is evaluated by comparing with the results of MIP models and heuristics appearing in the literature.     

Size-reduction heuristics for the unrelated parallel machines scheduling problem

In this paper we study the unrelated parallel machines problem where n independent jobs must be assigned to one out of m parallel machines and the processing time of each job differs from machine to machine. We deal with the objective of the minimisation of the maximum completion time of the jobs, usually referred to as makespan or C_max. This is a type of assignment problem that has been frequently studied in the scientific literature due to its many potential applications. We propose a set of metaheuristics based on a size-reduction of the original assignment problem that produce solutions of very good quality in a short amount of time. The underlying idea is to consider only a few of the best possible machine assignments for the jobs and not all of them. The results are simple, yet powerful methods. We test the proposed algorithms with a large benchmark of instances and compare them with current state-of-the-art methods. In most cases, the proposed size-reduction algorithms produce results that are statistically proven to be better by a significant margin.     

基于到达时间两台并行机上在线批调度

考虑两台同构并行机上在线批调度问题．每个批具有不确定的到达时间,一旦机器可以利用,要在当前可以利用的批中选择出合适的批,并将其中的工件调度到机器上,且工件在加工过程中不允许中断．目标函数是使调度的最大完成时间最小．给出了一个批在线调度ＲＢＬＰＴ算法,即选择当前批中加工时间之和最大的批按ＬＰＴ 规则调度．另外,利用反证法,对算法的最坏情况进行了分析．     

Using quadratic programming to solve high multiplicity scheduling problems on parallel machines

We introduce and analyze several models of schedulingn different types (groups) of jobs onm parallel machines, where in each group all jobs are identical. Our main goal is to exhibit the usefulness of quadratic programming approaches to solve these classes of high multiplicity scheduling problems, with the total weighted completion time as the minimization criterion. We develop polynomial algorithms for some models, and strongly polynomial algorithms for certain special cases. In particular, the model in which the weights are job independent, as well as the generally weighted model in which processing requirements are job independent, can be formulated as an integer convex separable quadratic cost flow problem, and therefore solved in polynomial time. When we specialize further, strongly polynomial bounds are achievable. Specifically, for the weighted model with job-independent processing requirements if we restrict the weights to be machine independent (while still assuming different machine speeds), anO(mn+n logn) algorithm is developed. If it is also assumed that all the machines have the same speed, the complexity of the algorithm can be improved toO(m logm+n logn). These results can be extended to related unweighted models with variable processing requirements in which all the machines are available at time zero. The research of Frieda Granot was partially supported by Natural Sciences and Engineering Research Council of Canada Grant 5-83998. The research of Jadranka Skorin-Kapov was partially supported by National Science Foundation Grant DDM-8909206.     

Generating subproblems in branch and bound algorithms for parallel machines scheduling problem

A branch and bound algorithm (B&B) has been widely used in various discrete and combinatorial optimization fields. To obtain optimal solutions as soon as possible for scheduling problems, three tools, which are branching, bounding and dominance rules, have been developed in the B&B algorithm. One of these tools, a branching is a method for generating subproblems and directly determines size of solution to be searched in the B&B algorithm. Therefore, it is very important to devise effective branching scheme for the problem.In this note, a survey of branching schemes is performed for parallel machines scheduling (PMS) problems with n independent jobs and m machines and new branching schemes that can be used for identical and unrelated PMS problems, respectively, are suggested. The suggested branching methods show that numbers of generated subproblems are much smaller than that of other methods developed earlier and therefore, it is expected that they help to reduce a lot of CPU time required to obtain optimal solutions in the B&B algorithm.     

A note: Simple heuristics for scheduling a maintenance activity on unrelated machines

Following several recent papers discussing various problems of scheduling a maintenance activity, we focus here on scheduling a maintenance activity on unrelated parallel machines. The objective is to minimize flow-time. In the basic setting, we assume that all the machines must be maintained simultaneously. The problem is known to be NP-hard, and we introduce and test numerically an efficient heuristic and a lower bound, both based on a solution of a matching problem. We also study the relaxed version, where the machines are not restricted to be maintained at the same time. Similar heuristic and lower bound are proposed and tested.