Using multidimensional scaling to solve traveling salesman and machine scheduling problems

In this note we show how multidimensional scaling can be used to obtain a roadmap corresponding to any general sequencing problem that may be modeled as a traveling salesman problem. Computational results with five well-known classical problems and five randomly generated test problems indicate that this approach provides good solutions with little computation time. It is also shown that equally good solutions may be produced with either ratio scaled data or rank order data.     

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.     

启发式列生成算法求解带恶化效应的同构并行机调度问题

针对实际生产中广泛存在的一类带恶化效应的同构并行机调度问题,以最小化最大完工时间为优化目标,构建该问题的整数规划模型,并提出一种启发式列生成算法(HCGA)进行求解.在HCGA中,首先,利用Dantzig-Wolfe分解方法,将原问题分解为一个主问题(MP)和多个子问题;然后,设计启发式算法获得初始列,其中每列为一台机器上的一个调度方案,基于初始列构建限制主问题(RMP)模型;接着,设计快速有效的动态规划算法求解子问题,以得到需添加至RMP的列集,同时,考虑传统列生成算法收敛速度较慢,设计一系列方法来加速列生成过程;最后,基于所获取的MP线性松弛解,设计深潜启发式算法确定原问题的整数解.HCGA与商用求解器GUROBI的对比实验结果表明,HCGA可在较短时间内获得更优的解.     

Processing time generation schemes for parallel machine scheduling problems with various correlation structures

This research considers the generation of random processing times for parallel machine scheduling problems. We present several processing time generation schemes that consider different levels and combinations of machine correlation and job correlation. Also, metrics to evaluate the amounts of machine relatedness and job uniformity for the randomly generated processing times of a given problem instance are presented. The proposed schemes generate desirable problem instances that can be used to test different solution approaches (such as heuristics, dynamic programming, and branch-and-bound). Computational results indicate that the schemes provide problem instances with many desirable properties.     

改进蚁群算法求解同型机任务调度问题

针对并行与分布式系统中的同型机调度问题,提出了一种改进蚁群算法。结合问题具体特点,给出了蚂蚁分配方案的生成策略,设计了一种新颖的基于任务适合度的信息素表示方法,以实现信息素的有效累积;改进了状态转移规则,通过对阈值的自适应调整使算法能根据搜索进度确定查找区域;在对信息素全局更新前,对每轮迭代获得的最好解进行变邻域搜索,避免算法陷入局部最优,提高收敛速度。仿真结果表明,改进算法有较强的寻优能力和稳定的求解质量。     

Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems

A linguistic-based meta-heuristic modeling and solution approach for solving the flexible job shop scheduling problem (FJSSP) is presented in this study. FJSSP is an extension of the classical job-shop scheduling problem. The problem definition is to assign each operation to a machine out of a set of capable machines (the routing problem) and to order the operations on the machines (the sequencing problem), such that predefined performance measures are optimized. In this research, the scope of the problem is widened by taking into account the alternative process plans for each part (process plan selection problem). Probabilistic selection of alternative process plans and machines are also considered. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls (Baykasolu, 2002). Using these controls and Giffler and Thompson's (1960) priority rule-based heuristic along with the multiple objective tabu search algorithm of Baykasolu et al. (1999) FJSSP is solved. This novel approach simplifies the modeling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its fast solution. Instead of scheduling job shops with inflexible algorithms that cannot take into account the flexibility which is available in the job shop, the present algorithm is developed which can take into account the flexibility during scheduling. Such an approach will considerably increase the responsiveness of the job shops.     

Using distance transform to solve real-time machine vision inspection problems

This paper describes novel solutions to two challenging real-time inspection tasks in machine vision. The first is fast surface approximation for volume and surface area measurements of irregularly shaped objects; the second is fast intensity gradient correction for surface inspection and evaluation of spherical objects. Both solutions apply a distance transform (DT) based on the distance of each image pixel from the object boundary. We describe both real-time machine vision inspection tasks and discuss their complexity. We show that the new solutions result in significant improvements in both accuracy and efficiency—despite the relative simplicity of the DT approach.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective

Single machine scheduling is a classical optimization problem that depicts multiple real life systems in which a single resource (the machine) represents the whole system or the bottleneck operation of the system. In this paper we consider the problem under a weighted completion time performance metric in which the processing time of the tasks to perform (the jobs) are uncertain, but can only take values from closed intervals. The objective is then to find a solution that minimizes the maximum absolute regret for any possible realization of the processing times. We present an exact branch-and-bound method to solve the problem, and conduct a computational experiment to ascertain the possibilities and limitations of the proposed method. The results show that the algorithm is able to optimally solve instances of moderate size (25–40 jobs depending on the characteristics of the instance).     

A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing

In this paper, we propose a metaheuristic for solving an original scheduling problem with auxiliary resources in a photolithography workshop of a semiconductor plant. The photolithography workshop is often a bottleneck, and improving scheduling decisions in this workshop can help to improve indicators of the whole plant. Two optimization criteria are separately considered: the weighted flow time (to minimize) and the number of products that are processed (to maximize). After stating the problem and giving some properties on the solution space, we show how these properties help us to efficiently solve the problem with the proposed memetic algorithm, which has been implemented and tested on large generated instances. Numerical experiments show that good solutions are obtained within a reasonable computational time.     

A new ILS algorithm for parallel machine scheduling problems

This paper addresses the non-preemptive scheduling problem of scheduling jobs on identical parallel machines to minimize the maximum completion time or makespan. The problem has been proved to be NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a new methodology to obtain near-optimal solutions. We formulate the problem as an integer programming and then propose a new iterated local search (ILS) algorithm based on a variable number of cyclic exchanges to solve it. The properties of the solutions are derived and the results are used to improve the computational efficiency of our algorithm. Computational experiments show that the cyclic exchange neighborhood embedded in an iterated local search framework is effective for solving the scheduling problems with up to 1000 jobs and 40 machines within a reasonable amount of computation time. Received: April 2005 / Accepted: January 2006     

Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems

Column generation has proven to be efficient in solving the linear programming relaxation of large scale instances of the multiple-depot vehicle scheduling problem (MDVSP). However difficulties arise when the instances are highly degenerate. Recent research has been devoted to accelerate column generation while remaining within the linear programming framework. This paper presents an efficient approach to solve the linear relaxation of the MDVSP. It combines column generation, preprocessing variable fixing, and stabilization. The outcome shows the great potential of such an approach for degenerate instances.     

Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects

In this paper, we study an unrelated parallel machine scheduling problem with setup time and learning effects simultaneously. The setup time is proportional to the length of the already processed jobs. That is, the setup time of each job is past-sequence-dependent. The objectives are to minimize the total absolute deviation of job completion times and the total load on all machines, respectively. We show that the proposed problem is polynomially solvable. We also discuss two special cases of the problem and show that they can be optimally solved by lower order algorithms.     

An agent-based approach to solve dynamic meeting scheduling problems with preferences

Multi-agent systems are widely used to address large-scale distributed combinatorial applications in the real world. One such application is meeting scheduling (MS), which is defined by a variety of features. The MS problem is naturally distributed and especially subject to many alterations. In addition, this problem is characterized by the presence of users’ preferences that turn it into a search for an optimal rather than a feasible solution. However, in real-world applications users usually have conflicting preferences, which makes the solving process an NP-hard problem. Most research efforts in the literature, adopting agent-based technologies, tackle the MS problem as a static problem. They often share some common properties: allowing the relaxation of any user's time restriction, not dealing with achieving any level of consistency among meetings to enhance the efficiency of the solving process, not tackling the consequences of the dynamic environment, and especially not addressing the real difficulty of distributed systems which is the complexity of message passing operations.In an attempt to facilitate and streamline the process of scheduling meetings in any organization, the main contribution of this work is a new scalable agent-based approach for any dynamic MS problem (that we called MSRAC, for Meeting Scheduling with Reinforcement of Arc Consistency). In this approach we authorize only the relaxation of users’ preferences while maintaining arc-consistency on the problem. The underlying protocol can efficiently reach the optimal solution (satisfying some predefined optimality criteria) whenever possible, using only minimum localized asynchronous communications. This purpose is achieved with minimal message passing while trying to preserve at most the privacy of involved users. Detailed experimental results on randomly generated MS problems show that MSRAC is scalable and it leads to speed up over other approaches, especially for large problems with strong constraints.     

heuristics for parallel machine scheduling with delivery times

A parallel machine scheduling problem is considered in which each job has a processing time and a delivery time. The objective is to find a schedule which minimizes the time by which all jobs are delivered. For a single machine this problem is easily solved in polynomial time, form2 machines it becomes NP-hard. Several heuristics using list scheduling as a subroutine are proposed and a tight worst-case analysis is given. The best one of our heuristics has a worst-case performance guarantee of 2–2/(m+1). For the on-line case we give a heuristic with the (best possible) worst-case performance of two.This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.     

Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems

This research compares the performance of various heuristics and one metaheuristic for unrelated parallel machine scheduling problems. The objective functions to be minimized are makespan, total weighted completion time, and total weighted tardiness. We use the least significant difference (LSD) test to identify robust heuristics that perform significantly better than others for a variety of parallel machine environments with these three performance measures. Computational results show that the proposed metaheuristic outperforms other existing heuristics for each of the three objectives when run with a parameter setting appropriate for the objective.     

Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems

Mixed integer programming (MIP) formulations for scheduling problems can be classified based on the decision variables upon which they rely. In this paper, four different MIP formulations based on four different types of decision variables are presented for various parallel machine scheduling problems. The goal of this research is to identify promising optimization formulation paradigms that can subsequently be used to either (1) solve larger practical scheduling problems of interest to optimality and/or (2) be used to establish tighter lower solution bounds for those under study. We present the computational results and discuss formulation efficacy for total weighted completion time and maximum completion time problems for the identical parallel machine case.     

A hybrid heuristic to solve the parallel machines job-shop scheduling problem

This paper presents an advanced software system for solving the flexible manufacturing systems (FMS) scheduling in a job-shop environment with routing flexibility, where the assignment of operations to identical parallel machines has to be managed, in addition to the traditional sequencing problem. Two of the most promising heuristics from nature for a wide class of combinatorial optimization problems, genetic algorithms (GA) and ant colony optimization (ACO), share data structures and co-evolve in parallel in order to improve the performance of the constituent algorithms. A modular approach is also adopted in order to obtain an easy scalable parallel evolutionary-ant colony framework. The performance of the proposed framework on properly designed benchmark problems is compared with effective GA and ACO approaches taken as algorithm components.