Online scheduling with rejection and withdrawal

We study an online scheduling problem with rejection, in which some rearrangement of the solution is allowed. This problem is called scheduling with rejection and withdrawal. Each arriving job has a processing time and a rejection cost associated with it, and it needs to be either assigned to a machine or rejected upon arrival. At termination, it is possible to choose at most a fixed number of scheduled jobs and withdraw them (i.e., decide to reject them). We study the minimization version, where the goal is to minimize the sum of the makespan and the total rejection cost (which corresponds to the penalty), and the maximization problem, where the goal is to maximize the sum of the minimum load and the total rejection cost (which corresponds to profit). We study environments of machines, which are the case of m identical machines and the case of two uniformly related machines, and show a strong relation between these problems and the related classic online scheduling problems which they generalize, in contrast to standard scheduling with rejection, which typically makes the scheduling problems harder.     

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.     

Reactive scheduling in a job shop where jobs arrive over time

The paper considers the dynamic job shop scheduling problem (DJSSP) with job release dates which arises widely in practical production systems. The principle characteristic of DJSSP considered in the paper is that the jobs arrive continuously in time and the attributes of the jobs, such as the release dates, routings and processing times are not known in advance, whereas in the classical job shop scheduling problem (CJSSP), it is assumed that all jobs to be processed are available at the beginning of the scheduling process. Reactive scheduling approach is one of the effective approaches for DJSSP. In the paper, a heuristic is proposed to implement the reactive scheduling of the jobs in the dynamic production environment. The proposed heuristic decomposes the original scheduling problem into a number of sub problems. Each sub problem, in fact, is a dynamic single machine scheduling problem with job release dates. The scheduling technique applied in theproposed heuristic is priority scheduling, which determines the next state of the system based on priority values of certain system elements. The system elements are prioritized with the help of scheduling rules (SRs). An approach based on gene expression programming (GEP) is also proposed in the paper to construct efficient SRs for DJSSP. The rules constructed by GEP are evaluated in the comparison of the rules constructed by GP and several prominent human made rules selected from literatures on extensive problem sets with respect to various measures of performance.     

Selection of cutting conditions for power constrained parallel machine scheduling

Most previous studies on machining optimization focused on aspects related to machining efficiency and economics, without accounting for environmental considerations. Higher cutting speed is usually desirable to maximize machining productivity, but this requires a high power load peak. In Taiwan, electricity prices rise sharply if instantaneous power demand exceeds contract capacity. Many studies over the previous decades have examined production scheduling problems. However, most such studies focused on well-defined jobs with known processing times. In addition, traditional sequencing and scheduling models focus primarily on economic objectives and largely disregard environmental issues raised by production scheduling problems. This study investigates a parallel machine scheduling problem for a manufacturing system with a bounded power demand peak. The challenge is to simultaneously determine proper cutting conditions for various jobs and assign them to machines for processing under the condition that power consumption never exceed the electricity load limit. A two-stage heuristic approach is proposed to solve the parallel machine scheduling problem with the goal of minimizing makespan. The heuristic performance is tested by distributing 20 jobs over 3 machines with four possible cutting parameter settings.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.     

Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which case the algorithm pays its rejection penalty, or it can be scheduled preemptively on the machines, in which case it may increase the maximum completion time of any machine in the schedule, also known as the makespan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule of all accepted jobs and the total penalty of all rejected jobs. We study two versions of the problem. The first one is the online problem where the jobs arrive unsorted, and the second variant is the semi-online case, where the jobs arrive sorted by a non-increasing order of penalties. We also show that the variant where the jobs arrive sorted by a non-decreasing order of penalties is equivalent to the unsorted one. We design optimal online algorithms for both cases. These algorithms have smaller competitive ratios than the optimal competitive ratio for the more general problem with arbitrary processing times (except for the case of identical machines), but larger competitive ratios than the optimal competitive ratio for preemptive scheduling of unit jobs without rejection.     

Scheduling a batch processing machine with incompatible job families

The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with incompatible job families. Jobs in a given family have identical job processing times, arbitrary job weights, and arbitrary job sizes. Batches are limited to jobs from the same family. The scheduling objective is to minimize total weighted completion time. We find that the procedure returns optimal solutions to problems of up to about 25 jobs in reasonable CPU time, and can be adapted for use as a heuristic for larger problems.     

The total completion time open shop scheduling problem with a given sequence of jobs on one machine

This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense, however it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.Scope and purposeShop scheduling problems, widely used in the modeling of industrial production processes, are receiving an increasing amount of attention from researchers. To model practical production processes more closely, additional processing restrictions can be introduced, e.g., the resource constraints, the no-wait in process requirement, the precedence constraints, etc. This paper considers the total completion time open shop scheduling problem with a given sequence of jobs on one machine. This model belongs to a new class of shop scheduling problems under machine-dependent precedence constraints. This problem is NP-hard in the strong sense. A heuristic is proposed to efficiently solve large-scaled problems and a branch-and-bound algorithm is presented to optimally solve small-scaled problems. Computational experience is also reported.     

分布式车间调度优化算法研究综述

在分布式制造环境下, 分布式车间调度着重研究工件在工厂间的合理分配以及各工厂内的合理加工顺序, 以实现调度指标的最优化. 分布式车间调度的研究具有重要的学术意义和应用价值, 已成为生产调度领域的热点. 对 此, 围绕分布式并行机调度、分布式流水线调度、分布式作业车间调度、分布式装配调度和分布式柔性车间调度等问题, 重点综述分布式调度优化算法方面的代表性成果, 介绍分布式调度的若干应用, 最后指出有待于进一步研究的若干方向和内容.

     

On the equivalence of single machine earliness/tardiness problems with job rejection

We present optimal algorithms for single-machine scheduling problems with earliness criteria and job rejection and compare them with the algorithms for the corresponding problems with tardiness objectives. We present an optimal O(n log n) algorithm for minimizing the maximum earliness on a single machine with job rejection. Our algorithm also solves the bi-criteria scheduling problem is which the objective is to simultaneously minimize the maximum earliness of the scheduled jobs and the total rejection cost of the rejected jobs. We also show that the optimal pseudo-polynomial time algorithm for the total tardiness problem with job rejection can be used to solve the corresponding total earliness problem with job rejection.     

Experience-Based Approach to Scheduling Problems With the Learning Effect

The existence of the learning effect in many manufacturing systems is undoubted; thus, it is worthwhile that it be taken into consideration during production planning to increase production efficiency. Generally, it can be done by formulating the specified problem in the scheduling context and optimizing an order of jobs to minimize the given time criteria. To carry out a reliable study of the learning effect in scheduling fields, a comprehensive survey of the related results is presented first. It reveals that most of the learning models in scheduling are based on the learning curve introduced by Wright. However, further study about learning itself pointed out that the curve may be an “S”-shaped function, which has not been considered in the scheduling domain. To fill this gap, we analyze a scheduling problem with a new experience-based learning model, where job processing times are described by “S”-shaped functions that are dependent on the experience of the processor. Moreover, problems with other experience-based learning models are also taken into consideration. We prove that the makespan minimization problem on a single processor is NP-hard or strongly NP-hard with the most of the considered learning models. A number of polynomially solvable cases are also provided.      

Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations

Scheduling with learning effects has attracted growing attention of the scheduling research community. A recent survey classifies the learning models in scheduling into two types, namely position-based learning and sum-of-processing-times-based learning. However, the actual processing time of a given job drops to zero precipitously as the number of jobs increases in the first model and when the normal job processing times are large in the second model. Motivated by this observation, we propose a new learning model where the actual job processing time is a function of the sum of the logarithm of the processing times of the jobs already processed. The use of the logarithm function is to model the phenomenon that learning as a human activity is subject to the law of diminishing return. Under the proposed learning model, we show that the scheduling problems to minimize the makespan and total completion time can be solved in polynomial time. We further show that the problems to minimize the maximum lateness, maximum tardiness, weighted sum of completion times and total tardiness have polynomial-time solutions under some agreeable conditions on the problem parameters.     

非同起点加工的多机调度合成算法

针对调度h个独立任务到初始时刻并非都空闲的m台机器上加工，使得机器最长加工时间（makespan）最短的问题，改进MLPT算法以减少运行时间，改进MULTIFIT算法以减少迭代次数，提出以改进的MLPT算法结果为改进的MULTIFIT算法的初始上界的合成算法－CMM，从理论上对MLPT，MULTIFIT和CMM算法的时间复杂度和调度结果进行了分析和比较，实验结果表明：改进的MULTIFIT经MULTIFIT的平均迭代次数少；CMM在平均迭代次数方面甚至比改进的MULTIFIT还少得多且调度结果不次于MULTIFIT和MLPT的优者。     

Scheduling on parallel identical machines with job-rejection and position-dependent processing times

We solve scheduling problems which combine the option of job-rejection and general position-dependent processing times. The option of rejection reflects a very common scenario, where the scheduler may decide not to process a job if it is not profitable. The assumption of position-dependent processing time is a common generalization of classical settings, and contains the well-known and extensively studied special cases of “learning” and “aging”. The machine setting is parallel identical machines, and two scheduling measures are considered: total flow-time and total load. When the number of jobs is given, both problems are shown to be solved in polynomial time in the number of jobs. The special case of non-decreasing job-position processing times (“aging”) is shown to be solved much faster.     

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.     

A computer simulation model for job shop scheduling problems minimizing makespan

One of the basic and significant problems, that a shop or a factory manager is encountered, is a suitable scheduling and sequencing of jobs on machines. One type of scheduling problem is job shop scheduling. There are different machines in a shop of which a job may require some or all these machines in some specific sequence. For solving this problem, the objective may be to minimize the makespan. After optimizing the makespan, the jobs sequencing must be carried out for each machine. The above problem can be solved by a number of different methods such as branch and bound, cutting plane, heuristic methods, etc. In recent years, researches have used genetic algorithms, simulated annealing, and machine learning methods for solving such problems. In this paper, a simulation model is presented to work out job shop scheduling problems with the objective of minimizing makespan. The model has been coded by Visual SLAM which is a special simulation language. The structure of this language is based on the network modeling. After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented and compared with other results reported in the literature. Finally, the model output is analyzed.     

Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure

A batch processing machine can simultaneously process several jobs forming a batch. This paper considers the problem of scheduling jobs with non-identical capacity requirements, on a single-batch processing machine of a given capacity, to minimize the makespan. The processing time of a batch is equal to the largest processing time of any job in the batch. We present some dominance properties for a general enumeration scheme and for the makespan criterion, and provide a branch and bound method. For large-scale problems, we use this enumeration scheme as a heuristic method.Scope and purposeUsually in classical scheduling problems, a machine can perform only one job at a time. Although, one can find machines that can process several jobs simultaneously as a batch. All jobs of a same batch have common starting and ending times. Batch processing machines are encountered in many different environments, such as burn-in operations in semiconductor industries or heat treatment operations in metalworking industries. In the first case, the capacity of the machine is defined by the number of jobs it can hold. In the second case, each job has a certain capacity requirement and the total size of a batch cannot exceed the capacity of the machine. Hence, the number of jobs contained in each batch may be different. In this paper, we consider this second case (which is more difficult) and we provide an exact method for the makespan criterion (minimizing the last ending time).     

Predictive performance modeling for distributed batch processing using black box monitoring and machine learning

In many domains, the previous decade was characterized by increasing data volumes and growing complexity of data analyses, creating new demands for batch processing on distributed systems. Effective operation of these systems is challenging when facing uncertainties about the performance of jobs and tasks under varying resource configurations, e. g., for scheduling and resource allocation. We survey predictive performance modeling (PPM) approaches to estimate performance metrics such as execution duration, required memory or wait times of future jobs and tasks based on past performance observations. We focus on non-intrusive methods, i. e., methods that can be applied to any workload without modification, since the workload is usually a black box from the perspective of the systems managing the computational infrastructure. We classify and compare sources of performance variation, predicted performance metrics, limitations and challenges, required training data, use cases, and the underlying prediction techniques. We conclude by identifying several open problems and pressing research needs in the field.     

Two–machine flowshop minimum–length scheduling problem with random and bounded processing times

We address the two–machine flowshop scheduling problem to minimize makespan where jobs have random and bounded processing times. The probability distributions of job processing times are unknown and only the lower and upper bounds of processing times are given before scheduling. In such cases there may not exist a unique schedule that remains optimal for all possible realizations of processing times, and therefore, a set of schedules has to be considered which dominates all other schedules. In this paper, we find some sufficient conditions for the considered problem.     

Implementation of a case-based production scheduling system in C language

This paper presents the application of Case-Based Reasoning to the production scheduling problem in a corrugated card-board factory, its main task is to find a promising sequence for jobs processing, a prototype of the scheduling system is implemented in C language. In this system, a schedule case is represented in the form of ordered tree and each job is represented in the format of attribute-value pairs. When jobs to be sequenced are given, a previous case which is the best matching with the problem is recalled from the case-base, the sequence of given jobs can be decided assigning the jobs to the nodes of the ordered tree of the recalled case. Several real world scheduling problems in the factory have been solved and the system behaved as correctly as the human experts did. It was showed that the Case-Based Reasoning approach is well suited to solve production scheduling problems.