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.     

具有线性恶化加工时间的调度问题

讨论了工件具有线性恶化加工时间的调度问题.在这类问题中,工件的恶化函数为线性 函数.对单机调度问题中目标函数为极小化最大完工时间加权完工时间和,最大延误以及最大费 用等问题分别给出了最优算法.对两台机器极小化最大完工时间的Flowshop问题,证明了利用 Johnson规则可以得到最优调度.对于一般情况,如果同一工件的工序的加工时间均相等,则 Flowshop问题可以转化为单机问题.     

Real-Time Scheduling with a Budget

Suppose that we are given a set of jobs, where each job has a processing time, a non-negative weight, and a set of possible time intervals in which it can be processed. In addition, each job has a processing cost. Our goal is to schedule a feasible subset of the jobs on a single machine, such that the total weight is maximized, and the cost of the schedule is within a given budget. We refer to this problem as budgeted real-time scheduling (BRS). Indeed, the special case where the budget is unbounded is the well-known real-time scheduling problem. The second problem that we consider is budgeted real-time scheduling with overlaps (BRSO), in which several jobs may be processed simultaneously, and the goal is to maximize the time in which the machine is utilized. Our two variants of this real-time scheduling problem have important applications, in vehicle scheduling, linear combinatorial auctions, and Quality-of-Service management for Internet connections. These problems are the focus of this paper. Both BRS and BRSO are strongly NP-hard, even with unbounded budget. Our main results are (2 + ε)-approximation algorithms for these problems. This ratio coincides with the best known approximation factor for the (unbudgeted) real-time scheduling problem, and is slightly weaker than the best known approximation factor of e/(e - 1) for the (unbudgeted) real-time scheduling with overlaps, presented in this paper. We show that better ratios (or simpler approximation algorithms) can be derived for some special cases, including instances with unit-costs and the budgeted job interval selection problem (JISP). Budgeted JISP is shown to be APX-hard even when overlaps are allowed and with unbounded budget. Finally, our results can be extended to instances with multiple machines.     

A two-stage hybrid flowshop scheduling problem in machine breakdown condition

This paper considers a two-stage hybrid flowshop scheduling problem in machine breakdown condition. By machine breakdown condition we mean that the machine may not always be available during the scheduling period. Machine failure may occur with a known probability after completing a job. Probability of machine failure depends on the previous processed job. The problem to be studied has one machine at the first stage and M parallel identical machines at the second stage. The objective is to find the optimal job combinations and the optimal job schedule such that the makespan is minimized. The proposed problem is compatible with a large scope of real world situations. To solve the problem, first, we introduce one optimal approach for job precedence when there is one machine in both stages and then provide a heuristic algorithm when there are M machines in stage two. To examine the performance of the heuristic, some experiments used are provided as well.     

Improving schedule stability in single-machine rescheduling for new operation insertion

The problem studied here entails inserting a new operation into an existing predictive schedule (preschedule) on a (non-preemptive) single machine by rescheduling its operations, so that the resultant schedule is the most stable one among schedules with minimal maximum tardiness. Stability is measured by the sum of absolute deviations of post-rescheduling start times from the pre-rescheduling start times. In addition to several simple heuristics, this study investigates a hybrid branch-and-bound/local-search algorithm. A large set of instances that include cases with inserted idle times allows for tests of the performance of the heuristics for preschedules with varying degrees of robustness. The results show that algorithms can be developed that significantly improve the stability of schedules with no degradation in T_max. In addition, new insights emerge into the robustness characteristics of a preschedule. Specifically, the number of gaps in the schedule, equal distribution of total slack among these gaps, and the slack introduced beyond the amount enforced by release times all have effects on schedule robustness and stability.     

Hybrid Evolutionary Algorithm for job scheduling under machine maintenance

The job scheduling problem (JSP) belongs to the well-known combinatorial optimization domain. After scheduling, if a machine maintenance issue affects the scheduled processing of jobs, the delivery of jobs must be delayed. In this paper, we have first proposed a Hybrid Evolutionary Algorithm (HyEA) for solving JSPs. We have then analyzed the effect of machine maintenance, whether preventive or breakdown, on the job scheduling. For the breakdown maintenance case, it is required to revise the algorithm to incorporate a rescheduling option after the breakdown occurs. The algorithm has been tested by solving a number of benchmark problems and thence comparing them with the existing algorithms. The experimental results provide a better understanding of job scheduling and the necessary rescheduling operations under process interruption.     

Application of neural networks to heuristic scheduling algorithms

This paper considers the use of artificial neural networks (ANNs) to model six different heuristic algorithms applied to the n job, m machine real flowshop scheduling problem with the objective of minimizing makespan. The objective is to obtain six ANN models to be used for the prediction of the completion times for each job processed on each machine and to introduce the fuzziness of scheduling information into flowshop scheduling. Fuzzy membership functions are generated for completion, job waiting and machine idle times. Different methods are proposed to obtain the fuzzy parameters. To model the functional relation between the input and output variables, multilayered feedforward networks (MFNs) trained with error backpropagation learning rule are used. The trained network is able to apply the learnt relationship to new problems. In this paper, an implementation alternative to the existing heuristic algorithms is provided. Once the network is trained adequately, it can provide an outcome (solution) faster than conventional iterative methods by its generalizing property. The results obtained from the study can be extended to solve the scheduling problems in the area of manufacturing.     

具有多个维修区间的单机调度问题

针对工件具有位置退化效应,机器具有多个维修区间的单机调度问题。工件的加工时间为位置相关的函数。每次机器维修后回到初始的水平。目标函数为总的提前费用,误工费用,共同交货期的窗时费用和开始时间费用。对于共同交货期分为包括维修区间和不包括维修区间两种情形进行讨论,采用线性规划建立指派问题的数学模型,并分别提出最优序列的一些最优性质和相应的多项式时间算法。     

Parallel machine scheduling problems using memetic algorithms

In this paper, we investigate how to apply the hybrid genetic algorithms (the memetic algorithms) to solve the parallel machine scheduling problem. There are two essential issues to be dealt with for all kinds of parallel machine scheduling problems: job partition among machines and job sequence within each machine. The basic idea of the proposed method is that (a) use the genetic algorithms to evolve the job partition and then (b) apply a local optimizer to adjust the job permutation to push each chromosome climb to his local optima. Preliminary computational experiments demonstrate that the hybrid genetic algorithm outperforms the genetic algorithms and the conventional heuristics.     

Dynamic scheduling of manufacturing job shops using genetic algorithms

Most job shop scheduling methods reported in the literature usually address the static scheduling problem. These methods do not consider multiple criteria, nor do they accommodate alternate resources to process a job operation. In this paper, a scheduling method based on genetic algorithms is developed and it addresses all the shortcomings mentioned above. The genetic algorithms approach is a schedule permutation approach that systematically permutes an initial pool of randomly generated schedules to return the best schedule found to date.A dynamic scheduling problem was designed to closely reflect a real job shop scheduling environment. Two performance measures, namely mean job tardiness and mean job cost, were used to demonstrate multiple criteria scheduling. To span a varied job shop environment, three factors were identified and varied between two levels each. The results of this extensive simulation study indicate that the genetic algorithms scheduling approach produces better scheduling performance in comparison to several common dispatching rules.     

Minimizing job completion time variance for service stability on identical parallel machines

This paper addresses a job scheduling problem on multiple identical parallel machines so as to minimize job completion time variance (CTV). CTV minimization is closely related to the Just-In-Time philosophy and the service stability concept since it penalizes both earliness and tardiness. Its applications can be found in many real-life areas such as Internet data packet dispatching and production planning. This paper focuses on the unrestricted case of the problem where idle times are allowed to exist before machines start to process jobs. We prove several dominant properties about the optimal solution to the problem. For instance, we prove that the mean completion time (MCT) on each machine should be the same under an optimal schedule. Based on these properties, an efficient heuristic algorithm is proposed. Computational experiments are conducted to test the performance of the proposed algorithm. The outputs demonstrate that the proposed algorithm is near optimal for small problem instances and greatly outperforms some existing algorithms for large problem instances.     

Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration

Maintenance is important to manufacturing process as it helps improve the efficiency of production. Although different models of joint deterioration and learning effects have been studied extensively in various areas, it has rarely been studied in the context of scheduling with maintenance activities. This paper considers scheduling with jointly the deterioration and learning effects and multi-maintenance activities on a single-machine setting. We assume that the machine may have several maintenance activities to improve its production efficiency during the scheduling horizon, and the duration of each maintenance activity depends on the running time of the machine. The objectives are to determine the optimal maintenance frequencies, the optimal maintenance locations, and the optimal job schedule such that the makespan and the total completion time are minimized, respectively, when the upper bound of the maintenance frequencies on the machine is known in advance. We show that all the problems studied can be solved by polynomial time algorithms.     

Discrepancy search for the flexible job shop scheduling problem

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop problem in which each operation must be processed on a given machine chosen among a finite subset of candidate machines. The aim is to find an allocation for each operation and to define the sequence of operations on each machine, so that the resulting schedule has a minimal completion time. We propose a variant of the climbing discrepancy search approach for solving this problem. We also present various neighborhood structures related to assignment and sequencing problems. We report the results of extensive computational experiments carried out on well-known benchmarks for flexible job shop scheduling. The results demonstrate that the proposed approach outperforms the best-known algorithms for the FJSP on some types of benchmarks and remains comparable with them on other ones.     

Common due date assignment and scheduling with ready times

We consider the problem of scheduling a set of nonsimultaneously available jobs on one machine. Each job has a ready time only at or after which the job can be processed. All the jobs have a common due date, which needs to be determined. The problem is to determine a due date and a schedule so as to minimize a total penalty depending on the earliness, tardiness and due date. We show that this problem is strongly NP-hard and give an efficient algorithm that finds an optimal due date and schedule when either the job sequence is predetermined or all jobs have the same processing time. We also propose three approximation algorithms for the general and special cases together with their experimental analysis.

Scope and purpose

We consider the single machine due date assignment problem for scheduling jobs which are ready for processing at different times. The problem under consideration arises in production planning and scheduling concerning the setting of appropriate due dates for a number of customer orders arriving over time. Most of the earlier publications on this subject assumed that the jobs are ready for processing simultaneously. This assumption is too restrictive for real-life production systems where jobs arrive at different times. We show that the problem with unequal ready times is NP-hard and develop fast heuristic algorithms for it, and exact algorithms for two special cases.     

一种基于强化学习的作业车间动态调度方法

Production scheduling is critical to manufacturing system. Dispatching rules are usually applied dynamically to schedule the job in a dynamic job-shop. Existing scheduling approaches sel- dom address machine selection in the scheduling process. Composite rules, considering both machine selection and job selection, are proposed in this paper. The dynamic system is trained to enhance its learning and adaptive capability by a reinforcement learning (RL) algorithm. We define the conception of pressure to describe the system feature. Designing a reward function should be guided by the scheduling goal to accurately record the learning progress. Competitive results with the RL-based approach show that it can be used as real-time scheduling technology.     

A Reinforcement Learning-based Approach to Dynamic Job-shop Scheduling

Production scheduling is critical to manufacturing system.Dispatching rules are usually applied dynamically to schedule (?)he job in a dynamic job-shop.Existing scheduling approaches sel- dom address machine selection in the scheduling process.Composite rules,considering both machine selection and job selection,are proposed in this paper.The dynamic system is trained to enhance its learning and adaptive capability by a reinforcement learning(RL)algorithm.We define the concep- tion of pressure to describe the system feature.Designing a reward function should be guided by the scheduling goal to accurately record the learning progress.Competitive results with the RL-based approach show that it can be used as real-time scheduling technology.     

An anticipative scheduling approach with controllable processing times

In practice, machine schedules are usually subject to disruptions which have to be repaired by reactive scheduling decisions. The most popular predictive approach in project management and machine scheduling literature is to leave idle times (time buffers) in schedules in coping with disruptions, i.e. the resources will be under-utilized. Therefore, preparing initial schedules by considering possible disruption times along with rescheduling objectives is critical for the performance of rescheduling decisions. In this paper, we show that if the processing times are controllable then an anticipative approach can be used to form an initial schedule so that the limited capacity of the production resources are utilized more effectively. To illustrate the anticipative scheduling idea, we consider a non-identical parallel machining environment, where processing times can be controlled at a certain compression cost. When there is a disruption during the execution of the initial schedule, a match-up time strategy is utilized such that a repaired schedule has to catch-up initial schedule at some point in future. This requires changing machine–job assignments and processing times for the rest of the schedule which implies increased manufacturing costs. We show that making anticipative job sequencing decisions, based on failure and repair time distributions and flexibility of jobs, one can repair schedules by incurring less manufacturing cost. Our computational results show that the match-up time strategy is very sensitive to initial schedule and the proposed anticipative scheduling algorithm can be very helpful to reduce rescheduling costs.     

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.     

Developing feasible and optimal schedules of jobs on one machine

The paper considers the properties of feasible and optimal scheduling of jobs on one machine under constraints on the terms of the beginning and completion of jobs and on partial sequences of job performance. The established properties and the lower-bound estimates of the length of the optimal schedule are used to develop methods for the exact and approximate solutions of the formulated problem by sequential optimization algorithms. The proposed algorithms are illustrated by numerical examples and can be successfully applied to solve these problems in the absence of constraints.