Scheduling a capacitated single machine with time deteriorating job values

We address the scheduling problem with the following characteristics: (i) there is a single machine available, (ii) the machine has limited capacity, and (iii) job value deteriorates with time. The problem is motivated from several real world situations, such as, downloading process of web pages, and scheduling of multiplexes. Since the problem is NP-hard, we propose new heuristics based on a multiplicative piece-wise metric as an approximation of the slope of job value deterioration. Computational results show that the proposed heuristics perform better than other existing heuristics for similar types of problems.     

Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine

This paper considers the problem of scheduling deteriorating jobs and due date assignment on a single machine. The actual processing time of a job is a linear increasing function of its starting time. The problem is to determine the optimal due dates and the processing sequence simultaneously to minimize costs for earliness, due date assignment and weighted number of tardy jobs. We present polynomial-time algorithms to solve the problem in the case of two popular due date assignment methods: CON and SLK.     

Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm

This paper addresses the problem of finding robust and stable solutions for the flexible job shop scheduling problem with random machine breakdowns. A number of bi-objective measures combining the robustness and stability of the predicted schedule are defined and compared while using the same rescheduling method. Consequently, a two-stage Hybrid Genetic Algorithm (HGA) is proposed to generate the predictive schedule. The first stage optimizes the primary objective, minimizing makespan in this work, where all the data is considered to be deterministic with no expected disruptions. The second stage optimizes the bi-objective function and integrates machines assignments and operations sequencing with the expected machine breakdown in the decoding space. An experimental study and Analysis of Variance (ANOVA) is conducted to study the effect of different proposed measures on the performance of the obtained results. Results indicate that different measures have different significant effects on the relative performance of the proposed method. Furthermore, the effectiveness of the current proposed method is compared against three other methods; two are taken from literature and the third is a combination of the former two methods.     

A note on “minimizing a weighted quadratic function of job lateness in the single machine system”

A set of jobs is to be scheduled on a single machine where an idle time is allowed to be inserted before the processing of the first job begins. The objective is to find an optimal sequence that minimizes the weighted sum of a quadratic function of job lateness. Sen et al. [Sen, T., Dileepan, P., Lind, M.R., 1995. Minimizing a weighted quadratic function of job lateness in the single machine system. International Journal of Production Economics 42(3), 237–243] presented a branch-and-bound algorithm for the problem; however, as shown in this note, their algorithm does not work because the branching rule for adjacent jobs is not applicable to non-adjacent jobs.     

Scheduling with processing set restrictions: PTAS results for several variants

We consider multiprocessor scheduling to minimize makespan. Each job has a given processing time and in addition, a subset of machines associated with it, also called its processing set. Each job has to be assigned to one machine in its set, thus contributing to the load of this machine. We study two variants of this problem on identical machines, the case of nested processing sets, and the case of tree-hierarchical processing sets. In addition, we consider uniformly related machines with a special case of inclusive processing sets, which has a clear motivation. We design polynomial time approximation schemes for these three variants. The first case resolves one of the open problems stated in the survey by Leung and Li (2008).     

Integrating noncyclical preventive maintenance scheduling and production planning for a single machine

This paper deals with the problem of integrating noncyclical preventive maintenance and tactical production planning for a single machine. We are given a set of products that must be produced in lots during a specified finite planning horizon. The maintenance policy suggests possible preventive replacements at the beginning of each production planning period, and minimal repair at machine failure. The proposed model determines simultaneously the optimal production plan and the instants of preventive maintenance actions. The objective is to minimize the sum of preventive and corrective maintenance costs, setup costs, holding costs, backorder costs and production costs, while satisfying the demand for all products over the entire horizon. The problem is solved by comparing the results of several multi-product capacitated lot-sizing problems. The value of the integration and that of using noncyclical preventive maintenance when the demand varies from one period to another are illustrated through a numerical example and validated by a design of experiment. The later has shown that the integration of maintenance and production planning can reduce the total maintenance and production cost and the removal of periodicity constraint is directly affected by the demand fluctuation and can also reduce the total maintenance and production cost.     

Impact of telework on exhaustion and job engagement: a job demands and job resources model

Teleworking, the increasingly common practice, which involves working away from the office using technology, entails changes in the experience of work. Such changes may influence the demands and resources associated with a job. While research on burnout has addressed the role of exhaustion and job engagement using the Job Demands‐Resources model, existing literature has focused on traditional work modes. This paper explores the effects on job demands and resources to understand the processes through which telework impacts the exhaustion and engagement of the teleworker. We find that the positive effect of telework revolves around reduced work pressure and role conflict and increased autonomy. The negative effect of telework is expressed through increased role ambiguity and reduced support and feedback. Overall, we find that telework is negatively related to both exhaustion and job engagement and that job demands and resources mediate these relationships.     

面向环境的单面瓦楞纸成型机设计与制造分析

环境与发展是人类共同关注的热点.可持续发展是强调环境与经济的协调发展,追求人与自然的和谐.改变传统的生产方式是可持续发展的重要途径,只有采用先进的生产技术,才能降低单位产品的能耗、物耗,才能实现少投入、多产出的生产方式,才能减少经济发展对资源和能源的需求,减少污染,从而减轻对环境的压力.     

Scheduling a flow shop with combined buffer conditions

In this paper, four inter-machine buffer conditions (i.e. no-wait, no-buffer, limited-buffer and infinite-buffer) in a flow shop are investigated. These four different buffer conditions are combined to generate a more generalised and more comprehensive scheduling problem, which can cover the classical flow-shop scheduling (FSS) with unlimited buffer, the blocking FSS (BFSS) without buffer, the no-wait FSS (NWFSS) and the limited-buffer FSS (LBFSS) problems. By analysing the structural properties of these four buffer conditions, an innovative constructive algorithm called the Liu–Kozan algorithm is proposed to build the feasible combined-buffer flow-shop scheduling (CBFSS) solution. The proposed Liu–Kozan algorithm mainly comprises a time-determination procedure and a tune-up procedure with eight sets of formulae. Detailed numerical implementations have been analysed to indicate that the proposed Liu–Kozan algorithm is very generic because without modification it enables the construction of the feasible solutions for the FSS, BFSS, NWFSS, LBFSS and CBFSS problems. By employing the similar mechanism of the well-known NEH algorithm, a two-stage hybrid heuristic algorithm called the Liu–Kozan–BIH algorithm is developed to find a good CBFSS schedule in an efficient and economical way.     

Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine

This study deals with the problem of scheduling jobs on a single machine to minimize the mean absolute deviation of the job completion time about a large common due window subject to the maximum tardiness constraint. Using the well-known three-field notation, the problem is identified as MAD/large DueWindow/T_max. The common due window is set to be large enough to allow idle time prior to the beginning of a schedule to investigate the effect of the T_max constraint. Penalties arise if a job is completed outside the due window. A branch and bound algorithm and a heuristic are proposed. Many properties of the solutions and precedence relationships are identified. Our computational results reveal that the branch and bound algorithm is capable of solving problems of up to 50 jobs and the heuristic algorithm yields approximate solutions that are very close to the exact solution.     

Coordination of a production network with a single buyer and multiple vendors

This article considers a single buyer sourcing a single product from a network of homogeneous suppliers. We assume a close and cooperative relationship between buyer and vendors and suggest two coordination mechanisms, which differently affect where inventory is held in the system. Accordingly, we derive analytical and heuristic solutions for both alternatives and study the relative advantage of the models in a sensitivity analysis. Finally, propositions for future research are presented.     

An LP-based tabu search for batch scheduling in a cutting process with finite buffers

This paper addresses a cutting stock problem under typical resource constraints that arise when working centres with nesting capabilities are associated with automatic feeders/stackers. The critical resource is the number of buffers available to host the batches built up by the centre. To cope with it, pattern and batch sequencing problems must be addressed simultaneously. A tabu-search algorithm exploring batch output sequences is proposed. The algorithm never opens more stacks than buffers, respects batch compatibility/precedence constraints, and keeps the maximum order spread under control. To demonstrate its effectiveness and efficiency, a computational study was set up, solving 920 test problems derived from the literature. The study enabled a proper tuning of the method and offered encouraging results: in 228 cases an optimum was found; in nearly all, the gap from the optimum was below 1%. Computation times range from fractions of seconds to a couple of minutes in the worst cases. Compared to existing methods, the algorithm provides on average the same solution quality, with the advantage of solving a problem which is more general and hence closer to application. The paper includes a discussion on the method extensions required to deal with asynchronous stacking and heterogeneous batches.     

Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective

This paper addresses the problem of scheduling a set of independent jobs on unrelated parallel machines with job sequence dependent setup times so as to minimize a weighted mean completion time. The study of the problem stemmed from a real service industry problem. This problem is at least NP-hard in the ordinary sense, even when there are only two identical machines with no setups. Seven heuristic algorithms are proposed and tested by simulation. The results and analysis of quite extensive computational experiments are reported and discussed. The findings through the computational results are presented. Whether this problem is strongly NP-hard is left as an open question.     

Heuristics for operational fixed job scheduling problems with working and spread time constraints

Operational fixed job scheduling problems select a set of jobs having fixed ready and processing times and schedule the selected jobs on parallel machines so as to maximize the total weight. In this study, we consider working time and spread time constrained versions of the operational fixed job scheduling problems. The working time constraints limit the total processing load on each machine. The spread time constraints limit the time between the start of the first job and the finish of the last job on each machine. For the working time constrained problem, we present a filtered beam search algorithm that evaluates the promising nodes of the branch and bound tree. For the spread time constrained problem we propose a two phase algorithm that defines the promising sets for the first jobs and finds a solution for each promising set. The results of our computational tests reveal that our heuristic algorithms perform very well in terms of both solution quality and time.     

Scheduling a maintenance activity and due-window assignment based on common flow allowance

We study a due-window assignment problem on a single machine. The job-dependent due-windows are obtained by the common flow allowance criterion. The scheduler has the option to perform a maintenance activity which is rate modifying, i.e., improves the processing times of the following jobs. We consider a number of versions of this setting: (i) The maintenance requires a constant time, (ii) The maintenance duration is an increasing function of its starting time (linear deterioration), and (iii) The maintenance duration is position-dependent (general deterioration). We study the standard setting of regular job processing times, and investigate also the extension to position-dependent processing times. The set of potential optimal positions for the maintenance activity is fully characterized. Consequently, the problems based on all the combinations of these settings are shown to be solved in polynomial time.     

Two-stage flowshop earliness and tardiness machine scheduling involving a common due window

This paper studies a non-preemptive two-stage flowshop scheduling problem to minimize the earliness and tardiness under the environment of a common due window. The window size and the window location are considered to be given parameters. The just-in-time problem exists naturally and has many practical applications. The problem is shown to be NP-complete in the strong sense. We develop a branch and bound algorithm and a heuristic to solve the problem. We conduct the computational experiments to test the performances of the algorithms. A strong lower bound is derived for the branch and bound algorithm that can efficiently solve 15 jobs problem for about 5 minutes. The heuristic is shown to be efficient and effective, which can solve the problem of 150 jobs for about 20 seconds and provide near-optimal solution. We justify that the heuristic is an excellent solution approach for large problem instances. We also show that four special cases are either polynomial solvable or NP-complete in the ordinary sense.