Scatter search with path relinking for multiprocessor open shop scheduling Abstract   Maintenance and health care diagnostic systems are generally composed of different workstations pertaining to technologically different processes. A workstation is composed of one or more parallel machines. In such systems, the multiprocessor open shop scheduling problem is commonly encountered. It is concerned with assigning processing intervals for each job on machines that need to be selected in each requested workstation. Meanwhile, jobs do not require a specific order for visiting workstations. This paper considers a static, deterministic version of the problem in which jobs do not have to visit all workstations, the workstations do not necessarily have identical machines, and the processing times depend on both the job and the machine. The objective is to minimize the maximum completion time (makespan) which is commensurate with maximizing the utilization of the available machines. To the best of our knowledge, this problem structure has not been considered in the literature before despite its existence in reallife applications. Since it is NPhard problem, efficient heuristics are needed to generate near optimal solutions in practically acceptable computational times. In this paper, two neighborhood search functions and two solution combination functions are developed and used within a scatter search with path relinking metaheuristic, along with a new distance definition between solutions. Computational experiments are conducted first to select the best levels of the metaheuristic parameters. Then, computational experiments are conducted on specially designed instances that take into consideration different settings of the studied problem. This is followed by computational experiments on a set of benchmark instances of the proportionate multiprocessor open shop scheduling problem which is a special case of the studied problem for which other metaheuristics have been developed in the literature. Results show that the developed metaheuristic is capable of generating optimal or nearoptimal solutions for different configurations of the studied problem. In addition, it generates competitive results for the proportionate case compared to the available metaheuristics with 18 new upper bounds; among them seven are optimal.

NonPreemptive Open Shop Scheduling Considering Machine Availability This paper considers a nonpreemptive open shop scheduling problem (OSSP), in which machines are not available to process jobs on known periodic interval times resulted from periodic service repair, rest period, and so on. Asymmetric transportation time between machines is considered, which can be different from one job to another. The objective is to minimize the weighted mean completion time (WMCT). Since the problem is categorized into NPhard class, two metaheuristic algorithms including genetic algorithm (GA) and differential evolution (DE) are proposed. Meanwhile, a new initial population is introduced, which significantly improves the performance of the algorithms. Finally, the performance of the algorithms is validated through some largesized instances and the results are discussed.