非同类机极小化最大完工时间的保密排序问题

提出并研究了一类非同类机的极小化最大完工时间的保密排序问题Rm||Cmax.该问题的模型参数分为若干组,每个组都由一个不愿意共享或公开自己数据的单位所拥有.基于随机矩阵变换构造了一个不泄露私有数据且与原问题等价的安全规划模型,求解该安全模型可以获得问题的最优解,而且各单位的隐私数据仍然保持不被泄露.     

Analysis of a linear programming heuristic for scheduling unrelated parallel machines

Each of n jobs is to be processed without interruption on one of m unrelated parallel machines. The objectives is to minimize the maximum completion time. A heuristic method is presented, the first stage of which uses linear programming to form a partial schedule leaving at most m?1 jobs unscheduled: the second stage schedules these m?1 jobs using an enumerative method. For m≥3, it is shown that the heuristic has a (best possible) worst-case performance ratio of 2 and has a computational requirement which is polynomial in n although it is exponential in m. For m = 2, it is shown that the heuristic has a (best possible) worst-case performance ratio of $\text{1 +}\text{5}\text{)}\text{2}$ and requires linear time. A modified version of the heuristic is presented for m = 2 which is shown to have a (best possible) worst-case performance ratio of $\text{3}\text{2}$ while still requiring linear time.     

Multiple-objective heuristics for scheduling unrelated parallel machines

This research proposes two heuristics and a Genetic Algorithm (GA) to find non-dominated solutions to multiple-objective unrelated parallel machine scheduling problems. Three criteria are of interest, namely: makespan, total weighted completion time, and total weighted tardiness. Each heuristic seeks to simultaneously minimize a pair of these criteria; the GA seeks to simultaneously minimize all three. The computational results show that the proposed heuristics are computationally efficient and provide solutions of reasonable quality. The proposed GA outperforms other algorithms in terms of the number of non-dominated solutions and the quality of its solutions.     

Approximation algorithms for scheduling unrelated parallel machines

We consider the following scheduling problem. There arem parallel machines andn independent jobs. Each job is to be assigned to one of the machines. The processing of jobj on machinei requires timep _ij . The objective is to find a schedule that minimizes the makespan.Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints.In contrast to our main result, we prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unlessP = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times.A preliminary version of this paper appeared in theProceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science (Computer Society Press of the IEEE, Washington, D.C., 1987) pp. 217–224.     

带学习效应的两台平行机时间表长问题

研究机器带学习效应, 目标函数为时间表长的两台平行机排序问题, 问题是NP-难的. 首先建立了求解该问题最优解的整数规划模型. 其次, 基于模拟退火算法给出了该问题的近似算法SA, 并证明了该算法依概率1 全局收敛到最优解. 最后, 通过数值模拟对所提出的算法进行了性能分析. 数值模拟结果表明, 近似算法SA可以达到最优值的99%, 准确度高, 算法较有效.     

Minimizing makespan for two parallel machines with job limit on each availability interval

We consider the problem of scheduling jobs on two parallel machines that are not continuously available for processing. The machine is not available after processing a fixed number of jobs in order to make precision adjustment of machines such as in wafer manufacturing, to reload the feeder in printed circuit board production, or to undertake any other maintenance works such as cleaning and safety inspections. The objective of the problem is to minimize the makespan. Two different scheduling horizons are investigated for this problem. For the short-term scheduling horizon, we consider only the time period before the unavailability interval, while for the long-term horizon, machines are allowed to restart processing after the unavailability interval. For both cases, which are strongly NP-hard, exact optimization algorithms based on the branch and bound method are proposed. Although the algorithms have exponential time complexities, computational results show that they can solve optimally the various-sized problems in reasonable computation time.     

List scheduling algorithms to minimize the makespan on identical parallel machines

In this paper we present constructive algorithms for the classical deterministic scheduling problem of minimizing the makespan on identical machines. Since the problem is known to beNP-hard in the strong sense, the approximate algorithms play a relevant role when solving this problem. The proposed algorithms are based on list scheduling procedures, but the assignment rule is not the same for the full set of jobs. Computational results show that these algorithms perform very well. This research has been partially supported by the Research Project H015/2000, Universidad de Alcalá. The authors are indebted to Joaquín Pérez and the referees for their helpful remarks and comments. We also wish to thank Paul Alexander Ayres for his help in the correct use of English.     

Scheduling under a common due-data on parallel unrelated machines

Due-data determination problems have gained significant attention in recent years due to the industrial focus in the just-in-time philosophy. In this paper the problem of scheduling a set of independent jobs on parallel unrelated processors under a common due-date is examined. The common due-date is a decision variable. The objective is to allocate and sequence the jobs on the machines and to determine the optimal due-data, so that the total cost be minimised. This cost is composed of the due-date assignment, the total earliness and the total tardiness cost. As the problem is NP-hard, a polynomial time heuristic procedure, which provides efficient solutions, is developed. The procedure is illustrated by means of an example and is tested via two small size experiments.     

Scheduling tasks with exponential duration on unrelated parallel machines

This paper introduces a stochastic scheduling problem. In this problem a directed acyclic graphs (DAG) represents the precedence relations among $m$ tasks that $n$ workers are scheduled to execute. The question is to find a schedule $\Sigma$ such that if tasks are assigned to workers according to $\Sigma$, the expected time needed to execute all the tasks is minimized. The time needed to execute task $t$ by worker $w$ is a random variable expressed by a negative exponential distribution with parameter ${\lambda }_{wt}$ and each task can be executed by more than one worker at a time. In this paper, we will prove that the problem in its general form is NP-hard, but when the DAG width is constant, we will show that the optimum schedules can be found in polynomial time.     

Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software.     

A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines

This paper addresses the capacitated lot-sizing problem involving the production of multiple items on unrelated parallel machines. A production plan should be determined in order to meet the forecast demand for the items, without exceeding the capacity of the machines and minimize the sum of production, setup and inventory costs. A heuristic based on the Lagrangian relaxation of the capacity constraints and subgradient optimization is proposed. Initially, the heuristic is tested on instances of the single machine problem and results are compared with heuristics from the literature. For parallel machines and small problems the heuristic performance is tested against optimal solutions, and for larger problems it is compared with the lower bound provided by the Lagrangian relaxation.     

Bicriteria optimisation of the makespan and mean flowtime on two identical parallel machines

This paper proposes an efficient algorithm to solve optimally the bicriteria problem of minimising the weighted sum of makespan and mean flowtime on two identical parallel machines. The proposed algorithm allows the decision-maker to minimise makespan and flowtime simultaneously according to his or her relative preference as reflected through the weights placed on makespan and flowtime. Our computational results show that the proposed algorithm can solve optimally problem instances with a large number of jobs in a reasonably small amount of CPU time.     

A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines

We study the problem of scheduling n non-preemptive jobs on m unrelated parallel machines. Each machine can process a specified subset of the jobs. If a job is assigned to a machine, then it occupies a specified time interval on the machine. Each assignment of a job to a machine yields a value. The objective is to find a subset of the jobs and their feasible assignments to the machines such that the total value is maximized. The problem is NP-hard in the strong sense. We reduce the problem to finding a maximum weight clique in a graph and survey available solution methods. Furthermore, based on the peculiar properties of graphs, we propose an exact solution algorithm and five heuristics. We conduct computer experiments to assess the performance of our and other existing heuristics. The computational results show that our heuristics outperform the existing heuristics.     

Scheduling deteriorating jobs with a learning effect on unrelated parallel machines

In this study we consider unrelated parallel machines scheduling problems with learning effect and deteriorating jobs, in which the actual processing time of a job is a function of joint time-dependent deterioration and position-dependent learning. The objective is to determine the jobs assigned to corresponding each machine and the corresponding optimal schedule to minimize a cost function containing total completion (waiting) time, total absolute differences in completion (waiting) times and total machine load. If the number of machines is a given constant, we show that the problems can be solved in polynomial time under the time-dependent deterioration and position-dependent learning model.     

On modelling the maximum workload allocation for parallel unrelated machines with setups

Consider a manufacturing process in which a group of machines (or people) perform a single operation on a number of different parts. The processing time depends on both the part and the machine. In addition, each machine requires significant setup time between processing different part types. The problem consists of obtaining a feasible allocation of parts to machines such that the makespan (i.e. greatest machine workload) is minimized. We present two equivalent 0–1 models. The first model arises by considering the assignment of individual parts to machines. It is amenable to Lagrangian decomposition techniques. The second model is more hierarchical in nature; it considers the two options of assigning an entire part type to a single machine, or of splitting the type across machines. The second model is more amenable than the first to branch-and-bound techniques. We report about our computational experience for finding lower bounds of the optimal solution by appending violated cuts and, ultimately, obtaining the optimal solution of real-life problems.     

Scheduling jobs with release dates on parallel batch processing machines to minimize the makespan

Batch processing happens in many different industries, in which a number of jobs are processed simultaneously as a batch. In this paper we develop two heuristics for the problem of scheduling jobs with release dates on parallel batch processing machines to minimize the makespan and analyze their worst-case performance ratios. We also present a polynomial-time optimal algorithm for a special case of the problem where the jobs have equal processing times.     

Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations

In this work, we take advantage of the powerful quadratic programming theory to obtain optimal solutions of scheduling problems. We apply a methodology that starts, in contrast to more classical approaches, by formulating three unrelated parallel machine scheduling problems as 0–1 quadratic programs under linear constraints. By construction, these quadratic programs are non-convex. Therefore, before submitting them to a branch-and-bound procedure, we reformulate them in such a way that we can ensure convexity and a high-quality continuous lower bound. Experimental results show that this methodology is interesting by obtaining the best results in literature for two of the three studied scheduling problems.     

Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes

This paper considers the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makespan and total completion time are given using mixed integer programming method and the computational complexity is analyzed. The bound on the number of feasible solutions is given and the properties of the optimal solutions are presented. Then a polynomial time algorithm is proposed and the worst case ratios for minimizing total completion time and makespan is proved to be 2 and (8/3–2/3 m) respectively. To test the proposed algorithm, we generate different levels of random instances. The computational results demonstrate the effectiveness of the algorithm for minimizing the two objectives.     

Optimal makespan schedule for three jobs on two machines

This paper deals with the problem of scheduling three jobs on two machines in order to minimize the makespan, when operation preemptions are forbidden and routes are fixed and may vary per job. It is shown that this problem can be solved by anO(r ⁴) algorithm, wherer is the maximal number of operations per job. Supported by Belarussian Fundamental Research Found, Project Φ60–242, and Deutsche Forschungsgemeinschaft, Project ScheMA