A mathematical model for job shop scheduling with multiple process plan consideration per job

In this paper, a mixed integer programming model is formulated for scheduling a set of jobs through a shop when each job is supplied or provided with multiple process plans or process routings. Simultaneous selection of a process plan for each job and the sequencing of the jobs through the machines in the shop based on the set of selected process plans is addressed. The procedure developed seeks to integrate the selection of machines for each job and the sequencing of jobs on each machine based on the objective of minimizing production makespan. the application of the procedure is demonstrated with an example problem. The following conclusions were drawn as a result of the research: (1) the procedure developed produces optimal or near optimal solution; (2) the benefit from the developed approach is that it allows a shop to adaptively select process plans for jobs to optimize on production makespan. By combining solution quality with scheduling flexibility and efficiency, the productivity of a shop can be greatly enhanced.     

An Evaluation of Tour Scheduling Heuristics with Differences in Employee Productivity and Cost

This study focuses on the manpower tour scheduling problem using data from a lockbox system of a commercial bank. The lockbox system uses employees who differ in productivity, hourly cost, number of available working hours per week, and days-off constraints. These specific problem characteristics require a more general problem formulation and solution procedure for the manpower tour scheduling problem than addressed in previous research. Four heuristic methods for solving the problem (three developed here and a simple round-up procedure) are tested on a set of forty problems. The results of this study show the effort to develop sophisticated heuristic methods for this class of problems is well justified.     

SCHEDULING JOBS ON PARALLEL PROCESSORS WITH DYNAMIC PROGRAMMING

The problem of scheduling jobs on M-parallel processors is one of selecting a set of jobs to be processed from a set of available jobs in order to maximize profit. This problem is examined and a dynamic programming solution is presented which decomposes it into a sequencing problem within an allocation problem. The computation required for solution is found to depend on the sequencing problem as it is affected by the waiting cost function. Various forms of the waiting cost function are considered. The solution procedure is illustrated by an example, and possible extensions of the formulation are discussed.     

Single machine group scheduling to minimize mean flow time subject to due date constraints

This paper considers a single machine group scheduling problem. All jobs are classified into groups and the jobs within a group are processed contiguously on the machine. A sequence-independent setup time is incurred between each two consecutively scheduled groups. This paper presents a solution procedure which utilizes Smith's algorithm and a proposed modified Smith's algorithm to find an optimal job sequence and an optimal group sequence which minimizes the mean flow time of jobs subject to the constraint that no jobs are tardy. The complexity of the algorithm is shown to have a polynomial running time in the number of groups and jobs.     

Atypical Employment Relations and Government Policy in Europe

Abstract. This paper analyses government policy towards the two major forms of atypical work in Europe: part-time employment and temporary work. It is submitted that the policies implemented promote the volume of marginal part-time employment and temporary work. The policies aiming at more temporary jobs did not result in additional employment; they merely resulted in a redistribution of unemployment and a shift in the recruitment patterns in the direction of subsidised temporary jobs. Too much emphasis on numerical flexibility is not without danger. Countries run the risk that employers will not pay sufficient attention to the source of their long-term flexibility, manpower training. I t is argued that regular part-time work is an alternative for uncertain temporary jobs, Its potential expansion is considerable. Some recommendations are put forward to promote regular part-time jobs and improve the position of flexible part-time workers and temporary workers.     

Manpower requirements of scientists and engineers in high technology industries

This paper analyzes the impact on job requirements for engineers, scientists, technicians and skilled workers of the output of high technology and research intensive industries. The manpower requirements for 22 occupations resulting from a billion dollars of output of each of 12 industries are estimated for 1983. The manpower impacts of the total output of each industry are then simulated to determine the importance of economic activity in these industries in creating employment within each occupation in 1983. Occupational manpower requirements generated by the industries' 1983 outputs are analyzed in relation to total industry output and employment and total employment within each occupation. It is found that the industries analyzed here, although accounting for only 19% of GNP, are responsible for creating between 25% and 60% of many science, engineering and related jobs. These results are detailed for each industry and for every occupation, and the direct and the indirect manpower requirements for each occupation are computed. The implications of these findings are briefly discussed.     

Job Shop Scheduling With Deadlines

In this paper we deal with a variant of the Job ShopScheduling Problem. We consider the addition of release dates anddeadlines to be met by all jobs. The objective is makespanminimization if there are no tardy jobs, and tardiness minimizationotherwise. The problem is approached by using a Shifting Bottleneckstrategy. The presence of deadlines motivates an iterative use of aparticular one machine problem which is solved optimally. Theoverall procedure is heuristic and exhibits a good trade-off betweencomputing time and solution quality.     

A Probabilistic Feasibility and Value Analysis of the Generalized Assignment Problem

We study the generalized assignment problem, under a probabilistic model for its cost and requirement parameters. First we address the issue of feasibility by deriving a tight condition on the probabilistic model that ensures that the corresponding problem instances are feasible with probability one as the number of jobs goes to infinity. Then, under an additional condition on the parameters, we show that the optimal solution value, normalized by dividing by the number of jobs, converges with probability one to a constant, again as the number of jobs goes to infinity. Finally, we discuss various examples.     

A generalized procedure for minimizing makespan in a CNC environment

This paper presents the problem of scheduling N jobs, each manufactured in a number of settings, in order, on a CNC machine equipped with an automatic tool changer. A generalized procedure to minimize makespan in a CNC environment has been developed and tested on real industrial problems, considering possible constraints. It is worthy of mention that the procedure suggested finds an optimal solution of the problem discussed by Sule in a short and simplified manner. The step-by-step analysis shows the simplicity and flexibility of the proposed approach.     

An integrated approach for manpower planning in the service sector

The manpower planning problem receives considerable attention by the management of service organizations because they are typically labor intensive. Not only must optimal staff sizes be determined over an extended horizon, but optimal staff schedules which assign labor to tours of duty and specific tasks, given the available staff size, must also be found. Adding to the complexity arising from the interrelatedness of the staff-sizing and staff-scheduling problems is the existence of the conflicting multiple objectives of minimizing costs and maximizing customer service. The few methodologies reported in the literature which treat the complete manpower planning problem as stated above have several shortcomings. Some techniques place a severe strain on computational capabilities. Also, these methods confound the specification of the goal levels with the analysis of the relative goal weightings. Often the specification of the desired goal levels is made at a different level in the organizational hierarchy than the specification of the relative importance of the various goals. This paper suggests an approach which overcomes these shortcomings. The methodology utilizes a simulation model with an imbedded heuristic procedure for the staff-scheduling problem to identify realistic aggregate staff-size goals to be used in a multiple-objective staff-sizing model. The methodology is applied to the manpower planning problem of a large sectional center post office and the managerial benefits are discussed.     

Developing a manpower strategy for an industry

This paper considers the following issues for developing an industry manpower strategy. An idea of the national system that exists for implementing a manpower strategy. The main questions arising from the strategy, and a definition of manpower planning. From this, the information and analysis techniques used to identify the strategy. The first application produces a manpower picture of the foundry industry. For company manpower planning the paper describes a manpower model of a company, and how the relationship between the activity and employment patterns of boundries was investigated. The industry findings are verified by company manpower planning investigations using the same information and techniques. The conclusions discuss some of the strengths and weaknesses of using this approach.     

A SINGLE-MACHINE SCHEDULING MODEL WITH FIXED-INTERVAL DELIVERIES

We consider an environment where a production facility modeled as a single machine needs to assign delivery dates to several orders and find a feasible sequence. Tardy jobs are not allowed. The delivery dates are to be at prespecified fixed intervals. The objective is to minimize the due date penalty and the cost of earliness. We provide a dynamic programming-based solution procedure that runs in polynomial time. We develop several dominance results that reduced the computational requirement by an order of magnitude in our computational study.     

A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs,financial budget,and resource constraint in multiple manufacturers

We study a coordinated serial-batching scheduling problem that features deteriorating jobs, financial budget, resource constraints, resource-dependent processing times, setup times, and multiple manufacturers simultaneously. A unique feature but also a significant challenge in this problem is the dual constraints on resources, i.e., financial budget and resource quantity. Some key structural properties are first identified for the setting where the jobs and resources are already assigned to each manufacturer, which enables us to develop the optimal resource allocation scheme. Then, a polynomial-time scheduling rule is proposed to search for the optimal solution for each manufacturer in this setting. Then, a hybrid BA-VNS algorithm combining Bat algorithm (BA) and variable neighborhood search (VNS) is proposed to tackle the studied problem, and the optimal scheduling rule is implemented in its encoding procedure. Finally, computational experiments are conducted to test the performance of the proposed algorithm, and the efficiency and improvements are compared with those of BA, VNS, and Particle Swarm Optimization (PSO), with respect to convergence speed as well as computational stability.     

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.     

加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。     

A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance

We study a single-machine scheduling model combining two competing agents and due-date assignment. The basic setting involves two agents who need to process their own sets of jobs, and compete on the use of a common processor. Our goal is to find the joint schedule that minimizes the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. The scheduling measure considered in this paper is minimum total (earliness, tardiness and due-date) cost, based on common flow allowance, i.e., due-dates are defined as linear functions of the job processing times. We introduce a simple polynomial time solution for this problem (linear in the number of jobs), as well as to its extension to a multi-agent setting. We further extend the model to that of a due-window assignment based on common flow allowance.     

Manpower allocation in the criminal investigation process

A model describing the optimal allocation of manpower for the investigation department of the Israeli police force is described. A technique for estimating police officials preferences is given. It is believed that the approach and the methodology used can be applied in various manpower allocation problems and can serve as a good case study.     

Some statistical aspects of manpower planning in the civil service

A special feature of modern manpower planning methods is the use of computer-based statistical models, and the Civil Service Department is taking the lead in their development and use for manpower planning in the non-industrial Civil Service. Account is being taken of related data requirements in the development of a new Personnel Record Information System which will replace a range of existing records.Development work in hand covers both the “demand” and “supply” aspects of manpower planning and a bank of generalized “supply” models is in operation. Stationary population, renewal and Markovian principles are involved, and the particular statistical problems of modelling small manpower groups are being met in the development of a “small group” simulation model.     

An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem

In the no-idle flowshop, machines cannot be idle after finishing one job and before starting the next one. Therefore, start times of jobs must be delayed to guarantee this constraint. In practice machines show this behavior as it might be technically unfeasible or uneconomical to stop a machine in between jobs. This has important ramifications in the modern industry including fiber glass processing, foundries, production of integrated circuits and the steel making industry, among others. However, to assume that all machines in the shop have this no-idle constraint is not realistic. To the best of our knowledge, this is the first paper to study the mixed no-idle extension where only some machines have the no-idle constraint. We present a mixed integer programming model for this new problem and the equations to calculate the makespan. We also propose a set of formulas to accelerate the calculation of insertions that is used both in heuristics as well as in the local search procedures. An effective iterated greedy (IG) algorithm is proposed. We use an NEH-based heuristic to construct a high quality initial solution. A local search using the proposed accelerations is employed to emphasize intensification and exploration in the IG. A new destruction and construction procedure is also shown. To evaluate the proposed algorithm, we present several adaptations of other well-known and recent metaheuristics for the problem and conduct a comprehensive set of computational and statistical experiments with a total of 1750 instances. The results show that the proposed IG algorithm outperforms existing methods in the no-idle and in the mixed no-idle scenarios by a significant margin.     

A simulation-based dynamic operator assignment strategy considering machine interference - a case study on integrated circuit chip moulding operations

A simulation-based dynamic operator assignment strategy is proposed considering machine interference in solving an integrated circuit moulding operation problem. The strategy iteratively solves a floating manpower operator-assignment problem between simulation-based diagnostic study and operator assignment decision. Given current-state information, it provides a means for system performance evaluation. It searches a satisfactory solution for both cycle time and service level performances by using floating manpower method. A structured experimental design is used to illustrate the effectiveness of the proposed methodology. Empirical results show promise for the proposed methodology in solving a practical application. Finally, the system implementation constraints from both hardware and management problems are addressed.