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.     

Scheduling two parallel machines with a single server: the general case

This paper considers the problem of scheduling two-operation non-preemptable jobs on two identical semi-automatic machines. A single server is available to carry out the first (or setup) operation. The second operation is executed automatically, without the server. The general problem of makespan minimization is NP-hard in the strong sense. In earlier work, we showed that the equal total length problem is polynomial time and we also provided efficient and effective solutions for the special cases of equal setup and equal processing times. Most of the cases analyzed thus far have fallen into the category of regular problems. In this paper we build on this earlier work to deal with the general case. Various approaches will be considered. One may reduce the problem to a regular one by amalgamating jobs, or we may apply the earlier heuristics to (possibly regular) job clusters. Alternately we may apply a greedy heuristic, a metaheuristic such as a genetic algorithm or the well known Gilmore–Gomory algorithm to solve the general problem. We report on the performance of these various methods.     

Scheduling reentrant jobs on parallel machines with a remote server

This paper explores a specific combinatorial problem relating to reentrant jobs on parallel primary machines, with a remote server machine. A middle operation is required by each job on the server before it returns to its primary processing machine. The problem, which is new to the literature, is inspired by the logistics of a semi-automated microbiology laboratory. We establish the NP-hard nature of the problem, and demonstrate various structural properties. A heuristic is developed and tested on randomly generated benchmark data. No alternative heuristics are available in the literature for comparison, but results indicate solutions reliably within 1.5% of optimum. Moreover, tests of our heuristic on real-life data from the microbiology laboratory provide a 20% improvement in throughput relative to current practice.     

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.     

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.     

Scheduling jobs with equal processing times and time windows on identical parallel machines

We present a linear programming approach to the problem of scheduling equal processing time jobs with release dates and deadlines on identical parallel machines. The known algorithm with complexity O(n ³log log n) of B. Simons schedules all the jobs while minimizing both the maximum completion time and the mean flow time. Our approach permits also to minimize the weighted sum of completion times and total tardiness in polynomial time for the problems without deadlines. The complexity status of these problems was open. Contract/grant sponsor: Alexander von Humboldt Foundation.     

提前/延期惩罚最小化互替机床调度算法

对经提前/延期（E/T）惩罚最小为目标的互替机床调度问题进行了分析,对互替机床E/T调度问题进行了描述,提出了解决调度问题的具体策略,在此基础上,建立了基于启发式的互替机床E/T调度算法,最后通过仿真实验验证了本算法的有效性和实用性。     

Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem

We present computational results with a heuristic algorithm for the parallel machines total weighted tardiness problem. The algorithm combines generalized pairwise interchange neighborhoods, dynasearch optimization and a new machine-based neighborhood whose size is non-polynomial in the number of machines. The computational results significantly improve over the current state of the art for this problem.     

Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates

We address the parallel machine total weighted tardiness scheduling problem with release dates. We describe dominance rules and filtering methods for this problem. Most of them are adaptations of dominance rules based on solution methods for the single-machine problem. We show how it is possible to deduce whether or not certain jobs can be processed by a particular machine in a particular context and we describe techniques that use this information to improve the dominance rules. On the basis of these techniques we describe an enumeration procedure and we provide experimental results to determine the effectiveness of the dominance rules.     

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 hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.     

Scheduling jobs on parallel machines with setup times and ready times

In this research we are interested in scheduling jobs with ready times on identical parallel machines with sequence dependent setups. Our objective is to minimize the total weighted tardiness. As this problem is NP-Hard, we develop a heuristic to solve this problem in reasonable time. Our approach is an extension of the apparent tardiness cost with setups (ATCS) approach by [Lee, Y. H., Pinedo, M. (1997). Scheduling jobs on parallel machines with sequence dependent setup times. European Journal of Operational Research, 100, 464–474.] to allow non-ready jobs to be scheduled – meaning we allow a machine to remain idle for a high priority job arriving at a later time. To determine the scaling parameters for our composite dispatching rule (called ATCSR), we first develop a ‘grid approach’ that considers multiple values for the scaling parameters, generates multiple schedules, and chooses the best schedule for the solution. This experimentation was then used to develop regression equations to predict the values of the scaling parameters that would yield the highest quality solution. The grid and regression versions of ATCSR provide better performance than grid and empirically based formula versions of ATCS, BATCS, and X-RM which are the prominent algorithms in the literature.     

Parallel machine scheduling with flexible resources

Parallel machine flexible resource scheduling (PMFRS) problems consider an additional flexible resource (e.g. operators), which can be freely allocated to any jobs and/or any machines and may speed-up the process in proportion to its amount. If job–machine assignment is unspecified, the problem is referred to as unspecified PMFRS (UPMFRS). This paper reviews the mathematical models of both PMFRS and UPMFRS problems in the literature and not only gives some extensions to the model of dynamic PMFRS problem but also presents integer programming (IP) models for static and dynamic UPMFRS problems with the objective of minimizing makespan. To solve large-sized dynamic PMFRS and UPMFRS problems, a relaxed IP based constraint programming (CP) approach is also proposed. All IP models and the proposed IP/CP approach are tested with an extensive computational study. The results of the computational experiments are discussed with respect to the major parameters of the problem and conclusions are drawn.     

The worst-case analysis of the Garey–Johnson algorithm

The Garey–Johnson algorithm is a well known polynomial-time algorithm constructing an optimal schedule for the maximum lateness problem with unit execution time tasks, two parallel identical processors, precedence constraints and release times. The paper is concerned with the worst-case analysis of a generalization of the Garey–Johnson algorithm to the case of arbitrary number of processors. In contrast to other algorithms for the maximum lateness problem, the tight performance guarantee for the even number of processors differs from the tight performance guarantee for the odd number of processors.     

基于粗糙规划的不确定加工时间的并行机调度

针对并行机调度中的不确定工件加工时间,提出用粗糙变量表示不确定量,并由此建立该问题的粗糙期望值规划模型.提出一种应用于调度问题的进化规划算法,改进了针对并行机问题的编码方式和变异方法.采用粗糙模拟的方法计算个体的适应值,即粗糙期望估计值,并加以不同规模的算例进行仿真实验.仿真结果表明,改进进化规划算法得到的解优于遗传算法得到的解.     

Scheduling identical parallel machines and operators within a period based changing mode

This article addresses the problem of scheduling n non-preemptive jobs on m identical parallel machines with ω operators to minimize the makespan. The number of operators is less than the number of machines. As a result, it may happen that an operator has to supervise simultaneously several machines. This in turn has an impact on the job processing times as they become a function of the operators modus operandi. In this paper we consider the case where each modus operandi can only be changed at the end of a given period, i.e., a period based changing mode. We present heuristic algorithms to solve this problem. An experimental study is conducted to evaluate the performance of these heuristics in the average case, and a worst case analysis is presented for one of them.     

A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property

We focus on the problem of scheduling n independent jobs on m identical parallel machines with the objective of minimizing total tardiness of the jobs considering a job splitting property. In this problem, it is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We develop several dominance properties and lower bounds for the problem, and suggest a branch and bound algorithm using them. Computational experiments are performed on randomly generated test problems and results show that the suggested algorithm solves problems of moderate sizes in a reasonable amount of computation time.