Two Machine Scheduling under Disruptions with Transportation Considerations

Effective logistics scheduling requires synchronization of manufacturing and delivery to optimize customer service at minimum total cost. In this paper, we study a new scheduling problem that arises in a disruption environment. Such a problem occurs when a disruption unexpectedly happens, and consequently, some machines become unavailable for certain periods. Jobs that are assigned to the disrupted machines and have not yet been processed can either be moved to other available machines for processing, which may involve additional transportation time and cost, or can be processed by the same machine after the disruption. Our goal is to reschedule jobs so that an objective function, including the original cost function, and possibly transportation costs and disruption cost caused by deviating from the originally planned completion times, is minimized. In this paper, we focus on the two-machine case to demonstrate some major properties, and hope that these properties can provide insights for solving other general problems, such as multiple (more than two) machine scheduling and machine scheduling in other configurations (job shop or flow shop) under disruption. We study problems with different related costs. In each problem, we either provide a polynomial algorithm to solve the problem optimally, or show its NP-hardness. If the problem is NP-hard in the ordinary sense, we also present a pseudo-polynomial algorithm to solve the problem optimally. This research is supported in part by Hong Kong RGC grant HKUST 6145/03E and in part by NSF Grant DMI-0300156.     

A bounded approximation for the minimum cost 2-sat problem

Given a satisfiable Boolean formula in 2-CNF, it is NP-hard to find a satisfying assignment that contains a minimum number of true variables. A polynomial-time approximation algorithm is given that finds an assignment with at most twice as many true variables as necessary. The algorithm also works for a weighted generalization of the problem. An application to the optimal stable roommates problem is given in detail, and other applications are mentioned.D. Gusfield was supported in part by NSF Grant CCR-8803704. Part of this work was done while he was at Yale University, partially supported by NSF Grant MCS-8105894. L. Pitt was supported in part by NSF Grant IRI-8809570. Part of this work was done while he was at Yale University, supported by NSF Grants MCS-8002447, MCS-8116678, and MCS-8204246.     

Scheduling with due date assignment under special conditions on job processing

We review the results on scheduling with due date assignment under such conditions on job processing as given precedence constraints, maintenance activity or various scenarios of processing time changing. The due date assignment and scheduling problems arise in production planning when the management is faced with setting realistic due dates for a number of jobs. Most research on scheduling with due date assignment is focused on optimal sequencing of independent jobs. However, it is often found in practice that some products are manufactured in a certain order implied, for example, by technological, marketing or assembly requirements and this can be modeled by imposing precedence constraints on the set of jobs. In classical deterministic scheduling models, the processing conditions, including job processing times, are usually viewed as given constants. In many real-life situations, however, the processing conditions may vary over time, thereby affecting actual durations of jobs. In the models with controllable processing times, the scheduler can speed up job execution times by allocating some additional resources to the jobs. In the models with deterioration or learning, the actual processing time can depend either on the position or on the start time of a job in the schedule. In scheduling with deterioration, the later a job starts, the longer it takes to process, while in scheduling with learning, the actual processing time of a job gets shorter, provided that the job is scheduled later. We consider also scheduling models with optional maintenance activity. In manufacturing processing, production scheduling with preventive maintenance planning is one of the most significant methods in preventing the machinery from failure or wear.     

分布式环境中的多作业执行调度策略与优化

分布式大数据计算引擎是科研机构、互联网企业和政府部门处理大规模数据必不可少的工具,它们的使用和推广促进了各个领域的快速发展,为社会进步做出了巨大贡献.但是,在多作业处理的情况下,目前主流的大数据计算引擎在资源分配和作业调度方面仍有许多不足之处,它们通常对多作业平均划分内存资源并以先进先出FIFO的方式调度作业,这样简单...     

Thrifty execution of task pipelines

Summary A sequence of tasks that must be performed on a sequential database can be scheduled in various ways. Schedules will differ with respect to the number of accesses made to peripheral storage devices and the amount of memory space consumed by buffers. Buffer requirements are discussed for task schedules that avoid accesses to peripherals storing the sequential database. The relationship between certain thrifty scheduling policies and loop jamming, a standard code optimization technique, is also identified. Application to UNIX pipelines and to file processing is discussed.This work is supported in part by NSF Grant MCS-8003340 and MCS-8103605. Schneider is also supported by a Faculty Development Grant from IBM Corporation     

Planning and scheduling teams of skilled workers

Solving problems that mix planning and scheduling are often seen as a challenge. Discrete time-based scheduling, along with complex side constraints, does not mix well with the more flexible nature of the planning model. This is demonstrated in our experiments when trying to solve a problem where we must assemble teams of skilled workers to perform jobs that require these skills, break up these teams and then assemble new ones to perform more jobs. The mixing of the planning part (grouping workers into teams) and the scheduling part (creating a schedule for each worker), along with some difficult side constraints and a large problem size (800 workers, 2,000 jobs over one month) combine to contribute to the challenge of finding good solutions for this problem.     

基于SGE的仿真网格及其作业调度研究

网格引擎是一个构建本地和集群网格的工具,其框架是由四种类型的主机及其对应的守护进程构成.该文主要研究了通过SGE框架构建分布式仿真网格平台的方法,描述了仿真网格平台上执行用户提交的仿真任务的工作流程.随后讨论了基于SGE仿真网格中的资源组织和作业调度,并分析了仿真网格中所使用的作业调度算法,包括确定作业顺序的FIFO算法、优先级算法、等额度和日历算法等;确定队列顺序的负载调整、队列号等算法等.     

Approximation algorithms for scheduling real-time jobs with multiple feasible intervals

Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. Earlier works developed an optimal off-line algorithm to schedule all the jobs in a given job set and on-line heuristics to schedule the jobs in a best effort manner. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is -hard for both non-preemptible and preemptible jobs. This paper develops two approximation algorithms for non-preemptible and preemptible jobs. When jobs are non-preemptible, Algorithm Least Earliest Completion Time First (LECF) is shown to have a 2-approximation factor; when jobs are preemptible, Algorithm Least Execution Time First (LEF) is proved being a 3-approximation algorithm. We show that our analysis for the two algorithms are tight. We also evaluate our algorithms by extensive simulations. Simulation results show that Algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms in average.     

A Stronger Complexity Result for the Single Machine Multi-Operation Jobs Scheduling Problem to Minimize the Number of Tardy Jobs

We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.     

A hybrid scheduling decision support model for minimizing job tardiness in a make-to-order based mould manufacturing environment

In the make-to-order (MTO) mode of manufacturing, the specification of each product is unique such that production processes vary from one product to another making the production schedule complex. In order to achieve high level productivity, the production flow is not arranged in sequence; instead, the job schedule of different production jobs is adjusted to fit in with the multiple-job shop environment. A poor scheduling of jobs leads to high production cost, long production time and tardiness in job performance. The existing of tardiness in the production schedule significantly affects the harmony among the multiple jobs on the shops floor. In order to provide a complete solution for solving MTO scheduling problems with job shifting and minimizing job tardiness, a hybrid scheduling decision support model (SDSM) is introduced. The model is combined by a Genetic Algorithm (GA) and an optimisation module. GA is adopted to solve the complex scheduling problem taking into consideration of the wide variety of processes while the optimisation module is suggested for tackling tardiness in doing the jobs in a cost effective way. The simulation results reveal that the model shortens the generation time of production schedules and reduces the production cost in MTO-based production projects.     

A paradigm for robust geometric algorithms

This paper explores a paradigm for producing geometrical algorithms in which logical decisions that depend on finite-precision numerical calculation cannot lead to failure. It applies this paradigm to the task of intersecting two convex polyhedral objects. A key tool in this work is a method of perturbing embedding polyhedra in ways consistent with their topology.Work on this paper was supported in part by NSF Grant DMC-86-17355, NSF Grant DMS-87-02070, ONR Grant N00014-86-0281, ONR Grant N00014-88-0591, and the U.S. Army Research Office through MSI, Cornell University.     

Single-machine scheduling with trade-off between number of tardy jobs and compression cost

We consider a single-machine scheduling problem, in which the job processing times are controllable or compressible. The performance criteria are the compression cost and the number of tardy jobs. For the problem, where no tardy jobs are allowed and the objective is to minimize the total compression cost, we present a strongly polynomial time algorithm. For the problem to construct the trade-off curve between the number of tardy jobs and the maximum compression cost, we present a polynomial time algorithm. Furthermore, we extend the problem to the case of discrete controllable processing times, where the processing time of a job can only take one of several given discrete values. We show that even some special cases of the discrete controllable version with the objective of minimizing the total compression cost are NP-hard, but the general case is solvable in pseudo-polynomial time. Moreover, we present a strongly polynomial time algorithm to construct the trade-off curve between the number of tardy jobs and the maximum compression cost for the discrete controllable version. This research was supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of the MOE, China, and the National Natural Science Foundation of China (10271110). The third author was supported in part by The Hong Kong Polytechnic University under a grant from the ASD in China Business Services.     

A decentralized model for flow shop production with flexible transportation system

The recent advances in technology sectors often clash with traditional organizational paradigms which can limit or make difficult an efficient implementation in the real world. In this paper we show how it is possible to exploit the advantages of innovative technologies in manufacturing when these are supported by new and efficient methods for production management. More in details, we face a flow shop scheduling problem in a shoe manufacturing system in which overtaking of jobs is allowed thanks to an innovative transportation system. Overtaking means that a job can be put in waiting state and another job can surpass it, allowing the change of the scheduling sequence. Preemption is not allowed. The objective function of the problem is the minimization of the maximum lateness. We propose a decentralized model, based on multi-agent system theory, to represent the production cells of the plant and to include the potentiality offered by overtaking of jobs at decisional level. The adoption of a decentralized approach increases the system flexibility since each machine is able to solve its local scheduling problem. Adding or removing machines to the plant will not imply a change in the scheduling algorithms. The outcomes of this work are reached firstly through a formulation of the problem with three flow shop scheduling models, secondly through a comparison of the models with respect to different performance indicators. The results highlight as the decentralized approach is able to reach comparable performances with the centralized one for a relevant number of instances. Moreover sensitivity analysis shows as in the decentralized model the computational time required to solve bigger instances increases less quickly than in the case of centralized ones. Finally, simulations of the decentralized approach clarify as the correlation of the local solution procedure is effected by the number of machines of the flow shop and the coordination mechanism is effected by the number of the jobs to be scheduled.     

Minimizing Makespan and Preemption Costs on a System of Uniform Machines

It is well known that for preemptive scheduling on uniform machines there exist polynomial time exact algorithms, whereas for non-preemptive scheduling there are probably no such algorithms. However, it is not clear how many preemptions (in total, or per job) suffice in order to guarantee an optimal polynomial time algorithm. In this paper we investigate exactly this hardness gap, formalized as two variants of the classic preemptive scheduling problem. In generalized multiprocessor scheduling (GMS) we have a job-wise or total bound on the number of preemptions throughout a feasible schedule. We need to find a schedule that satisfies the preemption constraints, such that the maximum job completion time is minimized. In minimum preemptions scheduling (MPS) the only feasible schedules are preemptive schedules with the smallest possible makespan. The goal is to find a feasible schedule that minimizes the overall number of preemptions. Both problems are NP-hard, even for two machines and zero preemptions. For GMS, we develop polynomial time approximation schemes, distinguishing between the cases where the number of machines is fixed, or given as part of the input. Our scheme for a fixed number of machines has linear running time, and can be applied also for instances where jobs have release dates, and for instances with arbitrary preemption costs. For MPS, we derive matching lower and upper bounds on the number of preemptions required by any optimal schedule. Our results for MPS hold for any instance in which a job, J_j, can be processed simultaneously by ρ_j machines, for some ρ_j ≥ 1.     

Scheduling jobs under decreasing linear deterioration

This paper considers the scheduling problems under decreasing linear deterioration. Deterioration of a job means that its processing time is a function of its execution start time. Optimal algorithms are presented respectively for single machine scheduling of minimizing the makespan, maximum lateness, maximum cost and number of late jobs. For two-machine flow shop scheduling problem to minimize the makespan, it is proved that the optimal schedule can be obtained by Johnson's rule. If the processing times of operations are equal for each job, flow shop scheduling problems can be transformed into single machine scheduling problems.     

Energy optimal schedules for jobs with multiple active intervals

In this paper, we study the scheduling problem of jobs with multiple active intervals. Each job in the problem instance has disjoint active time intervals where it can be executed and a workload characterized by the required number of CPU cycles. Previously, people studied multiple interval job scheduling problem where each job must be assigned enough CPU cycles in one of its active intervals. We study a different practical version where the partial work done by the end of an interval remains valid and each job is considered finished if total CPU cycles assigned to it in all its active intervals reach the requirement. The goal is to find a feasible schedule that minimizes energy consumption. By adapting the algorithm for single interval jobs proposed in Yao, Demers and Shenker (1995) [1], one can still obtain an optimal schedule. However, the two phases in that algorithm (critical interval finding and scheduling the critical interval) can no longer be carried out directly. We present polynomial time algorithms to solve the two phases for jobs with multiple active intervals and therefore can still compute the optimal schedule in polynomial time.     

An aggregation procedure for the deterministic job-shop problem

A new approach is proposed in this paper to solve the job-shop scheduling problem. Instead of considering operations or machines, the construction of partial schedules by dealing with jobs, one after the other, is suggested. A partial schedule for given jobs is characterized by the sequence of their operations on each machine. The principle of the algorithm is to aggregate a new job on the current schedule, i.e. to insert its operations without altering the previous order. Two main theoretical results are presented: firstly, the selection procedure for jobs and secondly, the aggregation algorithm. Next the method is explained using a simple example. Finally, the authors present and comment on computational results for an implementation of the algorithm, for some well-known job-shop problems.     

A fluid approach to large volume job shop scheduling

We consider large volume job shop scheduling problems, in which there is a fixed number of machines, a bounded number of activities per job, and a large number of jobs. In large volume job shops it makes sense to solve a fluid problem and to schedule the jobs in such a way as to track the fluid solution. There have been several papers which used this idea to propose approximate solutions which are asymptotically optimal as the volume increases. We survey some of these results here. In most of these papers it is assumed that the problem consists of many identical copies of a fixed set of jobs. Our contribution in this paper is to extend the results to the far more general situation in which the many jobs are all different. We propose a very simple heuristic which can schedule such problems. We discuss asymptotic optimality of this heuristic, under a wide range of previously unexplored situations. We provide a software package to explore the performance of our policy, and present extensive computational evidence for its effectiveness.     

Can PAC learning algorithms tolerate random attribute noise?

This paper studies the robustness of PAC learning algorithms when the instance space is {0,1}ⁿ, and the examples are corrupted by purely random noise affecting only the attributes (and not the labels). Foruniform attribute noise, in which each attribute is flipped independently at random with the same probability, we present an algorithm that PAC learns monomials for any (unknown) noise rate less than ₂ ¹ . Contrasting this positive result, we show thatproduct random attribute noise, where each attributei is flipped randomly and independently with its own probability p_i, is nearly as harmful as malicious noise-no algorithm can tolerate more than a very small amount of such noise.The research of S. A. Goldman was supported in part by a GE Foundation Junior Faculty grant and NSF Grant CCR-9110108. Part of this research was conducted while the author was at the M.I.T. Laboratory for Computer Science and supported by NSF Grant DCR-8607494 and a grant from the Siemens Corporation. The research of R. H. Sloan was supported in part by NSF Grant CCR-9108753. Part of this research was conducted while the author was at Harvard and supported by ARO Grant DAAL 03-86-K-0171.     

Completion time variance minimisation on two identical parallel processors

The problem of scheduling jobs to minimise completion time variance (CTV) is a well-known problem in scheduling research. CTV is categorized as a non-regular performance measure and its value may decrease by increasing the job completion times. This objective is relevant in situations where providing uniform service to customers is important, and is in-line with just-in-time philosophy. The problem concerned in this paper is to schedule n jobs on two identical parallel machines to minimise CTV. We consider the unrestricted version of the problem. The problem is said to be restricted when a machine is not allowed to remain idle when jobs are available for processing. It may be necessary to delay the start of job processing on a machine in order to reduce the completion time deviations. This gives rise to the unrestricted version of the problem. We discuss several properties of an optimal schedule to the problem. In this paper, we develop a lower bound on CTV for a known partial schedule and propose a branch and bound algorithm to solve the problem. Optimal solutions are obtained and results are reported.