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.     

Unrelated parallel machine scheduling with dedicated machines and common deadline

This paper addresses a scheduling problem in the manufacturing of Polyvinyl Chloride pipes. There are two main attributes of PVC pipes: diameter and color. Each attribute has a corresponding attribute setup time and usually has several different levels. Each extruder produces different PVC pipe products based on the diameters as large, middle and small. The alternatives exist between these extruders, where the large and the middle type extruders can be used to produce the PVC pipes with the other diameters; the small type extruders can be used to produce the PVC pipes with middle diameters but cannot produce those with large diameters. The processing times are longer in all of the alternatives among different types of extruders. The objective is to minimize the total completion time for the unrelated parallel machine problem.Three dedicated machine heuristics are proposed herein for the problem and have been evaluated by comparing with the current scheduling method used in the case plant. The computational results show that the proposed constructive heuristics outperform the current scheduling method with significant improvements and can be used to solve large-size problems in reasonable computational times.     

A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines

In this paper, we study a scheduling problem on identical parallel machines, in which a processing time and a due date are given for each job, and the objective is to maximize the number of just-in-time jobs. A job is called just-in-time if it is completed exactly on its due date. We discuss the known results, show that a recently published greedy algorithm for this problem is incorrect, and present a new quadratic time algorithm which solves the problem.     

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.     

ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times

To date, the topic of unrelated parallel machine scheduling problems with machine-dependent and job sequence-dependent setup times has received relatively little research attention. In this study, a hybrid artificial bee colony (HABC) algorithm is presented to solve this problem with the objective of minimizing the makespan. The performance of the proposed HABC algorithm was evaluated by comparing its solutions to state-of-the-art metaheuristic algorithms and a high performing artificial bee colony (ABC)-based algorithm. Extensive computational results indicate that the proposed HABC algorithm significantly outperforms these best-so-far algorithms. Since the problem addressed in this study is a core topic for numerous industrial applications, this article may help to reduce the gap between theoretical progress and industrial practice.     

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 robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines

This paper dealt with an unrelated parallel machines scheduling problem with past-sequence-dependent setup times, release dates, deteriorating jobs and learning effects, in which the actual processing time of a job on each machine is given as a function of its starting time, release time and position on the corresponding machine. In addition, the setup time of a job on each machine is proportional to the actual processing times of the already processed jobs on the corresponding machine, i.e., the setup times are past-sequence-dependent (p-s-d). The objective is to determine jointly the jobs assigned to each machine and the order of jobs such that the total machine load is minimized. Since the problem is NP-hard, optimal solution for the instances of realistic size cannot be obtained within a reasonable amount of computational time using exact solution approaches. Hence, an efficient method based on the hybrid particle swarm optimization (PSO) and genetic algorithm (GA), denoted by HPSOGA, is proposed to solve the given problem. In view of the fact that efficiency of the meta-heuristic algorithms is significantly depends on the appropriate design of parameters, the Taguchi method is employed to calibrate and select the optimal levels of parameters. The performance of the proposed method is appraised by comparing its results with GA and PSO with and without local search through computational experiments. The computational results for small sized problems show that the mentioned algorithms are fully effective and viable to generate optimal/near optimal solutions, but when the size of the problem is increased, the HPSOGA obtains better results in comparison with other algorithms.     

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.     

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.     

A note on minimizing the normalized sum of squared workload deviations on m parallel processors

In this note we provide a counter-example to a central result by Ho, Tseng, Ruiz-Torres, and López (2009) who proved that a schedule which minimizes the normalized sum of squared workload deviations is necessarily a makespan-optimal one. We explain why their proof is incorrect and present some computational results revealing the difference between workload balancing and makespan minimization.     

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.     

Block models for scheduling jobs on two parallel machines with a single server

We consider the problem of scheduling a set of non-preemptable jobs on two identical parallel machines such that the makespan is minimized. Before processing, each job must be loaded on a machine, which takes a given setup time. All these setups have to be done by a single server which can handle at most one job at a time. For this problem, we propose a mixed integer linear programming formulation based on the idea of decomposing a schedule into a set of blocks. We compare the results obtained by the model suggested with known heuristics from 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).     

解优先级约束并行机调度问题的人工免疫算法

针对家纺企业车间调度的实际情况,建立了优先级特殊工艺约束下并行多机拖后调度模型,并提出一种新颖的人工免疫算法对其求解。该算法是依据生物的免疫机理,将目标函数作为抗原,将问题的解作为抗体,对抗体采用向量组编码的方式进行编码,通过克隆、变异及一种新颖的基于浓度的种群多样性更新选择方法,提高了种群多样性,并通过局部搜索改善了种群质量,加快了收敛速度。仿真结果表明,与遗传算法相比较,该算法能更快更准确地收敛到全局最优解。     

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.     

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.