Single-machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect

We study single machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect. In the general truncated learning model, the actual processing time of a job is affected by the sum of actual processing times of previous jobs and by a job-dependent truncation parameter. We show that the single machine problems to minimize makespan and to minimize the sum of weighted completion times are both at least ordinary NP-hard and the single machine problem to minimize maximum lateness is strongly NP-hard. We then show polynomial solvable cases and approximation algorithms for these problems. Computational experiments are also conducted to show the effectiveness of our approximation algorithms.

     

Minmax common flow-allowance problems with convex resource allocation and position-dependent workloads

We study minmax due-date based on common flow-allowance assignment and scheduling problems on a single machine, and extend known results in scheduling theory by considering convex resource allocation. The total cost function of a given job consists of its earliness, tardiness and flow-allowance cost components. Thus, the common flow-allowance and the actual jobs’ processing times are decision variables, implying that the due-dates and actual processing times can be controlled by allocating additional resource to the job operations. Consequently, our goal is to optimize a cost function by seeking the optimal job sequence, the optimal job-dependent due-dates along with the actual processing times. In all addressed problems we aim to minimize the maximal cost among all the jobs subject to a constraint on the resource consumption. We start by analyzing and solving the problem with position-independent workloads and then proceed to position-dependent workloads. Finally, the results are generalized to the method of common due-window. For all studied problems closed form solutions are provided, leading to polynomial time solutions.

     

On single machine scheduling with resource constraint

The single machine scheduling with resource constraint is a nonlinear combinatorial optimization problem in cloud computing applications. Given a set of jobs and certain resource, the problem is to find a permutation of jobs and a distribution of resource to optimize certain objective function. The processing time of each job is a nonlinear function with respect to the resource assigned to it. In this paper, we propose a naive algorithm and study a subproblem in the algorithm that suppose the permutation of jobs is also given, how to find a resource distribution to minimize the total weighted flow time. We found a polynomial-time optimal solution for a special case and an approximation solution in general case.     

Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects

In this paper, we propose a new learning effect model in which the actual job processing time is a general function of the normal processing time of jobs already processed and its scheduled position. This model has the advantage that different learning curves can be constructed easily, such as the plateau function. It is found that most of the models in the literature are special cases of our proposed model. The optimal sequences for some single-machine problems are then provided.     

A FRAMEWORK FOR MACHINE SCHEDULING PROBLEMS WITH CONTROLLABLE PROCESSING TIMES

This is a study of single and parallel machine scheduling problems with controllable processing time for each job. The processing time for job j depends on the position of the job in the schedule and is a function of the number of resource units allocated to its processing. Processing time functions and processing cost functions are allowed to be nonlinear. The scheduling problems considered here have important applications in industry and include many of the existing scheduling models as special cases. For the single machine problem, the objective is minimization of total compression costs plus a scheduling measure. The scheduling measures include makespan, total flow time, total differences in completion times, total differences in waiting times, and total earliness and tardiness with a common due date for all jobs. Except when the total earliness and tardiness measure is involved, each case the problem is solved efficiently. Under an assumption typically satisfied in just-in-time systems, the problem with total earliness and tardiness measure is also solved efficiently. Finally, for a large class of processing time functions; parallel machine problems with total flow time and total earliness and tardiness measures are solved efficiently. In each case we reduce the problem to a transportation problem.     

Single-machine scheduling problems with the effects of learning and deterioration

In this paper, we consider the single-machine scheduling problems with the effects of learning and deterioration. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single-machine makespan and sum of completion times (square) minimization problems remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively.     

MINIMIZING ABSOLUTE AND SQUARED DEVIATION OF COMPLETION TIMES FROM DUE DATES

This is a study of a single-machine scheduling problem with the objective of minimizing the sum of a function of earliness and tardiness called the earliness and tardiness (ET) problem. I will show that if priority weights of jobs are proportional to their processing times, and if earliness and tardiness cost functions are linear, the problem will be equivalent to the total weighted tardiness problem. This proves that the et problem is np -hard. In addition, I present a heuristic algorithm with worst case bound for the et problem based on the equivalence relation between the two. When earliness and tardiness cost functions are quadratic, I consider the problem for a common due date for all jobs and for different job due dates. In general, the et problem with quadratic earliness and tardiness cost functions and all job weights equal to one is np -hard. I show that in many cases, when weights of jobs are proportional to their processing times, the problem can be solved efficiently. In the published results on the et problem with quadratic earliness and tardiness cost functions other researchers have assumed a zero starting time for the schedule. I discuss the advantages of a nonzero starting time for the schedule.     

Dynamic Assignment of Flexible Service Resources

Resource flexibility is an important tool for firms to better match capacity with demand so as to increase revenues and improve service levels. However, in service contexts that require dynamically deciding whether to accept incoming jobs and what resource to assign to each accepted job, harnessing the benefits of flexibility requires using effective methods for making these operational decisions. Motivated by the resource deployment decisions facing a professional service firm in the workplace training industry, we address the dynamic job acceptance and resource assignment problem for systems with general resource flexibility structure, i.e., with multiple resource types that can each perform different overlapping subsets of job types. We first show that, for systems containing specialized resources for individual job types and a versatile resource type that can perform all job types, the exact policy uses a threshold rule. With more general flexibility structures, since the associated stochastic dynamic program is intractable, we develop and test three optimization‐based approximate policies. Our extensive computational tests show that one of the methods, which we call the Bottleneck Capacity Reservation policy, is remarkably effective in generating near‐optimal solutions over a wide range of problem scenarios. We also consider a model variant that requires dynamic job acceptance decisions but permits deferring resource assignment decisions until the end of the horizon. For this model, we discuss an adaptation of our approximate policy, establish the effectiveness of this policy, and assess the value of postponing assignment decisions.     

A variable neighborhood search algorithm for human resource selection and optimization problem in the home appliance manufacturing industry

The increase in human resource cost puts forward higher requirements for the optimization of home appliance manufacturing processes. This paper studied an integrated human resource optimization problem considering the human resource selection, learning effect, skills degradation effect, and parallel production lines. There are multiple different manufacturing tasks with different normal processing times. Human resources have different abilities and costs. The actual processing time of a task is determined by its normal processing time, position, and ability of the human resource. The objective is to minimize production time and the labor cost. To solve the studied problem, we first consider the case where the human resources have been selected and assigned to the production lines. Then, some structural properties are proposed and a heuristic is developed to arrange tasks on every single production line. Also, we derive a lower bound for the problem. Since the investigated problem is NP-hard, a Variable Neighborhood Search is designed to solve the problem in a reasonable time. Finally, computational experiments are conducted and the experimental results validate the performance of the proposed methods.

     

The no-wait job shop with regular objective: a method based on optimal job insertion

The no-wait job shop problem (NWJS-R) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is prescribed. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The problem consists in finding a schedule that minimizes a general regular objective function. We study the so-called optimal job insertion problem in the NWJS-R and prove that this problem is solvable in polynomial time by a very efficient algorithm, generalizing a result we obtained in the case of a makespan objective. We then propose a large neighborhood local search method for the NWJS-R based on the optimal job insertion algorithm and present extensive numerical results that compare favorably with current benchmarks when available.     

Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling

We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker ( 2014 ) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.     

On the optimality of the TLS algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines

In this paper we study the optimality of the TLS algorithm for solving the online scheduling problem of minimizing the makespan on a set of m multipurpose machines, where there are two different job types and each job type can only be processed on a unique subset of machines. The literature shows that the TLS algorithm is optimal for the special cases where either m=2 or where all processing times are restricted to unity. We show that the TLS algorithm is optimal also for the special cases where the job processing times are either job type or machine set dependent. For both cases, the optimality of the TLS algorithm is proven by showing that its competitive ratio matches the lower bound for any processing set and processing time parameters.     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.     

Minimization of maximum lateness under linear deterioration

This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be -hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases.     

Single machine scheduling with general positional deterioration and rate-modifying maintenance

We present polynomial-time algorithms for single machine problems with generalized positional deterioration effects and machine maintenance. The decisions should be taken regarding possible sequences of jobs and on the number of maintenance activities to be included into a schedule in order to minimize the overall makespan. We deal with general non-decreasing functions to represent deterioration rates of job processing times. Another novel extension of existing models is our assumption that a maintenance activity does not necessarily fully restore the machine to its original perfect state. In the resulting schedules, the jobs are split into groups, a particular group to be sequenced after a particular maintenance period, and the actual processing time of a job is affected by the group that job is placed into and its position within the group.     

Single machine scheduling problems with subcontracting options

In this paper, we study a scheduling model as follows: there are n jobs which can be processed in house on a single machine or subcontracted to a subcontractor. If a job is subcontracted, its processing cost is different from the in-house cost and its delivery lead time is a stepwise function of the total processing time of outsourced jobs. Two objective functions are studied (1) to minimize the weighted sum of the maximal completion time and the total processing cost and (2) to minimize the weighted sum of the number of tardy jobs and the total processing cost. For the first problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm. For the second problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm for a special case.     

Minimizing makespan in an ordered flow shop with?machine-dependent processing times

We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine. In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number of machines is fixed.     

Synchronous flow shop problems: How much can we gain by leaving machines idle?

In synchronous production lines it may be beneficial to leave machines idle instead of processing the next job immediately. In this paper, the effects of inserting voluntary idle times are discussed in more detail for different objective functions (minimization of makespan, total completion time, maximum lateness). Besides deriving theoretical bounds on how much can be gained by inserting idle times, an extensive computational study is conducted to empirically examine the actual improvements. For this, exact algorithms and heuristics capable of incorporating voluntary idle times are proposed to find (near-) optimal schedules. It can be seen that the potential gain is very large in theory, while the empirical results indicate that in general only small improvements are achievable in practice.     

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。